Use Dijkstra's Algorithm to ﬁNd the Length of the Shortest

Question

Examlex · Accepted Answer

The Answer is First iteration: distinguished vertices:

a

; labels:

a : 0 , b : 3 , c : 7 , d : \infty , e : \infty , z : \infty

. Second iteration: distinguished vertices:

a , b ;

labels:

a : 0 , b : 3 , c : 5 , d : 9 , e : \infty , z : \infty

. Third iteration: distinguished vertices:

a , b , c ;

labels:

a : 0 , b : 3 , c : 5 , d : 6 , e : 11 , z : \infty

. Fourth iteration: distinguished vertices:

a , b , c , d ;

labels:

a : 0 , b : 3 , c : 5 , d : 6 , e : 8 , z : 14

. Fifth iteration: distinguished vertices:

a , b , c , d , e ;

labels:

a : 0 , b : 3 , c : 5 , d : 6 , e : 8 , z : 13

. Since at the next iteration

z

is a distinguished vertex, we conclude that the shortest path has length 13 .

Definitions: