无权图中邻接表中的java最短路径

Question

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

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

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

Answer 1

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

1. Dijkstra's algorithm查找一个顶点和所有其他顶点之间的最短路径（然后选择所需的一个）
2. Roy-Floyd algorithm查找所有可能的顶点对之间的最短路径

这些链接还包括伪代码

Answer 2

你可以用Dijkstra's和Floyd Warshall。对于未平滑图，假设每条边的权重为1，并应用该算法

Answer 3

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

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

Answer 4

下面是java中Dijkstra's shortest path算法的一个示例以及说明