How to find the shortest path in a weighted graph using Dijkstra's algorithm?

Question

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 = $\infty$
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

Ethan Caldwell · Accepted Answer

Step-by-step example: Graph with source A. Step A B C D E Z 0 0 ∗ ∞ ∞ ∞ ∞ ∞ 1 0 ∗ 4 2 ∗ ∞ ∞ ∞ 2 0 ∗ 3 ∗ 2 ∗ 10 12 ∞ 3 0 ∗ 3 ∗ 2 ∗ 8 12 ∞ 4 0 ∗ 3 ∗ 2 ∗ 8 ∗ 12 14 5 0 ∗ 3 ∗ 2 ∗ 8 ∗ 10 ∗ 13 6 0 ∗ 3 ∗ 2 ∗ 8 ∗ 10 ∗ 13 ∗ ∗ = 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 )

How to find the shortest path in a weighted graph using Dijkstra's algorithm?

1 Answer

How to find the shortest path in a weighted graph using Dijkstra's algorithm?

1 Answer