29
30
31
R
32
𝒂 𝑪
33
34
(a) (b)
Figure 1: A network with a root and a network with an absorbing (negative) circuit.
35
36
𝒂 𝑪
37
38
39
-
40
Bellman’s algorithm
Input:Let R=(X,A,l) be an acyclic network, with r as the initial
vertex.
Output: The shortest paths from the root r to all the vertices in R,
with their lengths.
S{r}; π(r) 0; xV, x≠r, π(x)+; Arc ;
For every vertex x such that N-(x) S do
π(x)minyN-(x)[π(y)+l(yx)]=π(z)+l(zx){z is the selected vertex}
SS{x}; ArcArc {zx};
EndFor
If S = X Then
The set Arc represents the arcs of the shortest paths from r to x,
x V.
Else
The vertex r is not a root, there is no shortest path in this
case.
EndIf
41
Figure 2 : Weighted graph (network) without circuit and with negative weights.
42
Initialization : S{s}; π(s) 0; xV, x≠s, π(x)+;
Arc ;
x = 1 : π(1) π(s)+l(sx)]=1 ; SS{1}; ArcArc{s1};
x = 2 : π(2) min[π(s)+l(s2), π(1)+l(12]=π(1)+l(12)=2 ;
SS{2}; ArcArc{12};
x = 4 : π(4) π(2)+l(24)=3 ; SS{4}; ArcArc{24};
x = 3 : π(3) π(1)+l(13) =3 ; SS{3}; ArcArc{13};
x=5: π(5)min[π(1)+l(15),π(2)+l(25),π(3)+l(35),π(4)+l(45)]=
π(1)+l(15)=-1 ; SS{5}; ArcArc{15};
x=6:π(6)min[π(3)+l(36),π(5)+l(56),π(4)+l(46)]=π(3)+l(36)=6;
SS{6}; ArcArc{36};
S = X End of the algorithm.
43
Figure 3 : The shortest paths from s to all other vertices of R.
44
45
46
Dijkstra's Algorithm
Input : R=(X,A,l) A network with positive edge lengths,r
as the initial vertex.
Output: The shortest paths from the root r to all
vertices in R, along with their lengths.
S{r}; π(r) 0; xV, x≠r, π(x)+; Arc(x) , xV;
While S ≠ V do
For every vertex y that is a successor of x do
If π(x)+l(xy)< π(y) then
π(y) π(x)+l(xy) ;
Arc(y){xy} ;
EndIf
EndFor
Choose a vertex zV\S such that π(z)minxV\S(π(x)) ;
47
If π(z)=+ then
Termination of the algorithm: the vertex r is not a
root, and there is no solution.
else
S S{z} ; xZ ;
EndIf
EndWhile
48
Figure 4 : Weighted graph (network) with all positive weights.
49
Initialization: S{r}; π(r) 0; xV, x≠r, π(x)+;
Arc(x) ;
Iteration1 x=r
Y=1 :π(r)+l(r1)=2<π(1)=+π(1)π(r)+l(r1)=0+2=2;
Arc(1){r1};
Y=2 :π(r)+l(r2)=8<π(2)=+ π(2)π(r)+l(r2)=0+8=8;
Arc(2){r2};
Choose a vertex z : z1 ; S S{1} ; x1 ;
Iteration2 x=1
Y=3 :π(1)+l(13)=3<π(3)=+ π(3)π(1)+l(13)=1+2=3;
Arc(3){13};
Y=2 :π(1)+l(12)=7<π(2)=8 π(2)π(1)+l(12)=2+5=7;
Arc(2){12};
Choose a vertex z : z3 ; S S{3} ; x3 ;
50
Iteration3 x=3
Y=2 :π(3)+l(32)=5<π(2)=7 π(2)π(3)+l(32)=3+2=5;
Arc(2){32};
Y=4 :π(3)+l(34)=7<π(4)=+ π(4)π(3)+l(34)=3+4=7;
Arc(4){34};
Y=5 :π(3)+l(35)=4<π(5)=+ π(5)π(3)+l(35)=3+1=4;
Arc(5){35};
Choose a vertex z : z5 ; S S{5} ; x5;
Vertex 5 has no successors.
Choose a vertex z : z2 ; S S{2} ; x2;
Iteration4 x=2
Y=4 :π(2)+l(24)=6<π(4)=7 π(4)π(2)+l(24)=5+1=6;
Arc(4){24};
Choose a vertex z : z4 ; S S{4} ; x4;
S=V End of the algorithm.
51
Figure 5 : The shortest paths from r to all other vertices in the network R.
