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

本文介绍了找到两个节点之间的最短路径（顶点）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I have a list of interconnected edges (E), how can I find the shortest path connecting from one vertex to another?

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

I am thinking about using lowest common ancestors, but the edges don't have a clearly defined root, so I don't think the solution works.

最短路径由所经过的最小顶点数定义。

Shortest path is defined by the minimum number of vertexes traversed.

注意：可能有一个连接两个顶点的多路径，所以明显的广度优先搜索将无法正常工作

推荐答案

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

I'm not sure if you need a path between every pair of nodes or between two particular nodes. Since someone has already given an answer addressing the former, I will address the latter.

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

If you don't have any prior knowledge about the graph (if you do, you can use a heuristic-based search such as A*) then you should use a breadth-first search.