кратчайшие пути не путь в графе

Question

Мне было интересно, есть ли алгоритм, который бы находил кратчайшие пути в графе.

Допустим, у меня есть граф, в котором есть пары путей из одной вершины в другую.Два или более из этих путей имеют одинаковую стоимость.Как я могу отметить, найти и т.д. все кратчайшие пути между этими вершинами?Насколько я знаю, алгоритмы Дейкстры или Беллмана-Форда найдут кратчайший путь, но они "выбирают" только один.

Answer 1

Алгоритм Дейкстры дает вам стоимость всех возможных промежуточных узлов и стоимость кратчайшего пути к стоку.Вы можете получить все пути от источника к стоку, выполнив сначала поиск по глубине от приемника к источнику (в обратном направлении), где вы пересекаете ребро (назад), только если стоимость этого ребра равна разнице между стоимостьюкратчайший путь от источника до двух узлов.Конечно, вы получаете пути в обратном порядке, но поменять их легко.

.

Answer 2

Взгляните на Флойд-Варшалл .

В информатике Алгоритм Флойда – Варшалла (иногда известный как WFI Алгоритм или Алгоритм Роя – Флойда) является графом алгоритм анализа для нахождения кратчайшие пути во взвешенном графе (с положительным или отрицательным краем веса). Разовое исполнение алгоритм найдет длины (суммарные веса) кратчайших путей между всеми парами вершин, хотя это не возвращает детали Сами дорожки. Алгоритм является пример динамического программирования.