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

Question

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

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

Существует также край между A и E с 2 весом, но я не мог его показать.

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

Answer 1

Просто MST

Если вы просто хотите, MST, это только включает в себя запуск Kruskal's algorithm (смотри ниже) или Prim's algorithm:

1. Initialize дерево с одной вершиной, выбранное произвольно из графика.
2. Выращивание дерева одним краем: из ребер, которые соединяют дерево с вершинами еще не на дереве, найдите край минимального веса и перенесите его в дерево.
3. Повторите шаг 2 (пока все вершины не будут в дереве).

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

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

Самый короткий путь между А и Е 2 (только непосредственно от А до Е), но МСТ (А-В-С-Д-Е) не включает в себя этот край.

«MST» включая некоторые кратчайший путь

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

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

производных от Wikipedia:

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