Objectives
- To understand how the same "open-list-closed-list" method used for depth- and breadth first search can be refined into an algorithm (due to Dijkstra) to find the shortest path between two vertices
- To see what effect this refinement has on the efficiency of the algorithm
Preparation
As a pre-requisite for this lab activity, you should be familiar with the definition of a graph as a collection of vertices (also called nodes) and edges connecting them. Additionally you should be familiar with the two implementation strategies for a graph, namely, an adjacency matrix representation and adjacency lists. Finally you should be familiar with the general algorithm that is used to implement depth- and breadth-first graph traversals in terms of an open list and a closed list. To review this algorithm see the
To prepare for the actual lab activity, read the description of of Dijkstra's algorithm given below and compare it with your textbook, if available.
Dijkstra's Shortest Path Algorithm
Recall the general algorithm we used to control both the depth- and breadth-first traversals of a graph.
/* initialization */
SomeKindOfList openList = { startVertex }
/* loop */
while ( closedNodes != numberOfNodes && !openList.empty())
{
closingVertex = openList.remove(); /* Whatever removal rule is used for the list */
increment the number of closedNodes;
for each non-closed vertex with an edge from closingVertex
{
openList.insert( vertex ); /* Whatever insertion rule is used for the list */
}
}
Both the depth- and breadth-first traversals may be used to "explore" vertices in a graph, but they do so blindly, that is, without any real purpose guiding the order in which they add nodes to the open list.
Dijkstra's algorithm explores vertices in a weighted graph with a very specific goal in mind, namely, finding the shortest path (also known as the least-cost path) from one designated start vertex to all other vertices in the graph. For example, suppose that we want to find the shortest path from vertex C to all other vertices in the graph of Figure 1.
 |
