Алгоритм Javascript Dijkstra: получение каждого возможного кратчайшего пути между 2 узлами

Question

Я нашел этот алгоритм, выходящий за пределы моего понимания и навыков JS. https://rosettacode.org/wiki/Dijkstra%27s_algorithm#JavaScript Каким-то образом мне удалось использовать его несколько месяцев назад для музыкального приложения, над которым я работаю.

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

Например, на этом графике:

кратчайший путь между k-> g может быть либо через h, i или j

[РЕДАКТИРОВАТЬ: в этом случае все мои веса равныдо 1, но я использую веса в моей системе с более сложными графиками. Мне просто нужен был очень простой пример, чтобы объяснить ...]

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

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

Любая помощь будет высоко ценится! Спасибо

Жюльен

Answer 1

хорошо, так что это очень далеко от изящного, но достаточно хорошее решение, которое я нашел, вместо того, чтобы модифицировать сам алгоритм (который для меня все еще напоминает Эверест, хотя я провел всю ночь, изучая код подробно!):

1) запустить алгоритм несколько раз с одними и теми же переменными, за исключением:

2) каждый раз, когда список графиков поворачивается на один шаг

[[a, b, 1],[b, c, 1],[c, a, 1]]
[[b, c, 1],[c, a, 1],[a, b, 1]]
[[c, a, 1],[a, b, 1],[b, c, 1]]

... и т. Д. для больших графиков

3) то же самое, но также и с обратным графиком

[[c, a, 1],[b, c, 1],[a, b, 1]]
[[b, c, 1],[a, b, 1],[c, a, 1]] 
[[a, b, 1],[c, a, 1],[b, c, 1]] 

... то же самое

4) сбор всех этих решений, затем удаление дубликатов.

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

Таким образом, я получаю все кратчайшие путиЯ хочу, за исключением одного случая: когда веса не равны в «эквивалентных сегментах» между двумя узлами - под эквивалентом я подразумеваю одинаковое количество узлов между ними.

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

Спасибо всем за ваши предложения! Бест,

Жюльен