非加权图中邻接表中的最短路径
首先，我想确保我的结构正确。 据我所知，表示图的邻接列表如下所示：
AdjList 是一个 ArrayList，其中每个元素是一个对象。每个对象内部都包含一个ArrayList来表示连接的顶点。例如，在上图中，顶点 1（AdjList 中的第一个索引）连接到 AdjList 索引 2、4 和 5 处的顶点。这种邻接表的表示方式正确吗？ （ps：我知道索引从 0 开始，为了简单起见，我在这里放 1）。
如果正确，我应该使用哪种算法来找到两个顶点之间的最短路径？
First, I would like to make sure I got the structure correct.
As far as I know, an adjacency list representing a graph looks like this:
AdjList is an ArrayList, where each element is an object. Each object contains an ArrayList inside to represent vertices connected. So for example, in the image above, Vertext 1 (first index in the AdjList) is connected to the vertex at index 2, 4, and 5 of the AdjList. Is this representation of an adjacency list correct? (ps: I know indices start at 0, i put 1 here for simplicity/ease).
If it is correct, which algorithm should I use to find the shortest path between two vertices?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
没有算法可以只给出两个顶点之间的最短路径。您可以使用以下任一方法：
这些链接还包括伪代码。
There is no algorithm to give you just the shortest path between two vertices. You can use either:
The links also include pseudocode.
这是 Java 中 Dijkstra 的最短路径 算法的示例以及解释
Here's an example for Dijkstra's shortest path algorithm in java along with explanations
您可以使用 Dijkstra 和 Floyd Warshall。对于未加权图，假设每条边的权重为 1 并应用该算法。
You can use Dijkstra's and Floyd Warshall. For unweighed graph assume weight of each edge to be 1 and apply the algorithm.
之前的答案提到了 disjktra 和 floyd 算法来解决问题，并且是有效的解决方案，但是在图表未加权的情况下，最好的解决方案是使用 BFS技术，更简单、最优。
BFS 的算法复杂度为 O(n)，而 disjktra O(n * log(n)) 和 Floyd O(n^2)
Previous answers mention disjktra and floyd algorithms to resolve the problem and are valid solutions, but where the graph is unweighted, the best solution is use a BFS technique, simpler and optimal.
BFS has a algorithm complexity of O(n), while disjktra O(n * log(n)) and Floyd O(n^2)