Where it runs
1. The problem
The last lesson (Bellman-Ford, step 99) and Dijkstra (step 97) answer the same question: from ONE start node, how far is every other node? One run gives one row of distances.
Sometimes you need the whole table: the distance from every place to every other place. Example: a courier depot has 40 pickup points. It wants the cost of the trip between any two of them, so it can plan any route the moment someone asks. That is n start points, and the answer is a grid of n by n numbers.
You could run Dijkstra once from each node. Floyd-Warshall fills the whole grid with one short triple loop (three loops, one inside the other). The code stays simple when the graph is small and dense, which means it has many edges.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that need the shortest distance between every pair of nodes, or which nodes can reach which, on a graph of a few hundred nodes at most. Three nested loops with the middle node outermost fill the whole table in n^3 steps.
- 1334.Find the City With the Smallest Number of Neighbors at a Threshold Distance (opens in a new tab)Medium
n is at most 100, so run the triple loop once, then count for each city how many others sit within the threshold.
Swap min and plus for OR and AND, and the same loop tells for every pair of courses whether one is a prerequisite of the other.
The 26 letters are the nodes, so the table is 26 by 26, and each position of the string then costs one lookup.
Each equation is an edge with a ratio, and going through a middle variable multiplies two ratios where the lesson adds two costs.