algorithm - 找到两个节点（顶点）之间的最短路径

Question

我有一个互连边列表 ( E)，如何找到从一个顶点连接到另一个顶点的最短路径？

我正在考虑使用最低共同祖先，但边缘没有明确定义的根，所以我认为该解决方案行不通。

最短路径由遍历的最小顶点数定义。

注意：可能存在连接两个顶点的多路径，因此显然广度优先搜索不起作用

Answer 1

Dijkstra 的算法将为您做到这一点。

Answer 2

我不确定您是否需要每对节点之间或两个特定节点之间的路径。由于有人已经给出了针对前者的答案，我将针对后者。

如果您对图没有任何先验知识（如果有，则可以使用基于启发式的搜索，例如A*），那么您应该使用广度优先搜索。

Answer 3

Floyd-Warshall算法可能是您的问题的解决方案，但也有其他解决方案可以解决所有对最短路径问题。

Answer 4

Shortest path is defined by the minimum number of vertexes treversed

它与最小边数加一相同。

您可以使用标准广度优先搜索，它会正常工作。如果您有多个连接两个顶点的路径，只需保存其中一个，它不会影响任何事情，因为每条边的权重都是 1。

Answer 5

额外的 2 美分。看看networkx。已经针对您的需要实施了一些有趣的算法，您可以选择最适合的。