Учитывая MST для взвешенного по ребрам графа, как вы можете найти минимально взвешенный путь от x до y?

У меня есть взвешенный по ребрам неориентированный граф, представленный минимальным остовным деревом. Каждая вершина представлена ​​целым числом. MST выглядит так:

Интересно, как я могу использовать этот MST, чтобы найти кратчайший путь от вершины x до вершины y? Скажем, я хочу найти кратчайший путь от 0 до 3. Легко видеть, что путь равен 0-2, 2-3 с общим весом 0,26 + 0,17 = 0,43. Но как мне построить общий способ сделать это? в псевдокоде

edge           weight
6-2            0,40
4-5            0.35
5-7            0.28
2-3            0.17
0-2            0.26
1-7            0.19
0-7            0.16

undirected-graph prims-algorithm minimum-spanning-tree
person 0jnats3    schedule 06.10.2019    source источник
comment
Должен быть только один путь (это дерево), и это не обязательно тот, который был бы кратчайшим в полном графике, поэтому я не уверен, что вы хотите сделать.   -  person harold    schedule 06.10.2019
comment
@harold Я предполагал, что дерево будет содержать все наименьшие пути от любой вершины к любой другой вершине.   -  person 0jnats3    schedule 06.10.2019
comment
К сожалению, это не работает, MST имеет минимальный общий вес, например в MST на соответствующей странице вики два узла в левом нижнем углу имеют ребро длиной 9 между ними в исходном графе, и это ребро является кратчайшим путем, но это ребро отсутствует в MST.   -  person harold    schedule 06.10.2019

Ответы (2)


arrow_upward
0
arrow_downward

В этом случае, поскольку вам дано MST, вы знаете только, что общие веса ребер в графе минимальны. Однако путь между двумя узлами в MST не гарантирует, что это минимальный путь между этими двумя узлами на реальном графе. Чтобы найти минимально взвешенный путь от узла x к узлу y, вы можете выполнить алгоритм Дейкстры на исходном графе (не на MST). Дейкстра может найти минимальное расстояние от начального узла, в данном случае x, до каждого другого узла в графе.

Выполните алгоритм Дейкстры следующим образом и сохраните информацию в таблице:

  1. Начните с начального узла, в данном случае x, и перейдите к узлу с наименьшим весом из x.

  2. Из посещенного узла с наименьшим весом исследуйте соседей и снова выберите ребро с наименьшим весом.

  3. Подсчитайте общую стоимость так далеко от края, который вы посещаете. Если вы начали с x, затем посетили a, затем c, найдите общее расстояние от x до a до c.

  4. Если вес узла ниже, чем был ранее записан, обновите значение в таблице, потому что теперь был найден более короткий путь.

В конечном итоге после выполнения этого алгоритма таблица должна содержать путь с наименьшим весом от x до y.

person anaidu    schedule 08.03.2020

arrow_upward
0
arrow_downward

MST не обязательно содержит кратчайший путь от одной вершины x до другого вектора y. Минимальное остовное дерево - это дерево, которое нашло минимальный путь для каждого посещаемого узла. Это не обязательно означает, что кратчайший путь от x до y включен в MST. Чтобы найти истинный кратчайший путь от x до y, вам нужно будет запустить алгоритм, чтобы найти кратчайший путь на исходном графе, как у Дейкстры.

person Lloyd Abernathy    schedule 10.04.2020