Mastering Algorithms for Problem Solving in Java/

...

/

Best-First: Dijkstra’s Algorithm

Best-First: Dijkstra’s Algorithm

Learn about Dijkstra’s algorithm and its applications in solving the shortest paths problem.

We'll cover the following...

Proof of tenseness property in Dijkstra’s algorithm

If we replace the FIFO queue in breadth-first search with a priority queue, where the key of a vertex vv is its tentative distance dist(v)dist(v), we obtain an algorithm first published in 1957 by a team of researchers at the Case Institute of Technology led by Michael Leyzorek, in an annual project report for the Combat Development Department of the US Army Electronic Proving Ground. The same algorithm was independently discovered by Edsger Dijkstra in 1956 (but not published until 1959), again by George Minty sometime before 1960, and again by Peter Whiting and John Hillier in 1960. A nearly identical algorithm was also described by George Dantzig in 1958. Although several early sources called it “Minty’s algorithm,” this approach is now universally known as “Dijkstra’s algorithm,” in full accordance with Stigler’s Law. The pseudocode for this algorithm is shown below.

An easy induction proof implies that at all times during the execution of this algorithm, an edge u→vu\rightarrow v is tense if and only if vertex uu is either in the priority queue or is the vertex most recently ExtractExtracted from the priority queue. Thus, Dijkstra’s algorithm is an instance of Ford’s general strategy, which implies that it correctly computes shortest paths, provided there are no negative cycles in GG.

The image below is a visualization of computing the shortest paths in a dag by relaxing outgoing edges in topological order. In each iteration, bold edges indicate predecessors, and the bold vertex is about to be scanned.

Algorithm

Dijkstra(s):‾InitSSSP(s)Insert(s,0)while the priority queue is not emptyu←ExtractMin()for all edges u→vif u→v is tenseRelax(u→v)if v is in the priority queueDecreaseKey(v,dist(v))elseInsert(v,dist(v))\underline{Dijkstra(s):} \\ \hspace{0.4cm} InitSSSP(s) \\ \hspace{0.4cm} Insert(s, 0) \\ \hspace{0.4cm} while\space the\space priority\space queue\space is\space not\space empty \\ \hspace{1cm} u ← ExtractMin( ) \\ \hspace{1cm} for\space all\space edges\space u\rightarrow v \\ \hspace{1.7cm} if \space u\rightarrow v\space is\space tense \\ \hspace{2.3cm} Relax(u\rightarrow v) \\ \hspace{2.3cm} if\space v\space is\space in\space the\space priority\space queue \\ \hspace{2.7cm} DecreaseKey(v, dist(v)) \\ \hspace{2.3cm} else \\ \hspace{2.7cm} Insert(v, dist(v))

Implementation

Press + to interact
import java.util.*;
// Graph data structure
class Graph {
    int V; // number of vertices
    List<List<Map.Entry<Integer, Integer>>> adj; // adjacency list
    Graph(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }
    void addEdge(int u, int v, int w) {
        adj.get(u).add(new AbstractMap.SimpleEntry<>(v, w));
    }
}
// Dijkstra's algorithm
class Dijkstra {
    void initSSSP(int s, List<Integer> dist) {
        Collections.fill(dist, Integer.MAX_VALUE);
        dist.set(s, 0);
    }
    void shortestPath(int s, Graph G) {
        List<Integer> dist = new ArrayList<>(G.V);
        for (int i = 0; i < G.V; i++) {
            dist.add(Integer.MAX_VALUE);
        }
        initSSSP(s, dist);
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getKey));
        pq.offer(new AbstractMap.SimpleEntry<>(0, s));
        while (!pq.isEmpty()) {
            Map.Entry<Integer, Integer> front = pq.poll();
            int u = front.getValue();
            int d = front.getKey();
            if (d > dist.get(u)) {
                continue;
            }
            for (Map.Entry<Integer, Integer> edge : G.adj.get(u)) {
                int v = edge.getKey();
                int w = edge.getValue();
                if (dist.get(u) != Integer.MAX_VALUE && dist.get(v) > dist.get(u) + w) {
                    dist.set(v, dist.get(u) + w);
                    pq.offer(new AbstractMap.SimpleEntry<>(dist.get(v), v));
                }
            }
        }
        // Print the shortest path distances
        for (int i = 0; i < G.V; ++i) {
            System.out.println("Shortest path from " + s + " to " + i + " is " + dist.get(i));
        }
    }
}
// Driver code
public class Main {
    public static void main(String[] args) {
        int V = 5;
        Graph G = new Graph(V);
        G.addEdge(0, 1, 10);
        G.addEdge(0, 2, 5);
        G.addEdge(1, 2, 2);
        G.addEdge(1, 3, 1);
        G.addEdge(2, 1, 3);
        G.addEdge(2, 3, 9);
        G.addEdge(2, 4, 2);
        G.addEdge(3, 4, 4);
        G.addEdge(4, 3, 6);
        Dijkstra dijkstra = new Dijkstra();
        dijkstra.shortestPath(0, G);
    }
}

Explanation

  • Lines 8–15: These lines define a constructor for the Graph class that takes an integer V representing the number of vertices in the graph.
  • Lines 23–26: The initSSSP function is used to initialize the dist list, which holds the shortest path distances from the source node to all other nodes in the graph.
  • Lines 57–59: These print the shortest path on the console.

No negative edges

Dijkstra’s algorithm is particularly well-behaved when the input graph has no negative-weight edges. In this setting, the algorithm intuitively expands a wavefront outward from the source vertex ss, passing over vertices in increasing order of their distance from ss, similarly to breadth-first search. The figure below shows the algorithm in action.

The illustration shows the first four iterations of Dijkstra’s algorithm on a graph with no negative edges. In each iteration, bold edges indicate predecessors; shaded vertices are in the priority queue; and the bold vertex is about to be scanned. The remaining iterations do not change the distances or the shortest-path tree.

We can derive a self-contained proof of correctness for Dijkstra’s algorithm in this setting by formalizing this wavefront intuition. For each integer ii, let uiu_i denote the vertex returned by the iith call to ExtractMinExtractMin, and let did_i be the value of dist(ui)dist(u_i) just after this ExtractExtraction. In particular, we have u1=su_1 = s and d1=0d_1 = 0. We cannot assume at this point that the vertices uiu_i are distinct; in principle, the same vertex might be ExtractExtracted more than once.

Lemma 1: If GG ...