A directed graph has edges S→A (4), S→B (1), B→A (2), A→C (1) and B→C (5). What is the shortest distance from S to C?
Correct answer C. 4
Explanation
Dijkstra settles S (0), then B (1). Through B, A improves from 4 to 3 and C becomes 6. A is settled next at 3, and A→C improves C to 3 + 1 = 4. So the shortest path is S→B→A→C with length 4. The value 5 comes from the direct S→A→C route, and 6 from S→B→C.
Answer checked How we write and check questions
Discussion