Утверждение: если все веса ребер в графе различны, то существует единственное дерево кратчайших путей. Либо приведите убедительный аргумент в пользу того, что утверждение верно, либо приведите контрпример.
Утверждение дерева кратчайшего пути (график)
comment
Какой график вы используете? (Я предполагаю, что вы используете график сетки A *?)
- person Burdock schedule 15.11.2014
comment
Не могли бы вы расширить, если все веса ребер различны.
- person Burdock schedule 15.11.2014
comment
Это MST (минимальное связующее дерево), поэтому все ребра различны.
- person camrymps schedule 15.11.2014
Ответы (2)
Если у вас есть MST, то из каждых двух вершин существует уникальный путь, что делает дерево кратчайших путей бессмысленным. Я предполагаю, что вы имели в виду, что результатом является MST. Однако это не так. Деревья кратчайших путей отличаются от минимальных остовных деревьев для одного и того же графа и даже для одного и того же корня. Дерево кратчайшего пути с корнем в вершине v обычно является результатом применения алгоритма Дейкстры к вершине v.
В общем, трудно поверить в уникальность деревьев над графами, если не заданы строгие требования (например, новые веса равны старым +1). @rici привел контрпример со структурой полидерева. Вот еще один контрпример для неориентированных графов. Оба дерева являются деревьями кратчайших путей с корнем A. Обратите внимание, что:
- Хотя оба являются деревьями кратчайших путей, их общая стоимость различается.
- Оба являются остовными деревьями, но ни одно из них не является минимальным.
person
Xline
schedule
15.11.2014
Я думаю, вы по ошибке поменяли местами веса ребер EC и BC. В среднем графе путь из A в C имеет общий вес 4+3=7. В крайнем правом графе путь из A в C имеет общий вес 5+6=11. Создание веса (EC) = 2 и веса (BC) = 6, кажется, исправляет это.
- person Mahesha999; 11.01.2018
Если я правильно понял вопрос:
person
rici
schedule
15.11.2014