Figure 1
To do this, the algorithm borrows the basic structure of the depth- and breadth-first traversals but alters it in two significant respects:
- For each vertex in the graph, it keeps track of that vertex's cost and its shortest-path-predecessor. At any given stage of the algorithm, the cost of a vertex is the length of the shortest path that has been explored so far from the start vertex to that given vertex. Initially the cost of all vertices except the start vertex is set to some "infinitely large value". The shortest-path-predecessor of the vertex is the vertex immediately preceding the given vertex on the shortest path from the start vertex to the vertex.
- The open list is organized as a priority queue in which a vertex's priority is given by its cost – the smaller the cost, the greater the priority of the vertex, that is, the earlier it is removed from the priority queue. As a vertex is removed from the open list and added to the closed vertices, all non-closed vertices adjacent to that vertex have their cost updated to see if a new, lower-cost path has been found to that vertex.
When a vertex is moved from the open list to the list of closed vertices in Dijkstra's algorithm, that is the point at which we are sure we have found the shortest path to it. Prior to being closed, the path to a vertex on the open list is the best path we have found so far, but that path is not yet guaranteed to be the absolute shortest path among all possible paths.
The pseudocode below takes these refinements into account and expresses Dijkstra's shortest path algorithm. Big is used to represent an "infinitely large value" in the cost array and No to represent "no predecessor" in the predecessor array.
Pseudo-code for Dijkstra's Algorithm
/* initialization */
PriorityQueue openList = { startVertex }
array cost = { Big, Big, Big, ... }
array pred = { No, No, No, ... }
cost[startVertex] = 0;
/* loop */
while ( !openList.empty()) {
closingVertex = vertex in openList with minimum value in cost[];
remove closingVertex from openList;
for each non-closed vertex with an edge from closingVertex {
if ( cost[vertex] > cost[closingVertex] + edgeWeight ) {
cost[vertex] = cost[closingVertex] + edgeWeight;
pred[vertex] = closingVertex;
put vertex into openList;
}
}
}
Example Trace of Dijkstra's Algorithm
The following trace of Dijkstra's shortest path algorithm for the graph of Figure 1 works under the assumption that, if two vertices in the open list tie for the least cost, the vertex that comes first in alphabetical order will be removed from the list. Note how the updating of the cost and pred arrays occurs. For example, on that iteration of the algorithm where B is closed, vertex F, whose cost and pred vales had been 10 and D respectively, has these values updated to 6 and B. This is because the algorithm "discovers" a shorter path to F than the path it had previously thought was best. In particular, it discovers it is cheaper to get to F by going through B instead of through D.
After all vertices have been closed, the shortest path from C to any other vertex may be obtained by working backwards through the predecessor array. For example, to recover the shortest path from C to E, we work backwards E G F B D C for a total path length of 10.
| Vertex closed is ... | Open list | -A- | -B- | -C- | -D- | -E- | -F- | -G- | -H- | -I- | |
| C | Big | Big | 0 | Big | Big | Big | Big | Big | Big | Cost | |
| No | No | No | No | No | No | No | No | No | Pred | ||
| C | D,I | Big | Big | 0 | 2 | Big | Big | Big | Big | 4 | Cost |
| No | No | No | C | No | No | No | No | C | Pred | ||
| D | B,F,I | Big | 4 | 0 | 2 | Big | 10 | Big | Big | 4 | Cost |
| No | D | No | C | No | D | No | No | C | Pred | ||
| B | F,I | Big | 4 | 0 | 2 | Big | 6 | Big | Big | 4 | Cost |
| No | D | No | C | No | B | No | No | C | Pred | ||
| I | E,F,H | Big | 4 | 0 | 2 | 11 | 6 | Big | 5 | 4 | Cost |
| No | D | No | C | I | B | No | I | C | Pred | ||
| H | A,E,F,G | 8 | 4 | 0 | 2 | 11 | 6 | 13 | 5 | 4 | Cost |
| H | D | No | C | I | B | H | I | C | Pred | ||
| F | A,E,G | 8 | 4 | 0 | 2 | 11 | 6 | 7 | 5 | 4 | Cost |
| H | D | No | C | I | B | F | I | C | Pred | ||
| G | A,E | 8 | 4 | 0 | 2 | 10 | 6 | 7 | 5 | 4 | Cost |
| H | D | No | C | G | B | F | I | C | Pred | ||
| A | E | 8 | 4 | 0 | 2 | 10 | 6 | 7 | 5 | 4 | Cost |
| H | D | No | C | G | B | F | I | C | Pred | ||
| E | 8 | 4 | 0 | 2 | 10 | 6 | 7 | 5 | 4 | Cost | |
| H | D | No | C | G | B | F | I | C | Pred |
Efficiency
As is the case for any graph algorithm, the efficiency of Dijkstra's algorithm is dependent upon whether the graph is implemented with an adjacency matrix or adjacency lists. The listing of the algorithm below has been annotated with four comments that we will use to discuss the efficiency – "OUTER LOOP", "INNER LOOP", "REMOVAL FROM OPEN LIST", "INSERTION INTO OPEN LIST".
/* initialization */
PriorityQueue openList = { startVertex }
array cost = { Big, Big, Big, ... }
array pred = { No, No, No, ... }
cost[startVertex] = 0;
/* loop */
while ( !openList.empty()) { /* OUTER LOOP */
/* REMOVAL FROM OPEN LIST */
closingVertex = vertex in openList with minimum value in cost[];
remove closingVertex from openList;
/* INNER LOOP */
for each non-closed vertex with an edge from closingVertex {
if ( cost[vertex] > cost[closingVertex] + edgeWeight ) {
cost[vertex] = cost[closingVertex] + edgeWeight;
pred[vertex] = closingVertex;
/* INSERTION INTO OPEN LIST */
put vertex into openList;
}
}
}
If the open list is implemented as efficiently as possible (using a heap for the priority queue), the insertion into and removal from the open list will be O(log V) where V is the number of vertices in the graph. If an adjacency matrix is used to implement the graph, then both the outer and inner loops are O(V), and hence the efficiency of the resulting algorithm is O(v
Compare with Your Textbook
Algorithms can appear different but still be basically identical. Compare our pseudo code with the description in your textbook (if available). Then try to answer the following questions:
- Does your textbook use the same "closed" and "open" terminology that we do here? If not, what alternate terminology does it use?
- Does you textbook's description of the algorithm explicitly mention the use of a priority queue to select the next node to be closed? If not, what alternate method does it use to describe how a vertex is selected to be closed?
Exploring the Algorithm's Dynamic Behavior
Explore the Algorithm within JHAVÉ or TRAKLA2
You can explore the algorithm's dynamic behavior using the algorithm visualization environment JHAVÉ. If you have not worked with JHAVÉ before, please take the time to first.
You can also "visually simulate" the algorithm's dynamic behavior using the TRAKLA2/Matrix environment developed at the Helsinki University of Technology – just follow this
Step through the algorithm using either visualization environment. When you have reached the point where you are correctly answering the questions posed by JHAVÉ or matching the model simulation provided by TRAKLA2, try working on the Exercises below.
Exercises
- Trace the action of Dijkstra's shortest path algorithm on the graph below, assuming that the start vertex is D.
Figure 2
Figure 2 
- Explain how the priority queue in Dijkstra's shortest path algorithm can be implemented to insure that both insertions and removals occur in O(log V) time. Note: This is not as easy as a "normal" priority queue because an item's priority may change while it is in the queue as the algorithm discovers a shorter path to it through a vertex that has just been closed.
- Suppose that we:
Will the algorithm then find the longest path from the start vertex to all other vertices? Explain why or give an example to show that it won't.
- Initialize the cost array to an "infinitely large negative number"
- Organize the priority queue to remove a vertex with the greatest cost entry instead of the least
- Change the
Designing Data Sets
Creating input for an algorithm is an effective way to demonstrate you understanding of the algorithm's behavior.
- A key idea in the shortest path algorithm is that a vertex's cost may be updated as we discover shorter paths to that vertex through vertices that are being closed. Hence, as we saw in our example trace, a vertex's cost may often change during the course of the algorithm. Design data sets such that:
- For all vertices, after their cost changes from Big to some finite value, their cost never changes again.
- For all vertices except two, their cost changes at least one more time after its initial change from Big to some finite value.
- Construct an example of a graph with negative edge weights in which Dijkstra's shortest path algorithm fails to work. Hence we conclude that a precondition for Dijkstra's algorithm is that the graph edges have non-negative weights.
Modifying the Algorithm
Create Your Own Visualization
Using your own source code, presentation software, or manually produced drawings, create your own visualization of the shortest path algorithm.
Presentation
Develop a ten minute presentation on the shortest path algorithm that uses the visualization you developed above to help you explain the nuances of the algorithm.
