Справочник по быстрому алгоритму для кратчайших путей узкого места

12

Я ищу хороший справочник для кратчайших путей узкого места. В частности, учитывая вершины s и t в неориентированном графе с весом ребер, вы хотите кратчайший путь от s до t, где длина пути - это максимальное ребро на этом пути. Это можно решить за время O (n + m), найдя средний вес ребра и (аккуратно) рекурсивно удалив половину ребер.

Кто-нибудь знает ссылку на это?

ds.algorithms reference-request graph-algorithms Бен
источник
Возможно, это спорный вопрос, но проблема, которую вы описываете, - это проблема минимаксного пути. Кратчайший путь к узким местам - это максимальная версия того, что вы описываете. Однако алгоритм для одной версии обычно (всегда?) Дает алгоритм для другой версии.
bbejot

Ответы:

10

П. М. Камерини (1978), проблема связующего дерева min-max и некоторые расширения, Письма обработки информации 7 (1): 10–14, doi: 10.1016 / 0020-0190 (78) 90030-3

Дэвид Эппштейн
источник
5
Кстати, если вы хотите решить проблему задачи с одним источником (и в некотором смысле все пары) для неориентированных графов, вы можете сделать это за рандомизированное время O (m + n): в 1961 году ТС Ху отметил, что пути узких мест для всех пар закодированы в максимальном остовном дереве; тогда алгоритм Karger, Klein и Tarjan с линейным временем минимального связующего дерева дает вам то, что вы хотите.
Вирджи
Насколько я могу судить, ссылка не то, что мне нужно. St-путь в связующем дереве min-max необязательно является самым коротким st-узким путем. Кроме того, алгоритм линейного ожидаемого времени KKT не то, что мне нужно, так как я хочу детерминированный, а не ожидаемое время выполнения. В любом случае, спасибо за помощь.
Бен
4
Фактически, st-путь P в минимальном остовном дереве T имеет минимальный максимальный вес ребра по всем st-путям. Предположим, это не так. Тогда пусть максимальное ребро P будет e. Удаление e из T создает разрез графа. Реальная minmax st-путь P 'должна иметь ребро e', пересекающее этот разрез. Добавление e 'к T \ {e} создает новое остовное дерево T', которое должно иметь меньшую стоимость, чем T, поскольку вес e 'не превышает максимальный вес ребра на P', который меньше w (e). Это противоречит тому, что T - минимальное остовное дерево.
Дева
2

На проблеме кратчайшего пути узкого места

Зенна
источник
3
Это в основном касается направленной версии проблемы, и она в основном заменена более ранней статьей 1988 года Габова и Тарьяна ams.org/mathscinet-getitem?mr=955149 . Смотрите en.wikipedia.org/wiki/Widest_path_problem для многих других ссылок.
Дэвид Эппштейн
Ссылка не работает.
hengxin