Algorithm - Dijkstra

ShortestPathDijkstra.java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

/**
 * Dijkstra Java Implementation
 * 
 */
public class ShortestPathDijkstra {
  private int dist[];
  private Set<Integer> settled;
  private PriorityQueue<ShortestPathDijkstraNode> pq;
  private int V; // Number of vertices
  List<List<ShortestPathDijkstraNode>> adj;

  public ShortestPathDijkstra(int V) {
    this.V = V;
    dist = new int[V];
    settled = new HashSet<>();
    pq = new PriorityQueue<>(V, new ShortestPathDijkstraNode());
  }

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    while (true) {
      int n = sc.nextInt();
      int m = sc.nextInt();
      int q = sc.nextInt();
      int s = sc.nextInt();

      if (n == 0 && m == 0 && q == 0 && s == 0) {
        return;
      }

      // Adjacency list representation of the
      // connected edges
      List<List<ShortestPathDijkstraNode>> adj = new ArrayList<>();

      // Initialize list for every node
      for (int i = 0; i < n; i++) {
        List<ShortestPathDijkstraNode> item = new ArrayList<>();
        adj.add(item);
      }

      for (int i = 0; i < m; i++) {

        int u = sc.nextInt();
        int v = sc.nextInt();
        int w = sc.nextInt();

        adj.get(u).add(new ShortestPathDijkstraNode(v, w));
      }

      // Calculate the single source shortest path
      ShortestPathDijkstra dpq = new ShortestPathDijkstra(n);
      dpq.dijkstra(adj, s);

      for (int i = 0; i < q; i++) {
        int t = sc.nextInt();

        if (dpq.dist[t] < Integer.MAX_VALUE) {
          System.out.println(dpq.dist[t]);
        } else {
          System.out.println("Impossible");
        }
      }

      System.out.println();
    }
  }

  // Function for Dijkstra's Algorithm
  public void dijkstra(List<List<ShortestPathDijkstraNode>> adj, int src) {
    this.adj = adj;

    for (int i = 0; i < V; i++) {
      dist[i] = Integer.MAX_VALUE;
    }

    // Add source node to the priority queue
    pq.add(new ShortestPathDijkstraNode(src, 0));

    // Dist at source is 0
    dist[src] = 0;

    while (!pq.isEmpty()) {

      // remove the minimum distance node
      // from the priority queue
      int u = pq.remove().node;

      // adding the node whose distance is
      // finalized
      settled.add(u);

      processNeighbours(u);
    }
  }

  // Function to process all the neighbours
  // of the passed node
  private void processNeighbours(int u) {
    int edgeDistance = -1;
    int newDistance = -1;

    // All the neighbors of v
    for (int i = 0; i < adj.get(u).size(); i++) {
      ShortestPathDijkstraNode v = adj.get(u).get(i);

      // If current node hasn't already been processed
      if (!settled.contains(v.node)) {
        edgeDistance = v.cost;
        newDistance = dist[u] + edgeDistance;

        // If new distance is cheaper in cost
        if (newDistance < dist[v.node]) {
          dist[v.node] = newDistance;

          // TODO: only add to the pq if it's better (changed)
          // Add the current node to the queue
          pq.add(new ShortestPathDijkstraNode(v.node, dist[v.node]));
        }
      }
    }
  }
}

// Class to represent a node in the graph
class ShortestPathDijkstraNode implements Comparator<ShortestPathDijkstraNode> {
  public int node;
  public int cost;

  public ShortestPathDijkstraNode(int node, int cost) {
    this.node = node;
    this.cost = cost;
  }

  @Override
  public int compare(ShortestPathDijkstraNode node1, ShortestPathDijkstraNode node2) {
    if (node1.cost < node2.cost) {
      return -1;
    }
    if (node1.cost > node2.cost) {
      return 1;
    }

    return 0;
  }
}