Dijkstra Algorithm

The Dijkstra Algorithm finds the shortest path from a source to all destination in a directed graph, i.e., single source shortest path problem. During the process, it will also determine a spanning tree for the graph.

Dijkstra partitions all nodes into two distinct sets. Unsettled and settled. Initially all nodes are in the unsettled sets, e.g., they must be still evaluated. A node is move to the settled set if a shortest path from the source to this node has been found.
Initially the distance of each node to the source is set to a very high value, e.g., Integer.MAX_VALUE.

The algorithms runs until the unsettledNodes are empty. In each iteration it selects the node with the lowest distance from the source out the unsettled nodes.

I used my previous Graph class. However, I added a new method chooseSource(int label) to select a node in the graph as the source node. In the node class, I added one more variable, initially assigned to Integer.MAX_VALUE, if a source node is chosen, the distance of the source is set to 0. Then when we construct the Dijkstra class, all shortest paths to the source node can be acquired.

public void chooseSource(int label) {
  Node source = getNode(label);
  source.dist = 0;
  
 }

The Dijkstra class:

import java.util.*;
public class Dijkstra {
 private Graph g;
 private int[] distTo;
 Node source;
 private int[] predecessor;
 private PriorityQueue pq;
 
 public Dijkstra(Graph G, int s) {
  this.g = G;
  g.chooseSource(s);
  pq = new PriorityQueue (new NodeComparator());
  source = g.getNode(s);
  pq.add(source);
  distTo = new int[g.getSize()];
  distTo[s - 1] = 0; 
  predecessor = new int[g.getSize() + 1];
  predecessor[s] = -1;
 }
 public void getShortestPath() {
  while (!pq.isEmpty()) {
   Node curr = pq.poll();
   for (Node w : curr.neighbors) {
    int distanceToSource = curr.dist + curr.edges.get(w).getWeight(curr, w);
    if (distanceToSource < w.dist) {
     pq.remove(w);
     w.dist = distanceToSource;
     predecessor[w.label] = curr.label;
     pq.add(w);
    }
   }
  }
 }
 /**
  * get the shortest path from source to target node
  * @param n
  */
 public void getShortestPath(int target) {
  boolean found = false;
  while (!pq.isEmpty() && !found) {
   Node curr = pq.poll();
   for (Node w : curr.neighbors) {
    int distanceToSource = curr.dist + curr.edges.get(w).getWeight(curr, w);
    if (distanceToSource < w.dist) {
     pq.remove(w);
     w.dist = distanceToSource;
     predecessor[w.label] = curr.label;
     pq.add(w);
    }
    if (w.label == target) {
     found = true;
     break;
    }
   }
  }
  
 }
 public String shortestPath(int label) {
  Node target = g.getNode(label);
  String NEWLINE = System.getProperty("line.separator");
  StringBuilder sb = new StringBuilder();
  sb.append("The shortest distance from " + label + " to source " + source.label 
    + " is: " + target.dist);
  sb.append(NEWLINE);
  int x;
  for (x = label; g.getNode(x).dist != 0; x = predecessor[x]) {
   sb.append(x + " -> ");
  }
  sb.append(source.label);
  //sb.delete(sb.length() - 4, sb.length() - 1);
  sb.append(NEWLINE);
  return sb.toString();
 }
 private class NodeComparator implements Comparator {
  
  public int compare(Node a, Node b) {
   if (a.dist - b.dist < 0)
    return -1;
   else if (a.dist - b.dist > 0)
    return 1;
   return 0;
  }
 }
}