Overview
Acyclic Shortest Path takes advantage of the graph's dependency order, making shortest paths simple even with negative edges as long as there are no cycles.
CoreSource checked
Acyclic Shortest Path
Finds shortest paths in a weighted DAG by relaxing edges in topological order.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- DAG Shortest Path
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
topological orderdistance relaxationweighted DAGpredecessor links
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)
When to Use
- Use when the graph is acyclic and a topological order is available.
- Use when project dependency costs is a central requirement.
When Not to Use
- Avoid when the graph may contain cycles or dynamic edge updates.
- Avoid when edge costs or movement rules do not match the algorithm's assumptions.
What It Does
- Topologically orders the graph
- Initializes source distance
- Relaxes each outgoing edge once
Use Cases
- Project dependency costs
- DAG route planning
- Compiler and scheduling graphs
Inputs
- Weighted directed acyclic graph
- Source node
Outputs
- Shortest distance to each reachable node
- Predecessor links
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 after its predecessor is processed.
Pseudocode
- 1.Topologically sort the DAG
- 2.Set source distance to 0 and others to infinity
- 3.Visit nodes in topological order
- 4.Relax every outgoing edge
- 5.Return distances and predecessors
Canonical Example
- Input
- edges = A->B:2, A->C:5, B->C:1
- Output
- dist[C] = 3
- Explanation
- Relaxing A then B finds the cheaper route A-B-C.
Implementation Notes
- Reuse the same relaxation helper used by Bellman-Ford or Dijkstra's Algorithm.
- Store predecessor links so paths can be reconstructed after distances are computed.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Forgetting to skip unreachable nodes can produce invalid arithmetic with infinity.
- Mixing heuristic, movement cost, and tie-breaking rules can produce surprising routes.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow distance values propagating once through a topologically ordered graph.
S
#
#
#
#
#
#
#
G
Step 1 of 5: Topologically sort the DAG
pathfindingNotes
Negative edges are safe here because a DAG cannot contain negative cycles.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Acyclic Shortest Path 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 pageUsesTopological Sort
Acyclic shortest paths relax vertices in topological order instead of using a priority queue.
Related Algorithms
Tags
Shortest PathDirected Acyclic GraphDynamic ProgrammingWeighted Graph