liveBook · Manning

Single-source shortest path

As explained in 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.

A single-source shortest-path algorithm finds the shortest distances from one starting vertex to every other vertex. It answers a different question from an all-pairs algorithm, which finds distances between every pair. section 9.1

Choose an approach based on the graph and the question:

  • Dijkstra’s algorithm handles one starting vertex and is described as suitable when edge weights are positive. section 9.1
  • Bellman–Ford also handles one starting vertex, while supporting negative edge weights and detecting negative cycles. section 9.3
  • For sparse graphs, repeatedly running a single-source algorithm can be more performant than Floyd–Warshall’s all-pairs computation. section 9.3

One starting point

If you are at Node A and need distances to the rest of a network, that is a single-source problem. If you need distances between every possible pair, it is an all-pairs problem. section 9.1

How Algorithms Every Programmer Should Know covers it

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.
How it connects
Connects single-source shortest paths to Dijkstra’s and Bellman–Ford algorithms, and contrasts them with Floyd–Warshall.

Also explained in

Compare how 3 books explain single-source shortest path →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.