Johnson's algorithm

Algorithm to find the All-Pairs Shortest Paths in a Weighted Directed Graph.

1. Johnson’s Algorithm for Sparse Graph
Dr.Kiran K
Assistant Professor
Department of CSE
UVCE
Bengaluru, India.

2. Introduction
•Johnson’salgorithmfindsShortestPathsbetweenAllPairsofverticesinagraph.
•Thealgorithmeitherreturnsamatrixofshortest-pathweightsforallpairsofverticesor
reportsthattheinputgraphcontainsanegative-weightcycle.
•ItusesassubroutinesbothDijkstra’salgorithmandtheBellman-Fordalgorithm.
•ItusesatechniquecalledReweighting.
•IfalledgeweightswinagraphG=(V,E)arenonnegative,shortestpathsbetweenallpairs
ofverticesisfoundbyrunningDijkstra’salgorithmoncefromeachvertex.
•Thealgorithmcomputesanewsetofnonnegativeedgeweightsŵ.
•ŵmustsatisfytwoimportantproperties:
1.Forallpairsofvertices(u,v)єV,apathpisashortestpathfromutovusingweight
functionwifandonlyifpisalsoashortestpathfromutovusingweightfunctionŵ.
2.Foralledges(u,v),thenewweightŵ(u,v)isnonnegative.

3. Preserving Shortest Paths by Reweighting
δ:shortest-pathweightsderivedfromweightfunctionw
:shortest-pathweightsderivedfromweightfunctionŵ
Lemma:ReweightingDoesnotchangeShortestPaths
GivenaWeighted,DirectedGraphG=(V,E)withweightfunctionw:E→R,
Leth:V→RbeanyfunctionmappingVerticestoRealnumbers.
Foreachedge(u,v)єE,defineŵ(u,v)=w(u,v)+h(u)–h(v),where
h(v)=δ(s,v).
Letp=<v
0,v
1,..,v
k>beanypathfromvertexv
0tovertexv
k.Thenpisashortest
pathfromv
0tov
kwithweightfunctionwifandonlyifitisashortestpathwith
weightfunctionŵ.Thatis,w(p)=δ(v
0,v
k)ifandonlyifŵ(p)=(v
0,v
k).
Furthermore,Ghasanegative-weightcycleusingweightfunctionwifandonlyifG
hasanegative-weightcycleusingweightfunctionŵ.

4. Preserving Shortest Paths by Reweighting…
Proof:
(1)w(p)=δ(v
0,v
k)ifandonlyifŵ(p)=(v
0,v
k).
(SumTelescope)
(L1)

5. Preserving Shortest Paths by Reweighting…
(L1)→Anypathpfromv
0tov
khasŵ(p)=w(p)+h(v
0)–h(v
k)(L2)
h(v
0)andh(v
k)donotdependonthepath. (L3)
(L2)and(L3)→ifonepathfromv
0tov
kisshorterthananotherusingweight
functionw,thenitisalsoshorterusingŵ. (L4)
(L4)→w(p)=δ(v
0,v
k)ifandonlyifŵ(p)=(v
0,v
k).
(2)Ghasanegative-weightcycleusingweightfunctionwifandonlyifGhasa
negative-weightcycleusingweightfunctionŵ.
Letc=<v
0,v
1,..,v
k>beacyclewherev
0=v
k
(L2)→ŵ(c)=w(c)+h(v
0)–h(v
k) (L5)
v
0=v
kin(L5)→ŵ(c)=w(c) (L6)
(L6)→chasnegativeweightusingwifandonlyifithasnegativeweightusingŵ.

6. Producing Nonnegative Weights by Reweighting
•GivenaWeighted,DirectedGraphG=(V,E)withweightfunctionw:E→R,
constructanewGraphGʹ=(Vʹ,Eʹ)whereVʹ=VU{s}forsomenewvertex
sȼVandEʹ=EU{(s,v):vєV}.
•Thenonnegativeweightsŵ(u,v)arecomputedasfollows:
1.Extendtheweightfunctionwsothatw(s,v)=0forallvєV.
2.Computeh(v)=δ(s,v)forallvєVʹ.
3.Computeŵ(u,v)=w(u,v)+h(u)–h(v)≥0.
h(v)≤h(u)+w(u,v) (TriangleInequality) (3.1)
ŵ(u,v)=w(u,v)+h(u)–h(v)(Lemma) (3.2)
(3.1)and(3.2)→ŵ(u,v)=w(u,v)+h(u)–h(v)≥0.

