Изменение кратчайшего пути для получения минимального пути

Question

Если мы модифицируем задачу кратчайшего пути так, чтобы стоимость пути между двумя вершинами была максимальной из затрат на ребра на ней, то для любой пары вершин u и v путь между ними следует за минимумомостовное дерево - это путь с минимальными затратами.

Как я могу доказать, что этот подход верен?Это имеет смысл, но я не уверен.Кто-нибудь знает, существует ли этот алгоритм в литературе?Для него есть имя?

Answer 1

Упомянутый вами подход подробно обсуждается в литературе, в которой обсуждается связь между алгоритмом Прима и алгоритмом Дейкстры, поскольку обычная википедия - хорошее место для начала вашего исследования:

Процесс, лежащий в основе алгоритма Дейкстры , похож на жадный процесс, используемый в алгоритме Прима . Цель Прима - найти минимальное остовное дерево, которое соединяет все узлы графа Дейкстра касается только самого дешевого пути из двух двух узлов.

Answer 2

Вы можете использовать некоторые основные факты MST (которые обычно обсуждаются в доказательстве корректности алгоритмов Прима и Крускала).Единственное, что сейчас имеет значение, это то, что

Лема 1:

При заданном графе (разбиение вершин на два непересекающихся множества) ребро вMST, соединяющий две части, будет самым дешевым из ребер, соединяющих две части.

(доказательство является прямым, если бы существовал более дешевый край, мы могли бы легко создать более дешевое остовное дерево)

Теперь мы можем доказать, что все пути в MST - это все пути минимальной стоимости, если учесть максимальную стоимость:

Возьмите любые две вершины s и t в G и путь p, который соединяет их в MST G. Теперь пусть uv будет самым дорогим ребром на этом пути.Мы можем описать граф, разрезанный над этим ребром, с одним разбиением с вершинами на стороне u MST и другим разбиением с вершинами на стороне v.Мы знаем, что любой путь, соединяющий s и t, должен проходить этот разрез, поэтому мы можем определить, что стоимость любого пути от s до t должна составлять как минимум стоимость самого дешевого фронта в этом разрезе.Но лемма 1 говорит нам, что ультрафиолетовое излучение - это самое дешевое преимущество в этом разрезе, поэтому p должно быть минимальным путем.