Дерево минимально взвешенных путей неориентированного графа

Question

Предположим, что у нас есть неориентированный граф G = (V, E), и у нас есть два узла S и X.

1. Можем ли мы придумать алгоритм, позволяющий минимизировать наибольший вес ребра на пути от S до X? Обратите внимание, что это не алгоритм кратчайшего пути, поскольку мы не заинтересованы в минимизации их суммы.
2. В чем сложность этого алгоритма?
3. Является ли алгоритм минимального связующего дерева (например, Prim) решением проблемы?

Answer 1

Вы можете использовать минимальное связующее дерево (алгоритм Прима) для решения этой проблемы.Вы начнете с вершины S, затем продолжите строить дерево, используя алгоритм Прима, пока не найдете X.Сложность будет O ((V + E) * logV).
Это будет работать, потому что в алгоритме прима вы всегда сначала выбираете ребро с минимальным весом.

Answer 2

Я не знаю, решит ли это минимальное связующее дерево, но это, безусловно, можно решить, внеся некоторые изменения в алгоритм Дейкстры.

Определите «длину» пути как максимальное ребро в этом пути. Теперь найдите кратчайший путь от S до X, используя алгоритм Дейкстры. Это путь, который вы ищете. Сложность равна O((N+M)log N), если вы используете двоичную кучу, и O(N * log N + M) с кучей Фибоначчи.

Обратите внимание, что для этого нового определения длины пути, если длина пути равна l, добавление ребра в конец пути не приведет к уменьшению его длины, так как максимальное ребро в этом пути может только увеличиться , Это свойство необходимо для правильной работы алгоритма Дейкстры.

Например, если вы искали путь с кратчайшим ребром, то алгоритм Дейкстры потерпит неудачу так же, как и при наличии отрицательных ребер в графе.