У меня есть гранично-взвешенный ненаправленный граф, представленный минимальным остовным деревом. Каждая вершина представлена целым числом. 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