Dijkstra’s Shortest-Path Algorithm and Its Limits with Negative Weights
Summary
The guide describes Dijkstra’s greedy method for finding shortest paths from a starting node to other nodes in a weighted graph. It initializes tentative distances from the source, repeatedly selects the unprocessed node with the lowest current distance, and updates distances to its neighbors. A worked table illustrates how candidate nodes are finalized and distance estimates change. The article distinguishes this single-source shortest-path problem from the minimum spanning tree problems addressed by Kruskal’s and Prim’s algorithms.
It gives a simple implementation’s time complexity as O(n²) and notes that suitable data structures can improve performance, especially for sparse graphs. A central limitation is that edge weights must be non-negative: with negative weights, a distance finalized early may later be improved, and a negative-weight cycle makes path costs unbounded below. The guide points to Bellman-Ford and Johnson’s algorithm for cases involving negative weights. It briefly mentions currency arbitrage, but does not explain a specific trading implementation; the main contribution is the graph algorithm and its constraints.
Key ideas
- Dijkstra’s algorithm computes shortest paths from one source by repeatedly finalizing the nearest unprocessed node.
- A simple implementation has O(n²) runtime, while data-structure choices can improve performance on sparse graphs.
- The method requires non-negative edge weights because finalized distances may otherwise be incorrect.
- Negative-weight cycles make path costs decrease without bound and require other algorithms to detect or handle them.
- Dijkstra solves shortest-path problems, while Prim’s and Kruskal’s algorithms construct minimum spanning trees.
Tags
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.