Single-source shortest path
The single-source shortest-path problem is to find minimum-cost paths from one source vertex to every other reachable vertex in a weighted graph.
Algorithms Every Programmer Should Know
A single-source shortest path algorithm computes shortest-path distances from one starting vertex to other vertices in a graph.
- How it is used
- Frames shortest-path algorithm choice around whether distances are needed from one starting vertex or between every pair.
- How deep it goes
- Defines the single-source scope and compares algorithm choices, but does not work through a single-source algorithm step by step.
- Examples
- Uses reaching the rest of a network from Node A to illustrate the single-source problem.
- What you can do after
- Evaluate algorithm choices by comparing problem scope, graph density, and whether negative edge weights occur.
Read how Algorithms Every Programmer Should Know explains single-source shortest path →
Optimization Algorithms: AI techniques for design, planning, and control problems
The problem of finding minimum-cost paths from one source node to every other reachable node in a weighted graph.
- How it is used
- Frames shortest-path computation as a blind-search foundation for routing and navigation problems.
- How deep it goes
- Explains initialization, priority ordering, relaxation, predecessors, and target-specific early stopping without covering implementation complexity.
- Examples
- Uses a toy graph with source S, nodes C, D, A, and B, plus navigation-routing applications.
- What you can do after
- Apply Dijkstra’s algorithm to compute shortest-path distances and predecessor links from a source node.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
The single-source shortest path problem asks for the minimum-weight paths from one starting vertex to every other vertex in a weighted graph.
- How it is used
- Uses weighted graph routing to find minimum-cost paths from one starting vertex to every other vertex.
- How deep it goes
- Explains the greedy procedure, priority queue, distance updates, predecessor tracking, and path reconstruction without formal proof.
- Examples
- Demonstrates city distances and reconstructs a Los Angeles–Boston route through Riverside, Chicago, and Detroit.
- What you can do after
- Apply it via a weighted-graph implementation that returns minimum distances and predecessor edges for chosen routes.
Related concepts
- Dijkstra's algorithmaddressed by · Dijkstra's algorithm computes shortest paths from a source vertex in a weighted graph with nonnegative edge weights.
- all-pairs shortest pathcontrasts with · The all-pairs shortest path problem is the problem of finding a minimum-cost path between every pair of vertices in a graph.
- Floyd–Warshallalternative to · Floyd–Warshall is a dynamic programming algorithm for computing shortest-path distances between every pair of vertices in a weighted graph.
Questions about single-source shortest path
What is single-source shortest path?
The single-source shortest-path problem is to find minimum-cost paths from one source vertex to every other reachable vertex in a weighted graph.
Which Manning books explain single-source shortest path?
Algorithms Every Programmer Should Know, Optimization Algorithms: AI techniques for design, planning, and control problems and Classic Computer Science Problems in Swift: Essential techniques for practicing programmers.
What is the difference between single-source shortest path and all-pairs shortest path?
The single-source shortest-path problem is to find minimum-cost paths from one source vertex to every other reachable vertex in a weighted graph. The all-pairs shortest path problem is the problem of finding a minimum-cost path between every pair of vertices in a graph.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.


