Question

Dijkstra's single source shortest path algorithm when run from vertex 'a' in the below graph, computes the corrects shortest path distance to

• A. Only vertex a
• B. Only vertices a, e, f, g, h
• C. Only vertices a, b, c, d
• D. All the vertices

Answer 1

The correct option is D All the vertices

Dijkstra's single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph.

Run the 1st pass : b1

b is minimum, so shortest distance to b is 1

After 1st pass, distances are : c3, e - 2
e is minimum, shortest distance to e is - 2

After 2nd pass, distances are : c3, f0 f is minimum, so shortest distance to f is 0

After 3rd pass, distances are : c3, g3
Both are same, let us take g so shortest distance to g is 3

After 4th pass, distances are: c3, h5, c is minimum. So shortest distance to c is 3

After 5th pass distance is : h - 2

h is minimum, So shortest distance to h is - 2