7. Producing Nonnegative Weights by Reweighting…
1.w(s,v)=0forallvєV.
Fig (a): Graph G
Fig (b): Graph G ʹ

8. Producing Nonnegative Weights by Reweighting…
2.h(v)=δ(s,v)forallvєVʹ (J1)
δ(s,v)iscomputedusingBellman-FordAlgorithm
•Theedgesarerelaxedinthefollowingorder:
(0,1);(0,2);(0,3);(0,4);(0,5);(1,2);(1,3);(1,5);(2,4);(2,5);(3,2);
(4,1);(4,3);(5,4);
•TheBellman-FordAlgorithmrunsfor5passessincethereare6verticesinthe
graphGʹ
•Attheendof5
th
pass,δ(s,v),theshortestpathsfromstoalltheverticesvєVʹ
wouldbecomputedifGʹdoesnotconsistanegativecycle.

9. Producing Nonnegative Weights by Reweighting…
Relax (1, 5): 5.d= min (5.d, 1.d+ w(1, 5)) = (0, 0+ (-4)) = -4
Relax (2, 4): 4.d= min (4.d, 2.d+ w(2, 4)) = (0, 0+ 1) = 0
Relax (2, 5): 5.d= min (5.d, 2.d+ w(2, 5)) = (-4, 0+ 7) = -4
Relax (3, 2): 2.d= min (2.d, 3.d+ w(3, 2)) = (0, 0+ 4) = 0
Relax (4, 1): 1.d= min (1.d, 4.d+ w(4, 1)) = (0, 0+ 2) = 0
Relax (4, 3): 3.d = min (3.d, 4.d+ w(4, 3)) = (0, 0+ -5) = -5
Relax (5, 4): 4.d = min (4.d, 5.d+ w(5, 4)) = (0, (-4) + 6) = 0
Relax (0, 1): 1.d= min (1.d, 0.d+ w(0, 1)) = (ꝏ, 0 + 0) = 0
Relax (0, 2): 2.d= min (2.d, 0.d+ w(0, 2)) = (ꝏ, 0 + 0) = 0
Relax (0, 3): 3.d= min (3.d, 0.d+ w(0, 3)) = (ꝏ, 0 + 0) = 0
Relax (0, 4): 4.d= min (4.d, 0.d+ w(0, 4)) = (ꝏ, 0 + 0) = 0
Relax (0, 5): 5.d= min (5.d, 0.d+ w(0, 5)) = (ꝏ, 0 + 0) = 0
Relax (1, 2): 2.d = min (2.d, 1.d+ w(1, 2)) = (0, 0+ 3) = 0
Relax (1, 3): 3.d = min (3.d, 1.d+ w(1, 3)) = (0, 0+ 8) = 0
ꝏ
ꝏ ꝏ
ꝏꝏ
0
-4 0
-50

10. Producing Nonnegative Weights by Reweighting…
Relax (1, 5): 5.d= min (5.d, 1.d+ w(1, 5)) = (-4, 0+ (-4)) = -4
Relax (2, 4): 4.d= min (4.d, 2.d+ w(2, 4)) = (0, 0+ 1) = 0
Relax (2, 5): 5.d= min (5.d, 2.d+ w(2, 5)) = (-4, 0+ 7) = -4
Relax (3, 2): 2.d= min (2.d, 3.d+ w(3, 2)) = (0, (-5) + 4) = -1
Relax (4, 1): 1.d= min (1.d, 4.d+ w(4, 1)) = (0, 0+ 2) = 0
Relax (4, 3): 3.d = min (3.d, 4.d+ w(4, 3)) = (-5, 0+ -5) = -5
Relax (5, 4): 4.d = min (4.d, 5.d+ w(5, 4)) = (0, (-4) + 6) = 0
Relax (0, 1): 1.d= min (1.d, 0.d+ w(0, 1)) = (0, 0 + 0) = 0
Relax (0, 2): 2.d= min (2.d, 0.d+ w(0, 2)) = (0, 0 + 0) = 0
Relax (0, 3): 3.d= min (3.d, 0.d+ w(0, 3)) = (-5, 0 + 0) = -5
Relax (0, 4): 4.d= min (4.d, 0.d+ w(0, 4)) = (0, 0 + 0) = 0
Relax (0, 5): 5.d= min (5.d, 0.d+ w(0, 5)) = (-4, 0 + 0) = -4
Relax (1, 2): 2.d = min (2.d, 1.d+ w(1, 2)) = (0, 0+ 3) = 0
Relax (1, 3): 3.d = min (3.d, 1.d+ w(1, 3)) = (-5, 0 + 8) = -5
0
-4 0
-50
-1
-4 0
-50

