FoundationSource checked

Dijkstra's Algorithm

Finds shortest paths from one source in a graph with nonnegative edge weights.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Intermediate
Family: Shortest Path
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 23
Code example: Not ready
Visualization: Ready
Aliases: Dijkstra, Dijkstra's Shortest Path

Overview

Dijkstra's Algorithm maintains tentative distances and repeatedly settles the unsettled node with the smallest known distance, relaxing its outgoing edges.

Core Concepts

tentative distanceedge relaxationpriority queuenonnegative weights

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O((V + E) log V)

Average

O((V + E) log V)

Worst

O((V + E) log V)

Space

O(V)

When to Use

Use it when all edge weights are nonnegative.
Use it when shortest paths from one source are needed.
Use a priority queue implementation for sparse graphs.

When Not to Use

Avoid it when any edge weight can be negative.
Avoid it for unweighted graphs where BFS is simpler.
Avoid recomputing it from scratch when the graph changes incrementally and a dynamic method is available.

What It Does

Computes single-source shortest paths
Uses edge relaxation and a priority queue

Use Cases

Road-network routing with nonnegative costs
Network delay calculations
Weighted graph search

Inputs

Weighted graph with nonnegative edges
Starting node

Outputs

Shortest distance to each reachable node
Previous-node links for paths

Key Formulas (1)

Relaxation step

dist_[v] = min(dist_[v], dist_[u] + weight(u, v))

dist[v] = min(dist[v], dist[u] + weight(u, v))

Updates a neighbor distance if the path through the current node is shorter.

Pseudocode

1.Set the start distance to zero
2.Put the start node in a priority queue
3.Remove the node with the smallest distance
4.Relax each outgoing edge
5.Update neighbors when a shorter distance is found
6.Repeat until the queue is empty

Canonical Example

Input: edges = A-B: 1, B-C: 2, A-C: 5; start = A; goal = C
Output: path = A -> B -> C, cost = 3
Explanation: Dijkstra's Algorithm: The algorithm compares route costs and selects the cheaper path through B.

Implementation Notes

Initialize the source distance to zero and all others to infinity.
Relax each outgoing edge from the node with the smallest tentative distance.
Store predecessors if the actual path must be reconstructed.

Common Pitfalls

Using Dijkstra's algorithm with negative edge weights.
Treating a stale priority-queue entry as final without checking the current distance.
Forgetting to initialize unreachable nodes to infinity.