This tutorial will introduce Dijkstra's algorithm, including a proof of correctness and time complexity analysis.
I have included a LaTeX typeset version of this tutorial.
Number of downloads: 1845
I. Introduction
Dijkstra's algorithm is used to find the shortest path between two vertices of a graph. More formally, we fix a starting vertex in the graph, vertex a. Dijkstra's algorithm then returns the shortest path from vertex a to every other vertex in the graph. We assume the graph is weighted and has no negative weights.
II. Breadth-First Traversal
Dijkstra's algorithm is an adaptation of the breadth-first traversal algorithm. So it is important to first understand the breadth-first traversal (BFS) algorithm. The BFS algorithm accepts a graph G(V, E) and initial vertex a in V. The algorithm then manages a queue, which dictates the order to visit the vertices. It then visits each of a's neighbors, pushing them onto the queue as they are visited. Then as long as the queue is non-empty, we poll a vertex, mark it as visited, and add all of its unvisited neighbors to the queue.
Let's consider an example. Given the graph below and the starting vertex 1, we examine the order in which the vertices are visited. While you can choose to visit neighbor vertices in any order, I will visit them from lowest label to highest label.
Start at the initial vertex 1 and mark it as visited. Now we visit each neighbor in the order 2, 3, 7, mark them as visited, and push each onto the queue respectively. So the queue is now: Q = [2, 3, 7].
Next, we poll 2 from the queue, leaving Q = [3, 7]. We have that 2's neighbors are 1, 3, 7, all of which have been visited. So we do nothing. Next, poll 3 from the queue. We push its unvisited neighbors- 4, 5, 6 onto the queue, marking them as visited along the way. This leaves Q = [7, 4, 5, 6].
Notice now that the vertices in Q have no unvisited neighbors in the graph. So the order the vertices are visited by the algorithm is: 1, 2, 3, 7, 4, 5, 6.
Dijkstra's Algorithm
Dijkstra's Algorithm works similarly as the BFS algorithm. We begin with a weighted graph G(V, E, W) where W is the weight function W : E -> R+, as well as an initial vertex a in V. That is, each edge has a non-negative weight. With each vertex, we associate a distance marker which denotes the distance from a, as well as the predecessor in the shortest path found by the algorithm. This allows us to not only find the distance of the shortest a-v path for any vertex v in V, but to explicitly access the path as well.
We begin by starting at a, and marking every other vertex as having distance infinity from a. We visit each neighbor v of a and: first set v's distance marker to W(a, v) then v's predecessor to a. Then, we push vertex adjacent to a onto a priority queue. The priority queue orders vertices by their distance markers. Finally, we mark the initial vertex as visited. No marked vertex can be used in future iterations.
Now, while the priority queue still has elements, we do the following. First, poll a vertex v from the priority queue. For each unvisited neighbor x of v, we check if dist(a, v) + W(v, x) < dist(a, x). If this condition is satisfied, we update x's distance marker to dist(a, v) + W(v, x). Next, we update x's predecessor to v, then update x's position in the priority queue.
After visiting all of v's neighbors, we mark v as visited.
Let's work through an example. Consider the following graph, and suppose we want vertex A as the root.
We start by setting dist(A, B) = 6, dist(A, D) = 1. Then we set B's and D's predecessor to A. Next, we push B and D into the priority queue, which is ordered: [D, B]. Finally, we mark A as visited.
Now poll D from the priority queue. We note dist(A, D) + W(D, B) = 3 < dist(A, B) = 6. So update dist(A, B) := 3 and set B's predecessor to D. Now, examine (D, E). We set dist(A, E) = dist(A, D) + W(D, E) = 2 and E's predecessor to D. We now push E onto the priority queue, which stores the elements in order: [E, B]. Now mark D as visited.
Now poll E from the priority queue. We note dist(A, E) + W(E, B) = 4 > dist(A, B), so we discard (E, B). Now consider (A, C). Since dist(A, E) + W(E, C) = 7 < infinity, so we set dist(A, C) := 7 and C's predecessor to E. Next, we push C onto the priority queue, which stores the elements in order [B, C]. Now mark E as visited.
Now poll B from the priority queue. We note dist(A, B) + W(B, C) = 8 > dist(A, C), we discard (B, C). We mark B as visited. The priority queue now contains [C] and no other vertices are unvisited. After polling C, the algorithm terminates.
The lengths of the shortest paths are as follows:
- dist(A, B) = 3
- dist(A, C) = 7
- dist(A, D) = 1
- dist(A, E) = 2
Now let's examine an implementation. We design the Dijkstra's class to accept a Graph and construct a shortest-path tree. We use HashMaps to store the predecessor of each vertex in the shortest paths, and to store the distances from the initial vertex to every other vertex in the graph.
We begin by visiting each of initialVertex's neighbors, updating their distances from initialVertex, and pushing them onto the PriorityQueue. We then mark initialVertex as visited and proceed with the rest of the algorithm. The processGraph() method handles the remainder of the algorithm. It polls the first vertex from the PriorityQueue and updates the distances as necessary to each of its unvisited neighbors. It then removes and re-adds any updated neighbors to the PriorityQueue to update their positions. In this way, the unvisited vertex with the smallest distance from initialVertex is polled from the PriorityQueue.
The getPathTo() and getDistanceTo() methods return the path and distance respectively from initialVertex to a chosen vertex in the graph. The getPathTo() method starts at the target vertex and traces the predecessors back to initialVertex.
import java.util.*; /** * * @author Michael Levet */ public class Dijkstra { private Graph graph; private String initialVertexLabel; private HashMap<String, String> predecessors; private HashMap<String, Integer> distances; private PriorityQueue<Vertex> availableVertices; private HashSet<Vertex> visitedVertices; /** * This constructor initializes this Dijkstra object and executes * Dijkstra's algorithm on the graph given the specified initialVertexLabel. * After the algorithm terminates, the shortest a-b paths and the corresponding * distances will be available for all vertices b in the graph. * * @param graph The Graph to traverse * @param initialVertexLabel The starting Vertex label * @throws IllegalArgumentException If the specified initial vertex is not in the Graph */ public Dijkstra(Graph graph, String initialVertexLabel){ this.graph = graph; Set<String> vertexKeys = this.graph.vertexKeys(); if(!vertexKeys.contains(initialVertexLabel)){ throw new IllegalArgumentException("The graph must contain the initial vertex."); } this.initialVertexLabel = initialVertexLabel; this.predecessors = new HashMap<String, String>(); this.distances = new HashMap<String, Integer>(); this.availableVertices = new PriorityQueue<Vertex>(vertexKeys.size(), new Comparator<Vertex>(){ public int compare(Vertex one, Vertex two){ int weightOne = Dijkstra.this.distances.get(one.getLabel()); int weightTwo = Dijkstra.this.distances.get(two.getLabel()); return weightOne - weightTwo; } }); this.visitedVertices = new HashSet<Vertex>(); //for each Vertex in the graph //assume it has distance infinity denoted by Integer.MAX_VALUE for(String key: vertexKeys){ this.predecessors.put(key, null); this.distances.put(key, Integer.MAX_VALUE); } //the distance from the initial vertex to itself is 0 this.distances.put(initialVertexLabel, 0); //and seed initialVertex's neighbors Vertex initialVertex = this.graph.getVertex(initialVertexLabel); ArrayList<Edge> initialVertexNeighbors = initialVertex.getNeighbors(); for(Edge e : initialVertexNeighbors){ Vertex other = e.getNeighbor(initialVertex); this.predecessors.put(other.getLabel(), initialVertexLabel); this.distances.put(other.getLabel(), e.getWeight()); this.availableVertices.add(other); } this.visitedVertices.add(initialVertex); //now apply Dijkstra's algorithm to the Graph processGraph(); } /** * This method applies Dijkstra's algorithm to the graph using the Vertex * specified by initialVertexLabel as the starting point. * * @post The shortest a-b paths as specified by Dijkstra's algorithm and * their distances are available */ private void processGraph(){ //as long as there are Edges to process while(this.availableVertices.size() > 0){ //pick the cheapest vertex Vertex next = this.availableVertices.poll(); int distanceToNext = this.distances.get(next.getLabel()); //and for each available neighbor of the chosen vertex List<Edge> nextNeighbors = next.getNeighbors(); for(Edge e: nextNeighbors){ Vertex other = e.getNeighbor(next); if(this.visitedVertices.contains(other)){ continue; } //we check if a shorter path exists //and update to indicate a new shortest found path //in the graph int currentWeight = this.distances.get(other.getLabel()); int newWeight = distanceToNext + e.getWeight(); if(newWeight < currentWeight){ this.predecessors.put(other.getLabel(), next.getLabel()); this.distances.put(other.getLabel(), newWeight); this.availableVertices.remove(other); this.availableVertices.add(other); } } // finally, mark the selected vertex as visited // so we don't revisit it this.visitedVertices.add(next); } } /** * * @param destinationLabel The Vertex whose shortest path from the initial Vertex is desired * @return LinkedList<Vertex> A sequence of Vertex objects starting at the * initial Vertex and terminating at the Vertex specified by destinationLabel. * The path is the shortest path specified by Dijkstra's algorithm. */ public List<Vertex> getPathTo(String destinationLabel){ LinkedList<Vertex> path = new LinkedList<Vertex>(); path.add(graph.getVertex(destinationLabel)); while(!destinationLabel.equals(this.initialVertexLabel)){ Vertex predecessor = graph.getVertex(this.predecessors.get(destinationLabel)); destinationLabel = predecessor.getLabel(); path.add(0, predecessor); } return path; } /** * * @param destinationLabel The Vertex to determine the distance from the initial Vertex * @return int The distance from the initial Vertex to the Vertex specified by destinationLabel */ public int getDistanceTo(String destinationLabel){ return this.distances.get(destinationLabel); } public static void main(String[] args){ Graph graph = new Graph(); Vertex[] vertices = new Vertex[6]; for(int i = 0; i < vertices.length; i++){ vertices[i] = new Vertex(i + ""); graph.addVertex(vertices[i], true); } Edge[] edges = new Edge[9]; edges[0] = new Edge(vertices[0], vertices[1], 7); edges[1] = new Edge(vertices[0], vertices[2], 9); edges[2] = new Edge(vertices[0], vertices[5], 14); edges[3] = new Edge(vertices[1], vertices[2], 10); edges[4] = new Edge(vertices[1], vertices[3], 15); edges[5] = new Edge(vertices[2], vertices[3], 11); edges[6] = new Edge(vertices[2], vertices[5], 2); edges[7] = new Edge(vertices[3], vertices[4], 6); edges[8] = new Edge(vertices[4], vertices[5], 9); for(Edge e: edges){ graph.addEdge(e.getOne(), e.getTwo(), e.getWeight()); } Dijkstra dijkstra = new Dijkstra(graph, vertices[0].getLabel()); System.out.println(dijkstra.getDistanceTo("5")); System.out.println(dijkstra.getPathTo("5")); } }
We use the Graph implementation from my previous tutorial included here:
Spoiler
Analysis of Dijkstra's Algorithm
In this section, we analyze the correctness and complexity of Dijkstra's Algorithm. The design of this algorithm leverages the optimal substructure exhibited by the shortest path problem. Formally, a problem is said to exhibit the optimal substructure property if an optimal solution contains within it solutions to the present optimal subproblems. We prove this formally.
Claim 1: Let G be a connected graph and let x, y be vertices in G. Let P be a shortest x-y path. Then for any pair of vertices a, b in P, it follows that P contains a shortest a-b path.
Proof: Suppose to the contrary. Let P be a shortest x-y path such that for vertices a, b in P, that the a-b sub-path in P is not a shortest a-b path. Let Q be a shortest a-b path. We replace the a-b sub-path in P with Q to obtain an x-y path shorter than P, a contradiction.
Any proof of correctness for Dijkstra's Algorithm leverages the optimal substructure problem. The main idea is this: when the algorithm marks a vertex v as visited, v's distance marker is the length of any shortest path from the initial vertex to v.
Before proving Dijkstra's algorithm, define d : V x V -> R+ be the shortest path metric on the graph. That is, for any pair of vertices x and y in the graph, d(x, y) is the length of any shortest x-y path.
Theorem 1: Let G be a connected graph. Dijkstra's algorithm terminates. Let v be the initial vertex used by the algorithm. Upon termination, the distance dist(v, y) computed by the algorithm is equal to d(v, y) for every vertex y in G.
We begin by showing the algorithm terminates.
Claim 2: Dijkstra's algorithm terminates.
Proof: Suppose to the contrary that the algorithm does not terminate. Then the priority queue always has an element. This implies that there is always some unvisited vertex in the graph, contradicting the finiteness of the graph.
Claim 3: Upon termination, the distance dist(v, y) computed by the algorithm is equal to d(v, y) for every vertex y in G.
Proof: The proof is by induction on the number of vertices polled from the priority queue. When no elements have been polled from the priority queue, we have correctly computed dist(v, v) = d(v, v) = 0. Suppose the claim holds true for the first k-1 elements polled from the priority queue. Let x be the kth vertex polled from the priority queue.
Suppose that dist(v, x) > d(v, x). By the algorithm, dist(v, x) is computed using only the previous k marked vertices. Then an unmarked vertex w must be present in any shortest path from v to x. Let P be the v-x path computed by the algorithm. Let P' be a shortest x-v path containing w. Without loss of generality, suppose w is the first unmarked vertex in P'. By Claim 1, the v-w sub-path in P' is a shortest v-w path. It is necessary that d(v, w) <= d(v, x) since w is along a shortest v-x path. It follows that w's predecessor would have visited w and pushed it onto the priority queue. So w would have been polled from the priority queue before x, a contradiction.
It follows that the algorithm correctly computes the lengths of the shortest v-y paths for all vertices y in G. QED.
Theorem 2: Dijkstra's Algorithm runs in O(E log V) time, where E is the number of edges and V is the number of vertices in the graph.
Proof: Suppose we use a heap where the key can be updated as the priority queue. Polling the vertex with the smallest distance marker from the heap takes O(log V) time. For each polled vertex, we must evaluate all of its neighbors. While a vertex can have at most V-1 neighbors, there are E total neighbors to be considered. When evaluating a vertex's neighbor, updating the distance takes O(1) time. However, updating the vertex's position in the heap takes O(log V) time. So the runtime is O(V log V + E log V). Since V is O(E) in the case of a connected graph, we have the runtime is O(E log V). QED.