找到两个节点（顶点）之间的最短路径 [英] Find the shortest Path between two nodes (vertices)

问题描述

我有一个相互连接的边缘（电子），我怎么能找到从一个顶点连接到另一个最短路径？

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.

这篇关于找到两个节点（顶点）之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！