Skip to content
Back to search results

Dijkstra Algorithm

Introduced by
Edsger W. Dijkstra
Year
1956
Type
algorithm
Family
Graph Algorithms
Font size

What does it do?

Dijkstra's Algorithm, introduced by Edsger W. Dijkstra in 1956, is one of the most fundamental algorithms in computer science for solving the single-source shortest path problem.

It finds the shortest path from a starting vertex to all other vertices in a weighted graph with non-negative edge weights.

The intuition behind the method

The algorithm maintains a set of vertices whose shortest distances from the source are already known, and iteratively expands this set by selecting the nearest unprocessed vertex and updating distances to its neighbors. The key insight is the greedy property: once a vertex is selected, its distance from the source is final because all edge weights are non-negative, so any longer path through unvisited vertices cannot be shorter. This guarantees correctness and optimality.

History

Edsger W. Dijkstra published his algorithm in 1959 in a three-page paper that would become one of the most cited works in computer science. The algorithm emerged from Dijkstra's work on the ARMAC computer in Amsterdam. Over decades, numerous improvements have been made, including better data structures (Fibonacci heaps achieving O(E+VlogV) complexity) and bidirectional variants. The algorithm remains central to modern routing protocols like OSPF in networking.

When to use it

Apply Dijkstra's algorithm when finding shortest paths in graphs with non-negative edge weights. It is ideal for navigation systems, network routing, and any graph problem requiring optimal paths. Use it for single-source shortest paths to all vertices. For graphs with negative weights, use Bellman-Ford instead. For bidirectional search or heuristic guidance, consider A* algorithm.

Limitations and considerations

  • Cannot handle graphs with negative edge weights
  • Computes shortest paths to all vertices, not just one destination (though can terminate early)
  • Less efficient than A* when heuristic information is available
  • Requires all vertices to be discovered; inefficient for very sparse connectivity

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Simple to understand and implement with clear correctness guarantees
  • Efficient with proper data structures: O((V+E)logV) with binary heap, O(V²) with array
  • Optimal for non-negative weight graphs; proves optimality of computed paths
  • Works on both directed and undirected graphs
  • Foundation for numerous extensions and related algorithms

Applications

  • GPS and navigation systems: finding shortest routes for vehicles and pedestrians
  • Network routing protocols: determining optimal paths for data packets in computer networks
  • Social networks: finding shortest connection paths between users or influencers
  • Game development: pathfinding for artificial intelligence and non-player character movement
  • Robot motion planning: computing optimal trajectories for robotic systems
  • Telecommunications: optimizing call routing and signal propagation paths

How it works

How it works

1

Set the distance to the source as zero and all other distances as infinity. Mark all vertices as unvisited and create a priority queue.

2

Select the unvisited vertex with minimum distance from the source using the priority queue.

3

For each neighbor of the selected vertex, if the path through the selected vertex offers a shorter distance, update the neighbor's distance and add it to the priority queue.

Common pitfalls

  • Using the algorithm on graphs with negative weights, resulting in incorrect shortest paths
  • Inefficient implementation with linear time extract-min operation, leading to poor performance
  • Failing to properly update distances when neighbors are revisited through different paths

Frequently asked questions

Why does Dijkstra's algorithm fail on negative weights?

The algorithm assumes that once a vertex is finalized, no shorter path can be found through unvisited vertices. With negative weights, a longer path might later improve when a negative edge is used, violating this assumption.

What data structure should be used for the priority queue?

Binary heaps provide O(logV) operations for both insertion and extraction, resulting in O((V+E)logV) total complexity. Fibonacci heaps achieve O(E+VlogV) but have large constant factors. Arrays work well for small graphs.

How can Dijkstra's algorithm find the path to one specific destination?

Terminate the algorithm as soon as the destination vertex is selected (its distance is finalized), avoiding unnecessary computation. Alternatively, reconstruct the path by maintaining parent pointers during execution.

Can Dijkstra's algorithm be used in undirected graphs?

Yes, undirected graphs can be represented as directed graphs with edges in both directions for each undirected edge, each with the same weight. The algorithm works identically on the bidirectional representation.

Related methods

Sources

  1. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.

    Open DOI reference
    Copied.
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

    ISBN: 978-0-262-03384-8
    Copied.