1

首先，我想确保结构正确。据我所知，表示图形的邻接列表如下所示：

相邻列表

AdjList 是一个 ArrayList，其中每个元素都是一个对象。每个对象内部都包含一个 ArrayList 来表示连接的顶点。例如，在上图中，Vertext 1（AdjList 中的第一个索引）连接到 AdjList 的索引 2、4 和 5 处的顶点。这种邻接表的表示是否正确？（ps：我知道索引从 0 开始，为了简单/方便，我把 1 放在这里）。

如果正确，我应该使用哪种算法来找到两个顶点之间的最短路径？

4

4 回答 4

4

没有算法可以只为您提供两个顶点之间的最短路径。您可以使用：

  1. Dijkstra 算法找到一个顶点和所有其他顶点之间的最短路径（然后选择你需要的那个）。
  2. Roy-Floyd 算法找到所有可能的顶点对之间的最短路径。

这些链接还包括伪代码。

于 2011-12-17T19:52:13.527 回答
2

这是Dijkstra在 java 中的最短路径算法的示例以及解释

于 2011-12-17T19:52:01.007 回答
1

您可以使用 Dijkstra 和 Floyd Warshall。对于未加权的图，假设每条边的权重为 1 并应用该算法。

于 2012-07-11T08:12:39.120 回答
1

以前的答案提到了解决问题的 disjktra 和 floyd 算法并且是有效的解决方案，但是在图未加权的情况下，最好的解决方案是使用BFS技术，更简单且最优。

BFS 的算法复杂度为 O(n)，而 disjktra O(n * log(n)) 和 Floyd O(n^2)

于 2021-10-13T17:10:26.453 回答