I’ve just written a script that executes Dijkstra’s algorithm that seeks to find the shortest path tree on a randomly generated graph.
Given a weighted graph G and a vertex s, the single node shortest path problem seeks to find the shortest path from s to every other vertex in this graph such that the sum of the weights of the edges along these paths is minimized. One famous algorithm for this problem is Dijkstra’s Algorithm, which constructs this shortest path tree using techniques of greedy algorithms and dynamic programming.
Dijkstra’s Algorithm works as follows.
- Initially we have an empty path tree T, and assume that the distance to every vertex in the graph has some maximum cost, say infinity, i.e. w(v) = infinity for all v in V.
- Add the node s to the tree, and give the associated path cost a value of zero, i.e. w(s) = 0.
- Find the edge which is adjacent to T that adds the vertex whose cost is minimum, i.e. we look for an e = (u, v) such that u is in T, and v is not in T and w(u) + cost(u, v) < w(v) is minimum. If no such edge exists go to 5.
- Add the corresponding edge and vertex to the tree, and update the weight vector of the vertex v. Go to 3.
- The path tree T now represents the shortest path from the vertex s to all other vertices reachable in the graph G. The weight vector w represents the costs of these paths.
For an example of Dijkstra’s algorithm executed on the Graph with the following adjacency matrix:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 0 | – | – | 2 | 4 | – | – | 20 | – |
| 1 | – | – | – | 11 | 11 | 7 | 5 | – |
| 2 | 2 | – | – | – | 10 | – | 7 | – |
| 3 | 4 | 11 | – | – | – | – | – | 2 |
| 4 | – | 11 | 10 | – | – | – | – | – |
| 5 | – | 7 | – | – | – | – | – | 14 |
| 6 | 20 | 5 | 7 | – | – | – | – | – |
| 7 | – | – | – | 2 | – | 14 | – | – |
Suppose we are interested in discovering the shortest paths from the node 0.
Initially Dijkstra’s algorithm constructs an empty path tree, T = {}.
Because we want to discover the shortest paths from the node 0, our first step will be to add this node to the tree and update the weight vector.
T = {0}
w(0) = 0.
Now we will consider the edges adjacent to T, {(0, 2), (0, 3), and (0, 6)}. Our assumption is that the shortest path of every vertex in T has already been computed correctly and we will seek the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T. The edge that does that currently is (0, 2) since w(0) = 0 and c(0, 2) = 2. We add the node 2 to T and update the weight vector.
T = {0, 2}
w(2) = 2.
The edges adjacent to T are now {(0, 3), (0, 6), (2, 4), (2, 6)}.
The associated path costs are:
w(0) + c(0, 3) = 0 + 4 = 4
w(0) + c(0, 6) = 0 + 20 = 20
w(2) + c(2, 4) = 2 + 10 = 12
w(2) + c(2, 6) = 2 + 7 = 9
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (0, 3). We add the node 3 to T and update the weight vector.
T = {0, 2, 3}
w(3) = 4
The edges adjacent to T are now {(0, 6), (2, 4), (2, 6), (3, 1), (3, 7)}.
The associated path costs are:
w(0) + c(0, 6) = 0 + 20 = 20
w(2) + c(2, 4) = 2 + 10 = 12
w(2) + c(2, 6) = 2 + 7 = 9
w(3) + c(3, 1) = 4 + 11 = 15
w(3) + c(3, 7) = 4 + 2 = 6
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (3, 7). We add the node 7 to T and update the weight vector.
T = {0, 2, 3, 7}
w(7) = 6
The edges adjacent to T are now {(0, 6), (2, 4), (2, 6), (3, 1), (5, 7)}.
The associated path costs are:
w(0) + c(0, 6) = 0 + 20 = 20
w(2) + c(2, 4) = 2 + 10 = 12
w(2) + c(2, 6) = 2 + 7 = 9
w(3) + c(3, 1) = 4 + 11 = 15
w(7) + c(5, 7) = 6 + 14 = 20
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (2, 6). We add the node 6 to T and update the weight vector.
T = {0, 2, 3, 6, 7}
w(6) = 9
The edges adjacent to T are now {(2, 4), (3, 1), (5, 7) (6, 1)}.
The associated path costs are:
w(2) + c(2, 4) = 2 + 10 = 12
w(3) + c(3, 1) = 4 + 11 = 15
w(7) + c(5, 7) = 6 + 14 = 20
w(6) + c(6, 1) = 9 + 5 = 14
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (2, 4). We add the node 4 to T and update the weight vector.
T = {0, 2, 3, 4, 6, 7}
w(4) = 12
The edges adjacent to T are now {(3, 1), (5, 7), (6, 1), (4, 1)}.
The associated path costs are:
w(3) + c(3, 1) = 4 + 11 = 15
w(7) + c(5, 7) = 6 + 14 = 20
w(6) + c(6, 1) = 9 + 5 = 14
w(4) + c(4, 1) = 12 + 11 = 23
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (6, 1). We add the node 1 to T and update the weight vector.
T = {0, 1, 2, 3, 4, 6, 7}
w(1) = 14
The edges adjacent to T are now {(5, 7), (1, 5)}.
The associated path costs are:
w(7) + c(5, 7) = 6 + 14 = 20
w(1) + c(1, 5) = 14 + 7 = 21
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (5, 7). We add the node 5 to T and update the weight vector.
T = {0, 1, 2, 3, 4, 5, 6, 7}
w(5) = 20
Now that T contains all the nodes from the tree, we know the shortest path from node 0 to all other nodes and and have solved the problem. The associated weight vector is w = [0, 14, 2, 4, 12, 20, 9, 6].
To learn more and see more examples, view Dijkstra’s Algorithm at LEARNINGlover.com