Сочетание кратчайшего пути и минимального остовного дерева

Question

Сочетание кратчайшего пути и минимального остовного дерева

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

 G
|2
H      A
|1     |6
F      ------B
|1           | 7
E -----D-----C
2      8

Есть также грань между А и Е с двумя весами, но я не мог этого показать.

Теперь, во-первых, мне нужно найти кратчайший путь между A и E (я должен сделать это из-за моего приложения), который является A-E-D-C, а затем соединить весь граф с минимальным охватом. Есть ли кто-нибудь, чтобы помочь мне дать некоторую подсказку? Извините за плохой английский это не мой родной язык

0

algorithm c++shortest-path

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Просто MST

Если вы просто хотите MST, это просто включает в себя запуск Алгоритм Крускала (см. ниже) или Алгоритм Прима:

Инициализируйте дерево с одной вершиной, произвольно выбранной из графа.

Вырастите дерево на одно ребро. Из ребер, которые соединяют дерево с вершинами, которых еще нет в дереве, найдите ребро с минимальным весом и перенесите его в дерево.

Повторите шаг 2 (пока все вершины в дереве).

Это не подразумевает получение кратчайших путей между вершинами. На самом деле, это не обязательно будет включать некоторые кратчайшие пути. Рассматривать:

  A
1 |\
B \
1 |  \ 2
C   \
1 |    \
D-----E
1

Кратчайший путь между A и E равен 2 (непосредственно от A до E), но MST (A-B-C-D-E) не включает этот край.

«MST», включая кратчайший путь

Если вы хотите найти MST, включающий кратчайший путь, это самая интересная проблема.

Это можно решить, запустив алгоритм Крускала с небольшим изменением.

Происходит от Википедия:

Создайте лес F (набор деревьев), где каждая вершина графа является отдельным деревом, исключая вершины из кратчайшего пути.
Добавьте кратчайший путь как одиночное дерево в лес
Создайте набор S, содержащий все ребра в графе, исключая ребра из кратчайшего пути
Пока S непусто, а F еще не охватывает
- Удалите ребро с минимальным весом из S
- Если этот край соединяет два разных дерева, то добавьте его в лес, объединив два дерева в одно дерево.
- В противном случае откажитесь от этого края

3