   Next:7.2.2 Dynamic Programming AlgorithmUp:7.2 Shortest Paths ProblemPrevious:7.2 Shortest Paths Problem

7.2.1 Single Source Shortest Paths Problem: Dijkstra's Algorithm

REF.
E.W. Dijkstra. A note on two problems in connection with graphs. Numerische Mathematik, Volume 1, pp. 269-271, 1959.
• Greedy algorithm
• It works by maintaining a set S of special'' vertices whose shortest distance from the source is already known. At each step, a non-special'' vertex is absorbed into S.
• The absorption of an element of V - S into S is done by a greedy strategy.
• The following provides the steps of the algorithm.
Let
 V = {1, 2,..., n} and source = 1 (7.1) C[i, j] = {

S= { 1 };

for (i = 2; i < n; i++)

D[i] = C[1,i];

for (i=1; i < = n-1; i++)

{

choose a vertex w V-S such that D[w] is a minimum;

S = S {w };

for each vertex v V-S

D[v] = min (D[v], D[w] + C[w, v])

}

}

• The above algorithm gives the costs of the shortest paths from source vertex to every other vertex.
• The actual shortest paths can also be constructed by modifying the above algorithm.
Theorem: Dijkstra's algorithm finds the shortest paths from a single source to all other nodes of a weighted digraph with positive weights.

Proof: Let V = 1, 2, ..., n and 1 be the source vertex. We use mathematical induction to show that

(a)
If a node i 1) S, then D[i] gives the length of the shortest path from the source to i.
(b)
if a node i S, then D[i] gives the length of the shortest special path from the source to i.
Basis: Initially S = 1 and hence (a) is vacuously true. For i S, the only special path from the source is the direct edge if present from source to i and D is initialized accordingly. Hence (b) is also true.

Induction for condition (a)

• The induction hypothesis is that both (a) and (b) hold just before we add a new vertex v to S.
• For every node already in S before adding v, nothing changes, so condition (a) is still true.
• We have to only show (a) for v which is just added to S.

• • Before adding it to S, we must check that D[v] gives the length of the shortest path from source to v. By the induction hypothesis, D[v] certainly gives the length of the shortest special path. We therefore have to verify that the shortest path from the source to v does not pass through any nodes that do not belong to S.
• Suppose to the contrary. That is, suppose that when we follow the shortest path from source to v, we encounter nodes not belonging to S. Let x be the first such node encountered (see Figure 7.4 ). The initial segment of the path from source to x is a special path and by part (b) of the induction hypothesis, the length of this path is D[x]. Since edge weights are no-negative, the total distance to v via x is greater than or equal to D[x]. However since the algorithm has chosen v ahead of x, D[x] D[v]. Thus the path via x cannot be shorter than the shortest special path leading to v.
Induction step for condition (b): Let  v and  S. When v is added to S, these are two possibilities for the shortest special path from source to w:
1.
It remains as before
2.
It now passes through v ( and possibly other nodes in S)
In the first case, there is nothing to prove. In the second case, let y be the last node of S visited before arriving at w. The length of such a path is D[y] + C[y,w].
• At first glance, to compute the new value of d[w], it looks as if we should compare the old value of D[w] with D[y] + C[y,w] for every y S (including v)
• This comparison was however made for all y S except v, when y was added to S in the algorithm. Thus the new value of D[w] can be computed simply by comparing the old value with D[v] + C[v,w]. This the algorithm does.
When the algorithm stops, all the nodes but one are in S and it is clear that the vector D, D, ..., D[n]) contains the lengths of the shortest paths from source to respective vertices.

Example: Consider the digraph in Figure 7.5. Initially:

S = {1}  D = 10  D = D = 30  D = 100

Iteration 1

Select w = 2, so that S = {1, 2}

 D = min( , D + C[2, 3]) = 60 (7.2) D = min(30, D + C[2, 4]) = 30 (7.3) D = min(100, D + C[2, 5]) = 100

Iteration 2

Select w = 4, so that S = {1, 2, 4}

 D = min(60, D + C[4, 3]) = 50 (7.4) D = min(100, D + C[4, 5]) = 90

Iteration 3

Select w = 3, so that S = {1, 2, 4, 3}

 D = min(90, D + C[3, 5]) = 60

Iteration 4

Select w = 5, so that S = {1, 2, 4, 3, 5}

 D = 10 (7.5) D = 50 (7.6) D = 30 (7.7) D = 60

Complexity of Dijkstra's Algorithm

With adjacency matrix representation, the running time is O(n2) By using an adjacency list representation and a partially ordered tree data structure for organizing the set V - S, the complexity can be shown to be

O(elog n)
where e is the number of edges and n is the number of vertices in the digraph.   Next:7.2.2 Dynamic Programming AlgorithmUp:7.2 Shortest Paths ProblemPrevious:7.2 Shortest Paths Problem
eEL,CSA_Dept,IISc,Bangalore