Overview
Multi-source Dijkstra initializes the priority queue with all source nodes at distance zero, then runs the usual Dijkstra relaxation process to assign each node its closest source distance.
CoreSource checked
Multi-Source Dijkstra
Finds shortest distances from the nearest of several source nodes in a nonnegative-weight graph.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- Shortest Path
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 2
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
multiple sourcespriority queuedistance relaxationnearest origin
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E log V)
Average
O(E log V)
Worst
O(E log V)
Space
O(V)
When to Use
- Use when every node needs distance to the nearest facility, seed, or starting point.
- Use when all edge weights are nonnegative.
When Not to Use
- Avoid when edges can be negative; use a negative-weight-capable method instead.
- Avoid when each source needs a separate full distance map rather than nearest-source distance.
What It Does
- Finds shortest distances from the nearest of several starting nodes
- Uses multiple sources and priority queue to guide the work.
- Produces path.
Use Cases
- Route planning
- Game navigation
- Robotics motion planning
Inputs
- Search graph or state space
- Start state
- Goal state or target set
Outputs
- Path
- Distance estimate
- Search frontier state
Key Formulas (2)
Relaxation step
dist[v] = min(dist[v], dist[u] + weight(u, v))
dist[v] = min(dist[v], dist[u] + weight(u, v))Updates a candidate distance when a route through the current node is shorter.
Initial distances
dist[s] = 0 for every source s
dist[s] = 0 for every source sStarts all source nodes as equally reachable.
Pseudocode
- 1.Set all distances to infinity
- 2.For each source, set distance to 0 and push it into the priority queue
- 3.While the queue is not empty
- 4.Pop the smallest-distance node
- 5.Relax each outgoing edge with nonnegative weight
- 6.Return nearest-source distances and optional owners
Canonical Example
- Input
- sources A and D, edges A-B cost 2, D-C cost 1, B-C cost 4
- Output
- B is nearest to A with distance 2; C is nearest to D with distance 1
- Explanation
- Both sources expand from distance zero in the same priority queue.
Implementation Notes
- Push every source into the priority queue with distance 0.
- Optionally track owner[source] to identify the nearest source region.
- Use the same stale-priority-queue-entry checks as ordinary Dijkstra.
Common Pitfalls
- Initializing only one source changes the problem back to ordinary Dijkstra.
- Tie-breaking between equally near sources should be deterministic if ownership matters.
- Negative edges invalidate Dijkstra's settled-node assumption.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow the frontier, settled nodes, and the final path over the search space.
S
#
#
#
#
#
#
#
G
Step 1 of 6: Set all distances to infinity
pathfinding-mechanismNotes
Multi-source Dijkstra computes nearest-source distance, not a full all-sources distance table.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Multi-Source Dijkstra invariants, recurrences, relaxation rules, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofDijkstra's Algorithm
Multi-source Dijkstra starts with several initial sources.
Often paired withFlow Field Pathfinding
Flow fields commonly use multi-source distance propagation.
Related Algorithms
Tags
PathfindingWeighted GraphShortest PathPriority Queue