Поиск кратчайшего пути с помощью Дейкстры с использованием кучи Фибоначчи?

Я реализовал C # Dijkstra с кучей Фибоначчи, используя SO вопрос и эту версию на Java, которая очень чистый, лаконичный и хорошо документированный.

Я изменил DirectedGraph, чтобы сделать его неориентированным графом.

Однако у меня есть 2 вопроса по самому алгоритму поиска:

  1. Текущий метод имеет 2 параметра (график и источник). Если я добавлю третий параметр (цель), какие изменения необходимы в самом алгоритме поиска, чтобы он искал только от источника к цели, а не по всем парам кратчайших путей?

  2. Функция возвращает список расстояний. Что мне нужно изменить, чтобы он возвращал кратчайший путь?


java c# shortest-path dijkstra
person Ivan-Mark Debono    schedule 23.05.2016    source источник
comment
Я не понимаю первый вопрос, но № 2 в качестве списка расстояний кратчайший путь - это список с наименьшим количеством, или вы имеете в виду, что хотите, чтобы он возвращал только один путь без проверки других путей? с помощью весов?.   -  person Xela    schedule 23.05.2016
comment
@Xela Обычно при использовании Dijkstra узлы, составляющие кратчайший путь, добавляются в список, причем целевой узел является первой записью. Затем, чтобы получить кратчайший путь, нужно вернуться к этому списку. Но текущая реализация имеет только переменную result, которая содержит все узлы, некоторые с весами, а большинство других с +бесконечностью.   -  person Ivan-Mark Debono    schedule 23.05.2016