11. Producing Nonnegative Weights by Reweighting…
Relax (1, 5): 5.d= min (5.d, 1.d+ w(1, 5)) = (-4, 0+ (-4)) = -4
Relax (2, 4): 4.d= min (4.d, 2.d+ w(2, 4)) = (-1, 0+ 1) = -1
Relax (2, 5): 5.d= min (5.d, 2.d+ w(2, 5)) = (-4, (-1) + 7) = -4
Relax (3, 2): 2.d= min (2.d, 3.d+ w(3, 2)) = (-1, (-5) + 4) = -1
Relax (4, 1): 1.d= min (1.d, 4.d+ w(4, 1)) = (0, 0+ 2) = 0
Relax (4, 3): 3.d = min (3.d, 4.d+ w(4, 3)) = (-5, 0+ (-5)) = -5
Relax (5, 4): 4.d = min (4.d, 5.d+ w(5, 4)) = (0, (-4) + 6) = 0
Relax (0, 1): 1.d= min (1.d, 0.d+ w(0, 1)) = (0, 0 + 0) = 0
Relax (0, 2): 2.d= min (2.d, 0.d+ w(0, 2)) = (-1, 0 + 0) = -1
Relax (0, 3): 3.d= min (3.d, 0.d+ w(0, 3)) = (-5, 0 + 0) = -5
Relax (0, 4): 4.d= min (4.d, 0.d+ w(0, 4)) = (0, 0 + 0) = 0
Relax (0, 5): 5.d= min (5.d, 0.d+ w(0, 5)) = (-4, 0 + 0) = -4
Relax (1, 2): 2.d = min (2.d, 1.d+ w(1, 2)) = (-1, 0+ 3) = 0
Relax (1, 3): 3.d = min (3.d, 1.d+ w(1, 3)) = (-5, 0 + 8) = -5
-1
-4 0
-50
-1
-4 0
-50

12. Producing Nonnegative Weights by Reweighting…
Relax (1, 5): 5.d= min (5.d, 1.d+ w(1, 5)) = (-4, 0+ (-4)) = -4
Relax (2, 4): 4.d= min (4.d, 2.d+ w(2, 4)) = (-1, 0+ 1) = -1
Relax (2, 5): 5.d= min (5.d, 2.d+ w(2, 5)) = (-4, (-1) + 7) = -4
Relax (3, 2): 2.d= min (2.d, 3.d+ w(3, 2)) = (-1, (-5) + 4) = -1
Relax (4, 1): 1.d= min (1.d, 4.d+ w(4, 1)) = (0, 0+ 2) = 0
Relax (4, 3): 3.d = min (3.d, 4.d+ w(4, 3)) = (-5, 0+ (-5)) = -5
Relax (5, 4): 4.d = min (4.d, 5.d+ w(5, 4)) = (0, (-4) + 6) = 0
Relax (0, 1): 1.d= min (1.d, 0.d+ w(0, 1)) = (0, 0 + 0) = 0
Relax (0, 2): 2.d= min (2.d, 0.d+ w(0, 2)) = (-1, 0 + 0) = -1
Relax (0, 3): 3.d= min (3.d, 0.d+ w(0, 3)) = (-5, 0 + 0) = -5
Relax (0, 4): 4.d= min (4.d, 0.d+ w(0, 4)) = (0, 0 + 0) = 0
Relax (0, 5): 5.d= min (5.d, 0.d+ w(0, 5)) = (-4, 0 + 0) = -4
Relax (1, 2): 2.d = min (2.d, 1.d+ w(1, 2)) = (-1, 0+ 3) = 0
Relax (1, 3): 3.d = min (3.d, 1.d+ w(1, 3)) = (-5, 0 + 8) = -5
-1
-4 0
-50
-1
-4 0
-50

