我有一个互连边的列表（ E ），如何找到从一个顶点连接到另一个顶点的最短路径？
我正在考虑使用lowest common ancestors，但边缘不要认为解决方案有效 .
最短路径由遍历的最小顶点数定义 .
注意：可能存在连接两个顶点的多路径，因此显然广度优先搜索将不起作用
我有一个互连边的列表（ E ），如何找到从一个顶点连接到另一个顶点的最短路径？
我正在考虑使用lowest common ancestors，但边缘不要认为解决方案有效 .
最短路径由遍历的最小顶点数定义 .
注意：可能存在连接两个顶点的多路径，因此显然广度优先搜索将不起作用
5 回答
我不确定你是否需要在每对节点之间或两个特定节点之间的路径 . 既然某人已经给出了解决前者的答案，我会解释后者 .
如果您没有关于图形的任何先验知识（如果您这样做，您可以使用基于启发式的搜索，例如A*），那么您应该使用breadth-first search .
Dijkstra的算法将为您完成此任务 .
Floyd-Warshall算法可能是您问题的可能解决方案，但也有other solutions来解决所有对最短路径问题 .
它与最小边数加1相同 .
您可以使用标准广度优先搜索，它将正常工作 . 如果你有多个连接两个顶点的路径，只需保存其中一个顶点就不会影响任何东西，因为每个边的权重都是1 .
额外2美分 . 看看networkx . 有一些有趣的算法已经实现了你需要的东西，你可以选择最适合的 .