如何通过ShortestPathsDijkstra获取遍历全部节点的最优路径？

核心问题拆解 #

你使用ShortestPathsDijkstra只能查询单终点路线，但需要遍历所有节点的完整最优路径，且调试时发现Target.predecessors存在数据却无法直接访问。

可行解决方案 #

1. 利用返回的路径查询函数批量生成所有节点路径 #

ShortestPathsDijkstra返回的是Func<TVertex, IEnumerable<TVertex>>类型的委托，你可以遍历所有节点，逐个调用该委托获取每个节点到起点的最优路径，再整合结果：

// 假设图为UndirectedGraph<int, Edge<int>>类型，起点为startNode
var shortestPaths = graph.ShortestPathsDijkstra(e => e.Weight, startNode);
var allPaths = new Dictionary<int, IEnumerable<int>>();

foreach (var node in graph.Vertices)
{
    if (shortestPaths(node) is IEnumerable<int> path)
    {
        allPaths[node] = path.Reverse(); // 反转后得到从起点到该节点的路径
    }
}

20个节点的规模下，这种逐个查询的方式完全不会有性能问题，无需纠结效率。

2. 直接访问前驱节点集合（推荐） #

ShortestPathsDijkstra的内部前驱节点字典是私有成员，无法直接访问，但可以改用DijkstraShortestPathAlgorithm类，它暴露了Predecessors属性，能直接获取所有节点的前驱关系，进而构建完整路径：

var dijkstra = new DijkstraShortestPathAlgorithm<int, Edge<int>>(graph, e => e.Weight);
dijkstra.Compute(startNode);

// 遍历所有节点，通过前驱关系构建路径
var allPaths = new Dictionary<int, List<int>>();
foreach (var node in graph.Vertices)
{
    var path = new List<int>();
    var current = node;
    while (dijkstra.Predecessors.ContainsKey(current) && dijkstra.Predecessors[current] != null)
    {
        path.Add(current);
        current = dijkstra.Predecessors[current];
    }
    path.Add(startNode);
    path.Reverse();
    allPaths[node] = path;
}

这种方法无需逐个调用查询函数，直接获取所有前驱数据，更贴合你的需求。

3. 旅行商问题补充建议 #

针对20个节点的TSP，在获取每个起点的单源最短路径后，可结合动态规划求解最优回路，这部分属于TSP核心逻辑，和当前QuickGraph的API问题无关，此处不展开。

总结 #

• 小规模场景下，用返回的委托逐个查询完全可行，性能影响可忽略
• 要直接获取所有前驱关系，需改用DijkstraShortestPathAlgorithm类而非ShortestPathsDijkstra扩展方法
• 调试时看到的predecessors是内部私有成员，无法直接访问，必须通过官方提供的API或类属性获取

内容的提问来源于stack exchange，提问作者Roberto Yglesias