Example - Shortest Path - Dijkstra's algorithm

Relaxation;

d(u) + c(u,v) < d(v)

d(v)=d(u) + c(u,v)

Source	A	B	C	D	E
A	0	∞	∞	∞	∞
C		10	5	∞	∞
E		8		14	7
B		8		13
D				9

Find the shortest path from A to B using the above table : B C  A   = 8

From Video Fig  A to C = 5  and C to B = 5+3=8

Find the shortest path from A to D using the above table : D B  C A  = 9

From Video Fig  A to C = 5  and C to B = 5+3=8 and B to D =8+1=9

Relaxation;

d(u) + c(u,v) < d(v)

d(v)=d(u) + c(u,v)

Source	A	B	C	D	E	F
A	0	∞	∞	∞	∞	∞
B		2	4	∞	∞	∞
C			3	6	4	∞
E				6	4	∞
D				6		6
F						6

Find the shortest path from A to F using the above table : F E B A

Find the shortest path from A to E using the above table : E B A

Find the shortest path from A to C using the above table : C B A

Find the shortest path from A to D using the above table : D B A