Dijkstra's Shortest Path Algorithm — Detailed Research
Note
Abstract
Dijkstra's algorithm is a classical greedy algorithm for solving the single-source shortest-path problem
in weighted graphs with non-negative edge weights. It repeatedly selects the unsettled vertex with the
smallest tentative distance and relaxes its outgoing edges. This paper explains the graph model,
algorithmic steps, correctness intuition, complexity under different data structures, applications,
limitations, and comparisons.
1. Introduction
Shortest-path problems occur whenever a system must minimize a cumulative cost. Road maps use
distance or travel time, communication networks use latency or link cost, and robotic systems may use
movement cost. Dijkstra's algorithm provides an efficient solution when edge weights are
non-negative.
2. Basic Idea
The algorithm maintains a tentative distance from the source to each vertex. Initially only the source
has distance zero. At every iteration, the smallest tentative distance among unsettled vertices is
selected. Because all edge weights are non-negative, no later route can improve the selected
distance.
3. Relaxation
For an edge (u,v) with weight w, relaxation tests whether d[u]+w is smaller than d[v]. If it is, d[v] is
updated and u becomes the predecessor of v. This operation gradually improves estimates until
shortest distances are finalized.
4. Procedure
Initialize distances, predecessors, and an unsettled set or priority queue. Repeatedly extract the vertex
with minimum tentative distance, mark it settled, and relax every outgoing edge. The process
continues until the queue is empty or the desired target has been finalized.
5. Correctness Intuition
The key greedy property depends on non-negative edge weights. Suppose u is the unsettled vertex
with minimum tentative distance. Any path reaching another unsettled vertex first must have cost at
least d[u], because additional edges cannot reduce the path cost. Thus d[u] is already optimal when u
is selected.
6. Complexity
With an adjacency matrix and linear search, the common complexity is O(V^2). With adjacency lists
and a binary heap, the complexity is commonly O((V+E) log V). Different priority-queue structures can
produce other bounds, but efficient minimum extraction improves performance on sparse graphs.
7. Restrictions
Dijkstra's algorithm assumes non-negative edge weights. Negative edges can invalidate the greedy
finalization rule. If negative weights are present, Bellman-Ford or another appropriate shortest-path
algorithm should be considered.
8. Path Reconstruction
Distances alone may not be enough. By storing a predecessor for every successful relaxation, the
algorithm can reconstruct a shortest path. Starting from a target vertex and following predecessor
pointers backward yields the route in reverse order.
9. Applications
Dijkstra's algorithm is used in navigation systems, network routing, geographic information systems,
robotics, and resource optimization. It is especially useful when the graph is sparse and edge costs
represent non-negative quantities.
10. Variants
Bidirectional search can reduce practical work when finding a path between two known endpoints.
Specialized implementations may use Fibonacci heaps or other priority queues. In road networks,
additional preprocessing and heuristic methods can further accelerate queries.
11. Comparison
Compared with Bellman-Ford, Dijkstra is generally faster but less general because it cannot safely
process negative edge weights. Compared with breadth-first search, Dijkstra handles arbitrary
non-negative weights whereas BFS is appropriate when all edges have equal unit cost.
12. Conclusion
Dijkstra's algorithm is a foundational greedy method. Its efficiency and intuitive operation make it one
of the most important algorithms for weighted shortest-path problems, provided that edge weights
satisfy the non-negativity requirement.