13. Producing Nonnegative Weights by Reweighting…
Relax (1, 5): 5.d= min (5.d, 1.d+ w(1, 5)) = (-4, 0+ (-4)) = -4
Relax (2, 4): 4.d= min (4.d, 2.d+ w(2, 4)) = (-1, 0+ 1) = -1
Relax (2, 5): 5.d= min (5.d, 2.d+ w(2, 5)) = (-4, (-1) + 7) = -4
Relax (3, 2): 2.d= min (2.d, 3.d+ w(3, 2)) = (-1, (-5) + 4) = -1
Relax (4, 1): 1.d= min (1.d, 4.d+ w(4, 1)) = (0, 0+ 2) = 0
Relax (4, 3): 3.d = min (3.d, 4.d+ w(4, 3)) = (-5, 0+ (-5)) = -5
Relax (5, 4): 4.d = min (4.d, 5.d+ w(5, 4)) = (0, (-4) + 6) = 0
Relax (0, 1): 1.d= min (1.d, 0.d+ w(0, 1)) = (0, 0 + 0) = 0
Relax (0, 2): 2.d= min (2.d, 0.d+ w(0, 2)) = (-1, 0 + 0) = -1
Relax (0, 3): 3.d= min (3.d, 0.d+ w(0, 3)) = (-5, 0 + 0) = -5
Relax (0, 4): 4.d= min (4.d, 0.d+ w(0, 4)) = (0, 0 + 0) = 0
Relax (0, 5): 5.d= min (5.d, 0.d+ w(0, 5)) = (-4, 0 + 0) = -4
Relax (1, 2): 2.d = min (2.d, 1.d+ w(1, 2)) = (-1, 0+ 3) = 0
Relax (1, 3): 3.d = min (3.d, 1.d+ w(1, 3)) = (-5, 0 + 8) = -5
-1
-4 0
-50
-1
-4 0
-50

14. Producing Nonnegative Weights by Reweighting…
Fig(c):h(v)computedforGʹofFig(b)
Vertex, v h(v)
1 0
2 -1
3 -5
4 0
5 -4

15. 3.ŵ(u,v)=w(u,v)+h(u)–h(v)≥0
ŵ(1,2)=w(1,2)+h(1)–h(2)=3+0+1=4
ŵ(1,3)=w(1,3)+h(1)–h(3)=8+0+5=13
ŵ(4,1)=w(4,1)+h(4)–h(1)=2+0-0=2
ŵ(1,5)=w(1,5)+h(1)–h(5)=-4+0+4=0
ŵ(2,5)=w(2,5)+h(2)–h(5)=7-1+4=10
Fig(c):h(v)computedforG'
Producing Nonnegative Weights by Reweighting…
ŵ(5,4)=w(5,4)+h(5)–h(4)=6-4-0=2
ŵ(2,4)=w(2,4)+h(2)–h(4)=1-1-0=0
ŵ(4,3)=w(4,3)+h(4)–h(3)=-5+0+5=0
ŵ(3,2) = w(3,2) + h(3) –h(2)=4-5+1=0 Fig (d): Gʹwith Reweighted edges

16. Computing All-Pairs Shortest Path
•Dijkstra’salgorithmisusedtofindtheshortestpaths.
•ThealgorithmisrunoncewitheachvertexvєVassource.
•IttakesthereweightedgraphGʹasinputandcomputesforallthevertexvєV.
•Finallyδ(u,v)iscomputedas:δ(u,v)=(u,v)+h(v)–h(u)
•AfterV-1passestheshortestpathsbetweenallpairsofverticeswouldbe
computed.

