Поиск широчайшего пути

Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём использования некоего специального значения вместо длины пути. Однако во многих случаях возможны более быстрые алгоритмы. Например, в графе, который представляет соединения между маршрутизаторами в интернете, в котором вес ребра представляет полосу пропускания соединения между двумя маршрутизаторами, задача о самом широком пути соответствует задаче поиска сквозного пути между двумя узлами интернета, который имеет максимально широкую полосу. Наименьший вес ребра на этом пути известен как ёмкость или ширина пути. Наравне с приложениями в маршрутизации в сети задача о самом широком пути является также важной компонентой метода Шульце определения победителя в многоходовых выборах, она была использована в цифровом совмещении изображений , и для вычисления максимальных потоков. Тесно связанная задача о минимаксном пути спрашивает о пути, который минимизирует максимальный вес любого из рёбер (можно интерпретировать как поиск самой ровной дороги, имеющей минимальные углы подъёма и спуска). Эта задача находит приложение в планировании дорожного движения. Любой алгоритм для задачи о самом широком пути может быть преобразован в алгоритм о минимаксном пути и, наоборот, путём обращения смысла всех сравнений весов, предпринимаемых в алгоритме, или, эквивалентно, путём замены весов на отрицательные значения.