Solving Graph Problems (Part 3) - Dijkstra

Problem Source: UVA Online Judge - 10986

Brief Analysis: As a first problem of Dijkstra, a very straight-forward problem chosen. Just read and code.

Java Code:

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;

public class Main {

    static int NODE, EDGE;
    static List<Node>[] G;
    static int[] parent, dist;
    static PriorityQueue<Node> Q;
    static int source, dest;

    static void dijkstra() {
        dist = new int[NODE];
        for (int i = 0; i < NODE; i++) dist[i] = Integer.MAX_VALUE;
        parent = new int[NODE];
        for (int i = 0; i < NODE; i++) parent[i] = -1;
        Q = new PriorityQueue<>();

        Node u, v;

        dist[source] = 0;
        u = new Node(source, 0);
        Q.add(u);

        while (!Q.isEmpty()) {
            u = Q.poll();

            for (int i = 0; i < G[u.label].size(); i++) {
                Node t = G[u.label].get(i);

                if (dist[u.label] + t.dist < dist[t.label]) {
                    dist[t.label] = dist[u.label] + t.dist;
                    parent[t.label] = u.label;
                    v = new Node(t.label, dist[t.label]);
                    Q.add(v);
                }
            }
        }
    }

    static class Node implements Comparable<Node> {
        int label, dist;

        public Node() {

        }

        public Node(int label, int dist) {
            this.label = label;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return dist - o.dist;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = inputFromSystem();

        int TC, tc;

        TC = scanner.nextInt();

        for (tc = 1; tc <= TC; tc++) {
            NODE = scanner.nextInt();
            EDGE = scanner.nextInt();
            source = scanner.nextInt();
            dest = scanner.nextInt();

            G = new ArrayList[NODE];
            for (int i = 0; i < NODE; i++) G[i] = new ArrayList<>();

            for (int i = 0; i < EDGE; i++) {
                int u = scanner.nextInt();
                int v = scanner.nextInt();
                int c = scanner.nextInt();

                G[u].add(new Node(v, c));
                G[v].add(new Node(u, c));
            }

            dijkstra();

            System.out.print("Case #" + tc + ": ");
            if (dist[dest] == Integer.MAX_VALUE) System.out.println("unreachable");
            else System.out.println(dist[dest]);
        }
    }

    static Scanner inputFromFile() {
        try { return new Scanner(new FileInputStream("input.txt")); }
        catch (FileNotFoundException e) { e.printStackTrace(); }
        return null;
    }

    static Scanner inputFromSystem() {
        return new Scanner(System.in);
    }
}

Few others Dijkstra problems:

  1. UVA Online Judge - 11377
  2. UVA Online Judge - 11492
  3. UVA Online Judge - 11833
  4. UVA Online Judge - 12047
  5. UVA Online Judge - 12144
Blog Comments powered by Disqus.

Next Post Previous Post