Понимание результатов QuickGraph ShortestPathsDijkstra

Question

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

Это соответствующая часть графика, который у меня есть:

Теперь я делаю поиск dijkstra по документации Quickgraph:

//Build QuickGraph UndirectedGraph from our data
UndirectedGraph<int, Edge<int>> ug = g.CreateUndirectedQuickGraph();

Func<Edge<int>,double> weightFunc = (Edge<int> edge) =>
{
    return 1; //without weights at this moment
};

var tryGetPath = ug.ShortestPathsDijkstra(weightFunc, 20);

IEnumerable<Edge<int>> path;
if (tryGetPath(23, out path))
    foreach (var e in path)
        Trace.WriteLine(e);

Как вы видите, я пытаюсь получить кратчайший путь между узлами 20 и 23. И получаю вывод:

20 -> 4
22 -> 4
23 -> 22

Кажется, это вроде как правильно, но я не совсем понимаю, как извлечь из него путь к узлу. Я ожидал что-то вроде:

20 -> 4
4 -> 22
22 -> 23

Как я могу построить окончательный путь из этого вывода?

---

Пример получения от 20 до 34:

 20->3 
 5->3 
 8->5 
 9->8
 36->9
 36->11
 34->11

Обратите внимание, как 36->11 появляется перед последним краем.

Answer 1

Я не использовал этот конкретный алгоритм в QuickGraph, но это выглядит так ...

Поскольку вы используете неориентированный граф, алгоритм, вероятно, работает как задумано.

Для ненаправленного ребра A->B (на самом деле A-B) я думаю, что вы в равной степени можете описать ребро как B->A, и это следует считать эквивалентным.

ie, вы можете интерпретировать вывод как упорядочение ребер, а не упорядочение вершин.

---

Если бы вы могли добавить дополнительные узлы для вашего второго более длинного примера, возможно, мы можете проверить, полностью ли работает эта идея.