LH
Apr 29, 2026
How to find the shortest path in a weighted graph using Dijkstra's algorithm?
I am studying graph theory and I need to understand Dijkstra's algorithm for finding the shortest path from a source vertex to all other vertices in a weighted graph.
I know the basic idea:
- Set distance to source = 0, all others =
- Mark all vertices as unvisited
- For the current vertex, consider all unvisited neighbors and update their distances
- Mark current as visited, select the unvisited vertex with smallest distance
- Repeat until all visited
But I have specific questions:
- Why does Dijkstra's algorithm fail with negative edge weights?
- What is the time complexity with different data structures?
- Can someone walk through the algorithm step-by-step on a concrete graph?
For example, find shortest paths from A on:
- A→B: 4, A→C: 2
- B→C: 1, B→D: 5
- C→D: 8, C→E: 10
- D→E: 2, D→Z: 6
- E→Z: 3
1 answers169 views
Loading comments...
1 Answer
**Step-by-step example:** Graph with source A.
\begin{array}{c|cccccc}
\text{Step} & A & B & C & D & E & Z \\ \hline
0 & 0^* & \infty & \infty & \infty & \infty & \infty \\
1 & 0^* & 4 & 2^* & \infty & \infty & \infty \\
2 & 0^* & 3^* & 2^* & 10 & 12 & \infty \\
3 & 0^* & 3^* & 2^* & 8 & 12 & \infty \\
4 & 0^* & 3^* & 2^* & 8^* & 12 & 14 \\
5 & 0^* & 3^* & 2^* & 8^* & 10^* & 13 \\
6 & 0^* & 3^* & 2^* & 8^* & 10^* & 13^*
\end{array}
$*$ = visited (finalised).
Final shortest distances: A→B: 3 (A→C→B), A→C: 2, A→D: 8 (A→C→B→D), A→E: 10 (A→C→B→D→E), A→Z: 13 (A→C→B→D→E→Z).
**Why Dijkstra fails with negative weights:**
Dijkstra assumes that once a vertex's distance is finalised (visited), it will never decrease. With negative edges, a later path could reduce the distance, invalidating this assumption. For negative weights without negative cycles, use the Bellman-Ford algorithm instead.
**Time Complexity:**
- Naive array: $O(V^2)$
- Binary heap: $O((V + E) \log V)$
- Fibonacci heap: $O(V \log V + E)$
Loading comments...