Insight 34.13.1.
Dijkstra’s algorithm finds the shortest path from one vertex to all other reachable vertices. If we only care about the shortest path to a specific vertex, we can stop the algorithm once we visit that vertex.
Section 34.13 Dijkstra’s Algorithm
We know that breadth-first search can be used to find the shortest path between two vertices in an unweighted graph. But it will not always find the lowest cost path in a weighted graph. Consider the graph below.
The shortest path from vertex 1 to vertex 5 is not the path with the fewest edges. But breadth first search from vertex 1 would start by exploring 2 and 4. As it explored 2, it would find 5 and determine that the path from 1 to 5 should be
1 -> 4 -> 5 when that path is actually longer (a total weight of 70) than the optimal path 1 -> 2 -> 3 -> 5 (total weight of 60).
The whole point of a weighted graph is that different edges have different costs. If we want to find the most efficient path from one vertex to another, we want to focus on the total cost of the path, not just the number of edges. To find the true shortest path, we need a different algorithm.
Dijkstra’s algorithm is a generalization of breadth-first search that can be used to find the shortest path in a weighted graph. In it, we keep track of the cost to reach each vertex from the start vertex. At each step, we select the vertex with the lowest cost that has not yet been visited. We visit it and check each neighbor. If the cost to reach a neighbor through the current vertex is less than the known cost to reach that neighbor, we update the cost and parent of that neighbor.
Dijkstra(graph, start):
Map parentMap
Map costMap
Map knownMap
costMap[start] = 0
while costMap has a vertex that is not in knownMap:
select lowest cost vertex that is not in knownMap as minCostVertex
knownMap[minCostVertex] = true
for each neighbor in graph.getNeighbors(minCostVertex):
if neighbor not in knownMap:
costThroughVertex = costMap[minCostVertex] + graph.getEdgeWeight(minCostVertex, neighbor)
if (neighbor not in costMap) or (costThroughVertex < costMap[neighbor]):
costMap[neighbor] = costThroughVertex
parentMap[neighbor] = minCostVertex
return parentMap
When the algorithm is finished, we can reconstruct the shortest path to any desired vertex from the parent map that it produced.
The pseudocode contains these two somewhat ugly lines:
...
while not costMap has a vertex that is not in knownMap:
select lowest cost vertex that is not in knownMap as minCostVertex
...
They illustrate one of the key differences between breadth-first search (see Listing 34.6.1) and Dijkstra’s algorithm. BFS uses a first-in first-out queue to decide what to explore next. In contrast, Dijkstra’s algorithm needs to select the vertex with the lowest cost that has not yet been visited. The pseudocode matches the animation below. As you step through the algorithm, observe that every time we need to select the next vertex to visit, it scans through the cost map to find the vertex with the lowest cost that has not yet been visited.
Activity 34.13.1. Dijkstra’s Algorithm.
Pick a vertex to find shortest paths from by entering a value into
Start Vertex and then pressing Run Dijkstra. Then step through the animation.
This animation shows a cost table instead of a priority queue. Each time it needs to select the next vertex to visit, it will scan the cost table to find the vertex with the lowest cost that has not yet been visited. The initial cost for each vertex is shown as INF (infinity)—that corresponds to something that is not yet in the cost map.
Instructions.
When the
> button is highlighted, an animation is prepared to run. Use the Step button to step through the animation one step at a time.
When no animation is in progress, you can use the data controls to start a new animation.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
-
Core Controls.
-
<<: Skip to the beginning of the animation. -
<: Step backwards one step in the animation. -
>: Step forward one step in the animation. -
>>: Skip to the end of the animation. -
Auto Step Speed Set to anything other than off to automatically step through the animation at the selected speed.
-
Zoom Set the zoom level. You can also use Ctrl + Mouse Wheel to zoom in and out.
-
-
Graph Controls.
-
New Graph Randomly generate a new graph with the same settings.
-
Directed Graph Randomly generate a new directed graph.
-
Undirected Graph Randomly generate a new undirected graph.
-
Small Graph Randomly generate a graph with 8 vertices.
-
Large Graph Randomly generate a graph with 19 vertices.
-
Logical Representation Display current graph’s logical representation.
-
Adjacency List Representation Display current graph’s adjacency list representation.
-
Adjacency Matrix Representation Display current graph’s adjacency matrix representation.
-
In an actual implementation, those lines would need to be replaced with some loop logic to pick the right vertex. The cost to scan through all vertices in the known map is \(O(n)\text{,}\) where n is the number of vertices. However, we could use a priority queue (min-heap) to store the vertices by their cost. If we used a priority queue, we could find and remove the lowest cost vertex in logarithmic time instead of linear time. However, that would make increasing the cost of a vertex more complex, since we would have to update the priority queue to reflect the new cost.
Checkpoint 34.13.1.
Which are true about Dijkstra’s algorithm?
- It works on weighted graphs
- It calculates the cost of a vertex B being considered from vertex A as the weight of the edge connecting them plus the cost from the starting vertex to vertex A
- It finds the shortest path from one vertex to all other reachable vertices
- It finds the shortest path from one vertex to a single other vertices
- the cost of a vertex B being considered from vertex A as the weight of the edge connecting them
You have attempted of activities on this page.
