Skip to main content

Dijkstra's shortest paths from source F

Short answer

Dijkstra's algorithm repeatedly selects the vertex with smallest tentative distance, finalizes it, and relaxes outgoing edges. From F, shortest distances: E=1 (F-E), C=3 (F-C), A=7 (F-A), B=9 (F-A-B), D=∞ (unreachable).

Discuss Dijkstra's shortest path algorithm. Find the shortest paths for given graph with source node 'F' using Dijkstra's algorithm. [Figure: directed weighted graph with edges A→B 2, C→A 6, D→B 11, F→A 7, F→C 3, E→C 5, D→F 9, F→E 1]

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative weights. Keep dist[v] = ∞ for all except the source (0). Repeatedly select the unfinalised vertex u with the smallest dist, finalise it, and relax each outgoing edge (u, v, w): if dist[u] + w < dist[v], set dist[v] = dist[u] + w. Time O(V²) with an array.

Given directed graph

Edges: A→B 2, C→A 6, D→B 11, F→A 7, F→C 3, E→C 5, D→F 9, F→E 1. Source = F.

StepSelectedABCDEF
Init-∞∞∞∞∞0
1F (0)7∞3∞10
2E (1)7∞3∞10
3C (3)7 (3+6 = 9 is worse)∞3∞10
4A (7)793∞10
5B (9)793∞10
6D (∞)793∞10

In step 2, E→C gives 1 + 5 = 6, which is not better than 3.

Shortest distances from F:

DestinationDistancePath
E1F-E
C3F-C
A7F-A
B9F-A-B
D∞no path (D has no incoming edge)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 10 questions →