Таблица замен
| что спрашивают | что писать вместо dist[j] = min(dist[j], dist[i] + w) |
|---|
| кратчайший путь | так и оставить |
| самый длинный путь | max, и стартовать от -inf |
| наименьшее число рёбер | min(dist[j], dist[i] + 1) |
| самое лёгкое узкое место | min(dist[j], max(dist[i], w)) |
| сколько вершин достижимо | ничего, посчитать не-бесконечности |
| путь из X в Y | ничего, поменять стартовую вершину |
| путь через вершину | ничего, взять Флойда |
Меняется одна строка.
Узкое место
Формулировка звучит так: найти путь, в котором самое тяжёлое ребро как можно легче. Веса не складываются — вдоль пути берётся максимум, и уже его мы минимизируем. Так спрашивают про грузовик, который не проедет по слабому мосту: важен не весь маршрут, а худший мост на нём.