Unraveling Dijkstra's Algorithm: Finding Shortest Paths

Question

Consider a weighted graph representing the distances between cities. Nodes represent cities, and edges represent the roads connecting them with associated distances. If City A is connected to City B with a distance of 5, City B to City C with a distance of 3, and City A to City C with a distance of 8, how would Dijkstra's algorithm determine the shortest path from City A to City C? Walk me through the steps and identify the shortest path and its total distance.

Answer 1

Djikstra's algorithm can also tell you the shortest paths from one vertex of a graph to all the other vertices, so I'll describe that variant here.

1.

Initial vertex: A

unvisited set of vertices = {B,C}

initial distances (haven't checked any of the other vertices, so don't actually know what these distances are yet except that A is length 0 from itself):

A to A = 0

A to B = infinity

A to C = infinity

mark A as visited

check adjacent vertices:

B and C are adjacent

A to B = 5

A to C = 8

for right now, we know 2 new things:

shortest known path is going from A directly to C (A -> C)

shortest known path from A to B is A -> B

2.

Now move on to closest vertex, which is B (5 < 8)

mark B as visited

unvisited set = {C}

C is only unvisited neighbor, so look at B to C

B to C has length 3, so compare to current shortest path, which is A -> C and has length 8.

length through B from A to C is 5+3 is not < 8, so we keep the earlier shortest path A -> C. If d(B,C) was (for instance) 2 instead, we'd update the shortest path to be A -> B -> C.

Done with vertex B.

3.

Now move on to vertex C.

mark C as visited.

C has no unvisited neighbors (since A and B were already visited), so don't have to do anything more here.

No more vertices to check. Done

Results:

shortest path from A to C is A -> C, length 8

shortest path from A to B is A -> B, length 5

Answer 2

The provided answer is accurate and well-explained. However, there's a small clarification to make in terms of the update process when considering alternative paths.

Start at the initial vertex A.

Unvisited set of vertices = {B, C}.

A to A = 0 (self-distance)

A to B = infinity

A to C = infinity

Mark A as visited.

Check adjacent vertices (B and C):

A to B = 5

A to C = 8

Shortest known path to C is A -> C (length 8).

Shortest known path to B is A -> B (length 5).

Mark B as visited.

Unvisited set = {C}.

Check B's unvisited neighbor, which is C.

B to C has length 3.

Compare to the current shortest path A -> C (length 8).

The length through B from A to C is 5 + 3 = 8, which is equal to the current shortest path.

No update is needed for the path from A to C.

Mark C as visited.

C has no unvisited neighbors (A and B were already visited).

Shortest path from A to C is A -> C, length 8.

Shortest path from A to B is A -> B, length 5.