Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём использования некоего специального значения вместо длины пути[1]. Однако во многих случаях возможны более быстрые алгоритмы.
Например, в графе, который представляет соединения между маршрутизаторами в интернете, в котором вес ребра представляет полосу пропускания соединения между двумя маршрутизаторами, задача о самом широком пути соответствует задаче поиска сквозного пути между двумя узлами интернета, который имеет максимально широкую полосу[2][3]. Наименьший вес ребра на этом пути известен как ёмкость или ширина пути. Наравне с приложениями в маршрутизации в сети задача о самом широком пути является также важной компонентой метода Шульце определения победителя в многоходовых выборах[4], она была использована в цифровом совмещении изображений [5], анализе метаболических потоков[англ.][6] и для вычисления максимальных потоков[7].
Тесно связанная задача о минимаксном пути спрашивает о пути, который минимизирует максимальный вес любого из рёбер (можно интерпретировать как поиск самой ровной дороги, имеющей минимальные углы подъёма и спуска). Эта задача находит приложение в планировании дорожного движения[8]. Любой алгоритм для задачи о самом широком пути может быть преобразован в алгоритм о минимаксном пути и, наоборот, путём обращения смысла всех сравнений весов, предпринимаемых в алгоритме, или, эквивалентно, путём замены весов на отрицательные значения.
В неориентированном графе самый широкий путь может быть найден как путь между двумя вершинами в максимальном остовном дереве графа, а минимаксный путь может быть найден как путь между двумя вершинами в минимальном остовном дереве[9][10][11].