Directed graph G= (V,E)
Path from u to v
Before: length of path = number of edges
Cost C: E -> R+
Length(or cost) of path: sum of costs of edges on path
| 1--2: | 1,3,2 | 25 |
| 1--3: | 1,3 | 15 |
| 1--4: | 1,4 | 20 |
| 1--5: | 1,3,2,5 | 40 |
Shortest path from a single source node to all other nodes.
Figure 4.15 (page 242)
If d2 < d1, then P1 is not a shortest path from v0 to v.
Lemma: If v0, v1, v2..., vk, P is a shortest path from v0 to v, then v0,
v1,..., vi is a shortest path from v0 to vi for all 1 < i <
k (shortest total is shortest all along way)
Also, dist (v0,v1) < dist (v0,v2) < .... < dist
(v0,v)
Scan graph for nodes within a given radius of v0
Thus first find shortest path for each intermittent stop possible. Keep
increasing radius.
S = set of nodes for which shortest paths have been computed.
The next node to be included must be the one with the shortest path from v0
among all nodes not in S.
Let this node be v.
All intermediate nodes on the shortest path from v0 to v must belong to S.
S -- set of nodes "closest" to v0 for which shortest paths have already been
computed.
v <- next node to be included in S.
Greedy: v is that node in V-S closest to v0
Dist (u)<-- cost of shortest path from v0 to u passing only through nodes in
S. (for all u
Once v is included in S, dist's will have to be corrected. So each time we put
a vertex v in, we have to check all vertices v is connected to, and increment
Dist(u)
Dijkstra's Shortest Path algorithm:
Also see another form and this code traced
P1: shortest path from v0 to v.
Code in book on page 245 has constant for initial v.
Algorithm path (v0, G)
{
Time: O(n2)
// initialize
S = {v0}
S'= V - S
for all u in S' do
dist(u) = cost (v0,u)
for i = 1 to n - 1
// determine n-1 paths from v v = node in S' with least dist(u)
}
S = S U {v}
S' = S' - {v}
for all u in S' adjacent to v do
dist(u) = min(dist (u), dist (v) + cost (v, u))
!