17. Algorithm
•Johnson’salgorithmusesassubroutinesboththeBellman-Fordalgorithmandthe
Dijkstra’salgorithm.
•Atfirst,itextendsthegivenweighteddirectedgraphGtoproducegraphGʹ.
•RunsBellman-Fordalgorithmtocomputeh(v)ifthegraphGʹdoesnotcontain
negativecycles.
•ReweightsthegraphGʹtogetreweightededgesEʹ.
•RunsDijkstra’salgorithmV-1timestogetAll-PairsShortestPathofGʹ,and
correspondinglycomputestheshortestpathsofthegraphGusing:
δ(u,v)=(u,v)+h(v)–h(u)
•Itreturnsa|V|x|V|matrix,D=d
uv,whered
uv=δ(u,v).
RunningTime:
•Ifthemin-priorityqueueinDijkstra’salgorithmisimplementedbyaFibonacci
heap,Johnson’salgorithmrunsinO(V
2
lgV+VE)time.
•BinaryminheapimplementationyieldsarunningtimeofO(VElgV).

18. Algorithm…
JOHNSON(G,w)
ComputeG',whereG'.V=G.VU{s},G'.E=G.EU{(s,v):vєG.V}and
w(s,v)=0forallvєG.V
If(BELLMAN-FORD(G',w,s)==FALSE)
print“GraphcontainsNegative-WeightCycle”
ElseFor(EachVertexvєG'.V)
Seth(v)tothevalueofδ(s,v)computedbyBELLMAN-FORDalgorithm
Foreachedge(u,v)єG'.E
ŵ(u,v)=w(u,v)+h(u)–h(v)
LetD=(d
uv)beanewnxnmatrix
For(EachVertexuєG.V)
RunDIJKSTRA(G,ŵ,u)tocompute(u,v)forallvєG.V
For(EachVertexvєG.V)
d
uv=(u,v)+h(v)–h(u)
ReturnD

19. Example
Fig(e):ReweightedGraph
2
2
2
0
0
S VRelax(u, v, w) Q uCost
1,2,3,4,510
1 2
3
5
Relax (1,2): 2.d= min (2.d, 1.d+ w(1, 2)) = (ꝏ, 0 + 4) = 4
Relax (1,3): 3.d= min (3.d, 1.d+ w(1, 3)) = (ꝏ, 0 + 13) = 13
Relax(1,5): 5.d= min (5.d, 1.d+ w(1, 5)) = (ꝏ, 0 + 0) = 0
2,3,4,550
1,5 4Relax (5,4): 4.d= min (4.d, 5.d+ w(5, 4)) = (ꝏ, 0+ 2) =22,3,442
1,5,43Relax (4,3): 3.d= min (3.d, 4.d+ w(4, 3)) = (13, 2+ 0) = 22,3 32
1,5,4,32Relax (3,2): 2.d= min (2.d, 3.d+ w(3, 2)) = (4, 2 + 0) = 22 22
ꝏ
0 ꝏ
ꝏꝏ
Fig (f): (u, v) for Graph in Fig (e) from
Source 1using Dijkstra’sAlgorithm
(u, v) from Source 1

20. Fig (f): (u, v) from Source 1
Example…
Fig (g): δ(u, v) of Graph in Fig (f) from source 1
using d
uv= (u, v) + h(v) –h(u)
( (u,v), δ(u,v)) –Values within each vertex.
2
2
2
0
0
δ(1, 2) = (1,2) + h (2) –h (1) = 2 –1 –0 = 1
δ(1, 3) = (1,3) + h (3) –h (1) = 2 –5 –0 = -3
δ(1, 4) = (1,4) + h (4) –h (1) = 2 + 0 –0 = 2
δ(1, 5 )= (1,5) + h (5) –h (1) = 0 –4 –0 = -4
δ(u, v) from Source 1

21. 0
0
0
2
2
Example…
Fig(e):ReweightedGraph
S VRelax(u, v, w) Q uCost
1,2,3,4,520
2 4
5
Relax (2, 4): 4.d= min (4.d, 2.d+ w(2, 4)) = (ꝏ, 0 + 0) = 0
Relax(2, 5): 5.d= min (5.d, 2.d+ w(2, 5)) = (ꝏ, 0 + 10) = 10
1,3,4,540
2,4 1
3
Relax (4, 1): 1.d= min (1.d, 4.d+ w(4, 1)) = (ꝏ, 0+ 2) =2
Relax (4, 3): 3.d= min (3.d, 4.d+ w(4, 3)) = (ꝏ, 0+ 0) =0
1,3,5 30
2,4,3- 1,5 12
2,4,3,15Relax (1, 5): 5.d= min (5.d, 1.d+ w(1, 5)) = (10, 2+ 0) = 25 52
0
ꝏ ꝏ
ꝏꝏ
(u, v) from Source 2
Fig (h): (u, v) for Graph in Fig (e) from
Source 2using Dijkstra’sAlgorithm

22. Fig (h): (u, v) from Source 2
Example…
δ(2, 1) = (2, 1) + h (1) –h (2) = 2 + 0 + 1 = 3
δ(2, 3) = (2, 3) + h (3) –h (2) = 0 –5 + 1 = -4
δ(2, 4) = (2, 4) + h (4) –h (2) = 0 + 0 + 1 = 1
δ(2, 5) = (2, 5) + h (5) –h (2) = 2 –4 + 1 = -1
δ(u, v) from Source 2
0
0
0
2
2
Fig (i): δ(u, v) of Graph in Fig (f) from source 2
using d
uv= (u, v) + h(v) –h(u)
( (u,v), δ(u,v)) –Values within each vertex.

23. 0
0
0
2
2
Example…
Fig(e):ReweightedGraph
S VRelax(u, v, w) Q uCost
1,2,3,4,530
3 2Relax (3, 2): 2.d= min (2.d, 3.d+ w(3, 2)) = (ꝏ, 0 + 0) = 0 1,2,4,520
3,2 4
5
Relax (2, 4): 4.d= min (4.d, 2.d+ w(2, 4)) = (ꝏ, 0+ 0) =0
Relax (2, 5): 5.d= min (5.d, 2.d+ w(2, 5)) = (ꝏ, 0+ 10) =10
1,4,5 40
3,2,41Relax (4, 1): 1.d= min (1.d, 4.d+ w(4, 1)) = (ꝏ, 0+ 2) = 2 1,5 12
3,2,4,15Relax (1, 5): 5.d= min (5.d, 1.d+ w(1, 5)) = (10, 2+ 0) = 25 52
ꝏ
ꝏ 0
ꝏꝏ
(u, v) from Source 3
Fig (j): (u, v) for Graph in Fig (e) from
Source 3 using Dijkstra’sAlgorithm

24. Fig (j): (u, v) from Source 3
Example…
δ(3, 1) = (3, 1) + h (1) –h (3) = 2 + 0 + 5 = 7
δ(3, 2) = (3, 2) + h (2) –h (3) = 0 –1 + 5 = 4
δ(3, 4) = (3, 4) + h (4) –h (3) = 0 + 0 + 5 = 5
δ(3, 5) = (3, 5) + h (5) –h (3) = 2 –4 + 5 = 3
δ(u, v) from Source 3
0
0
0
2
2
Fig (k): δ(u, v) of Graph in Fig (f) from source 3
using d
uv= (u, v) + h(v) –h(u)
( (u,v), δ(u,v)) –Values within each vertex.

25. 0
0
0
2
2
Example…
Fig(e):ReweightedGraph
S VRelax(u, v, w) Q uCost
1,2,3,4,540
4 1
3
Relax (4, 1): 1.d= min (1.d, 4.d+ w(4, 1)) = (ꝏ, 0 + 2) = 2
Relax (4, 3): 3.d= min (3.d, 4.d+ w(4, 3)) = (ꝏ, 0 + 0) = 0
1,2,3,530
4,3 2Relax (3, 2): 2.d= min (2.d, 3.d+ w(3, 2)) = (ꝏ, 0+ 0) =0 1,2,5 20
4,3,25Relax (2, 5): 5.d= min (5.d, 2.d+ w(2, 5)) = (ꝏ, 0+ 10) = 101,5 12
4,3,2,15Relax (1, 5): 5.d= min (5.d, 1.d+ w(1, 5)) = (10, 2+ 0) = 25 52
ꝏ
ꝏ ꝏ
0ꝏ
(u, v) from Source 4
Fig (l): (u, v) for Graph in Fig (e) from
Source 4 using Dijkstra’sAlgorithm

26. Fig (m): δ(u, v) of Graph in Fig (f) from source 4
using d
uv= (u, v) + h(v) –h(u)
( (u,v), δ(u,v)) –Values within each vertex.
Fig (l): (u, v) from Source 4
Example…
δ(4, 1) = (4, 1) + h (1) –h (4) = 2 + 0 –0 = 2
δ(4, 2) = (4, 2) + h (2) –h (4) = 0 –1 –0 = -1
δ(4, 3) = (4, 3) + h (3) –h (4) = 0 –5 –0 = -5
δ(4, 5) = (4, 5) + h (5) –h (4) = 2 –4 –0 = -2
δ(u, v) from Source 4
0
0
0
2
2

27. 2
2
2
0
4
Example…
Fig(e):ReweightedGraph
S VRelax(u, v, w) Q uCost
1,2,3,4,550
5 4Relax (5, 4): 4.d= min (4.d, 5.d+ w(5, 4)) = (ꝏ, 0 + 2) = 2 1,2,3,442
5,4 1
3
Relax (4, 1): 1.d= min (1.d, 4.d+ w(4, 1)) = (ꝏ, 2+ 2) =4
Relax (4, 3): 3.d= min (3.d, 4.d+ w(4, 3)) = (ꝏ, 2+ 0) =2
1,2,3 32
5,4,32Relax (3, 2): 2.d= min (2.d, 3.d+ w(3, 2)) = (ꝏ, 2+ 0) = 21,2 22
5,4,3,2- 1 14
ꝏ
ꝏ ꝏ
ꝏ0
(u, v) from Source 5
Fig (n): (u, v) for Graph in Fig (e) from
Source 5 using Dijkstra’sAlgorithm

28. Fig (o): δ(u, v) of Graph in Fig (f) from source 5
using d
uv= (u, v) + h(v) –h(u)
( (u,v), δ(u,v)) –Values within each vertex.
Fig (n): (u, v) from Source 5
Example…
δ(5, 1) = (5, 1) + h (1) –h (5) = 4 + 0 + 4 = 8
δ(5, 2) = (5, 2) + h (2) –h (5) = 2 –1 + 4 = 5
δ(5, 3) = (5, 3) + h (3) –h (5) = 2 –5 + 4 = 1
δ(5, 4) = (5, 4) + h (4) –h (5) = 2 + 0 + 4 = 6
δ(u, v) from Source 5
2
2
2
0
4

29. Example…
Output:
All-PairsShortestPathMatrixd
uv
Fig (a): Input Graph G
12345
101-32-4
230-41-1
374053
42-1-50-2
585160

30. Appendix
Triangleinequality
Foranyedge(u,v)єE,δ(s,v)≤δ(s,u)+w(u,v).
Heightfunction-DistanceFunction
HeightofaVertex-DistanceLabel.ItisrelatedtoitsDistancefromthesinkt
Relabel-OperationthatIncreasestheHeightofaVertex.
Telescopingseries
Foranysequencea
0,a
1,,,,a
n,

31. BELLMAN-FORD(G,w,s)
INITIALIZE-SINGLE-SOURCE(G,s)
For(i=1to|G.V|-1)
For(EachEdge(u,v)єG.E)
RELAX(u,v,w)
For(EachEdge(u,v)єG.E)
If(v.d>(u.d+w(u,v))
ReturnFALSE
ReturnTRUE
v.d:Shortest-PathEstimatefromSource
stov.
Appendix…
INITIALIZE-SINGLE-SOURCE(G,s)
For(EachVertexvєG.V)
v.d=ꝏ
v.π=NIL
s.d=0
RELAX(u,v,w)
If(v.d>(u.d+w(u,v))
v.d=u.d+w(u,v)
v.π=u
v.π:Predecessorofv.

32. Appendix…
DIJKSTRA(G,s)
INITIALIZE-SINGLE-SOURCE(G,s)
S=Ø
Q=G.V
While(Q≠Ø)
u=EXTRACT-MIN(Q)
S=SU{u}
For(EachVertexvєG.Adj[u]
RELAX(u,v,w)
S:verticeswhosefinalshortest-pathweightsfromthesourceshavealreadybeendetermined.
EXTRACT-MIN(Q):RemovesandreturnstheelementofQwiththeSmallestkey.

33. References:
•ThomasHCormen.CharlesELeiserson,RonaldLRivest,CliffordStein,
IntroductiontoAlgorithms,ThirdEdition,TheMITPressCambridge,
MassachusettsLondon,England.