当前位置：首页 > news >正文

图的最短路径算法-迪杰斯特拉（Dijkstra）算法与弗洛伊德（Frolyd）算法

news 2024/11/5 0:44:18

一、最短路径算法（Shortest Path）

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

最短路径不一定是经过边最少的路径，但在这些最短路径中，长度最短的那一条路径上只有一条边，且它的权值在从源点出发的所有边的权值最小。

算法具体的形式包括：

确定起点的最短路径问题：也叫单源最短路问题，即已知起始结点，求最短路径的问题。在边权非负时适合使用Dijkstra算法，若边权为负时则适合使用Bellman-ford算法或者SPFA算法。
确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。
全局最短路径问题：也叫多源最短路问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、SPFA算法（Bellman-Ford算法的改进版本）、Floyd-Warshall算法、Johnson最短路算法。

二、迪杰斯特拉（Dijkstra）算法

迪杰斯特拉（Dijkstra）算法是由荷兰计算机科学家艾兹赫尔·韦伯·迪杰斯特拉（Edsger Wybe Dijkstra），又译艾兹赫尔·韦伯·戴克斯特拉于1959年提出的，因此又叫戴克斯特拉。

Dijkstra 算法是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
在这里插入图片描述

1. 算法思想

迪杰斯特拉算法的主要思想是通过不断更新顶点之间的最短路径，逐步找到从指定起点到各个顶点的最短路径。该算法以贪心策略为基础，在每一步选择当前最优的顶点，并根据该顶点更新其他顶点的距离值，确保已确定的最短路径不再被修改。通过反复进行这样的选择和更新，最终得到了从起点到所有其他顶点的最短路径。

总的来说，迪杰斯特拉算法的思想就是以逐步迭代的方式，通过不断选择当前最优的顶点，更新其他顶点的距离值，直至得到起点到各个顶点的最短路径。

2. 算法步骤

初始化： 创建一个集合 final 存放所有已知实际最短路径值的顶点，将本次最短路径的源点（起点） $v_0$ 插入在集合 final 中；创建一个数组 dist 存放最短距离数组，记录每个顶点到起点的最短距离，设置 dist 初始值，若源点 $v_0$ 与 $v_i$ 之间有弧，则 dist[i] 设置为弧上的权值，否则标记为 $\infty$ ；创建数组 path 表示从源点 $v_0$ 到顶点 $v_i$ 之间的最短路径的前驱结点，如果其没有前驱结点被选取，则初始化为-1。
选取起点： 在图的顶点集合中，找到还没确定最短路径，且dist 最小的顶点 $v_i$ ，将其移动到集合 final 中。
更新距离： 对于当前确定最短路径的顶点，遍历其所有相邻顶点，如果通过当前顶点 $v_i$ 到达相邻顶点的距离小于相邻顶点当前记录的最短距离，则更新相邻顶点的最短距离为新的距离值，同时记录相邻顶点更新后的前驱。
迭代计算： 重复步骤2和步骤3，直到所有顶点都插入到集合 final 中。
返回结果： 最终得到起点到每个顶点的最短路径。

3. 算法案例

对如下图，以 $v_0$ 为源点的Dijkstra算法计算最短路径的流程如下：
在这里插入图片描述
（1）初始化

如上图所示，以 $v_0$ 为Dijkstra算法的源点，首先在 final 数组中标记 $v_0$ ，并初始化dist和path数组 $d i s t [0] = 0$ 、 $p a t h [0] = - 1$ ；
然后计算其余4个节点到源点 $v_0$ 的距离并存入 dist 数组中，其中 $v_1$ 与 $v_0$ 边的权值为 10， $v_4$ 到 $v_0$ 边的权值为 5， $v_2$ 、 $v_3$ 顶点与源点 $v_0$ 不相邻，所以数组中 $d i s t [1] = 10$ 、 $dist[2]=\infty$ 、 $dist[3]=\infty$ 、 $d i s t [4] = 5$ ；
最后设置 path 数组的值， $v_1$ 和 $v_4$ 的前驱节点是 $v_0$ ，所以 $p a t h [1] = 0$ 、 $p a t h [4] = 0$ ，而 $v_2$ 、 $v_3$ 顶点与源点 $v_0$ 不相邻，所以前驱结点初始化为 $p a t h [2] = - 1$ 、 $p a t h [3] = - 1$ 。

（2）迭代计算

第一轮迭代：

第一轮迭代首先根据初始化时的 dist 数组，确定了 $v_4$ 与源点 $v_0$ 的距离 $d i s t [4]$ 最短，所以将 $v_4$ 作为第一轮迭代的顶点。将顶点 $v_4$ 填入到 final 集合中，并更新 dist 数组和 path 数组， $v_4$ 与源点 $v_0$ 的距离为5，所以 $d i s t [4] = 5$ ，此时 $v_4$ 的前驱节点为 $v_0$ ，故 $p a t h [4] = 0$ ；
最后重新计算其余三个顶点 $v_1$ 、 $v_2$ 、 $v_3$ 与源点 $v_0$ 的距离并更新 dist 和 path 数组， $v_1$ 与源点 $v_0$ 的距离在路径为 $v_0 \to v_4 \to v_1$ 的路径下是8（5+3），故更新 $d i s t [1] = 8$ ， $p a t h [1] = 4$ ； $v_2$ 与源点 $v_0$ 的距离在路径为 $v_0 \to v_4 \to v_2$ 的路径下是14（5+9），故更新 $d i s t [2] = 14$ ， $p a t h [2] = 4$ ； $v_3$ 与源点 $v_0$ 的距离在路径为 $v_0 \to v_4 \to v_3$ 的路径下是7（5+2），故更新 $d i s t [3] = 7$ ， $p a t h [3] = 4$ 。
在这里插入图片描述

第二轮迭代：

第二轮迭代首先根据第一轮迭代时的 dist 数组，确定了 $v_3$ 与源点 $v_0$ 的距离 $d i s t [3]$ 最短，所以将 $v_3$ 作为第二轮迭代的顶点。将顶点 $v_3$ 填入到 final 集合中，并更新 dist 数组和 path 数组， $v_3$ 与源点 $v_0$ 的距离为7，所以 $d i s t [3] = 7$ ，此时 $v_3$ 的前驱节点为 $v_4$ ，故 $p a t h [3] = 4$ ；
最后重新计算其余二个顶点 $v_1$ 、 $v_2$ 与源点 $v_0$ 的距离并更新 dist 和 path 数组， $v_1$ 与源点 $v_0$ 的距离在路径为 $v_0 \to v_4 \to v_1$ 的路径下是8（5+3），故更新 $d i s t [1] = 8$ ， $p a t h [1] = 4$ ； $v_2$ 与源点 $v_0$ 的距离在路径为 $v_0 \to v_4 \to v_3 \to v_2$ 的路径下是13（5+2+6），故更新 $d i s t [2] = 13$ ， $p a t h [2] = 3$ 。
在这里插入图片描述

第三轮迭代：
第三轮迭代首先根据第二轮迭代时的 dist 数组，确定了 $v_1$ 与源点 $v_0$ 的距离 $d i s t [1]$ 最短，所以将 $v_1$ 作为第二轮迭代的顶点。将顶点 $v_1$ 填入到 final 集合中，并更新 dist 数组和 path 数组， $v_1$ 与源点 $v_0$ 的距离为8，所以 $d i s t [1] = 7$ ，此时 $v_1$ 的前驱节点为 $v_4$ ，故 $p a t h [1] = 4$ ；
最后重新计算最后一个顶点 $v_2$ 与源点 $v_0$ 的距离并更新 dist 和 path 数组， $v_2$ 与源点 $v_0$ 的距离在路径为 $v_0 \to v_4 \to v_1 \to v_2$ 的路径下是9（5+2+6），故更新 $d i s t [2] = 9$ ， $p a t h [2] = 1$ 。
在这里插入图片描述
第四轮迭代：
第四轮迭代时，将最后一个顶点 $v_2$ 填入到 final 集合中。

（3）返回结果
源点 $v_0$ 到 $v_1$ 的最短(带权)路径⻓度为： $d i s t [1] = 8$ ，通过 path可知， $v_0$ 到 $v_1$ 的最短(带权)路径： $v_0 \to v_4 \to v_1$ ；

源点 $v_0$ 到 $v_2$ 的最短(带权)路径⻓度为： $d i s t [2] = 9$ ，通过 path可知， $v_0$ 到 $v_2$ 的最短(带权)路径： $v_0 \to v_4 \to v_1 \to v_2$ ；

源点 $v_0$ 到 $v_3$ 的最短(带权)路径⻓度为： $d i s t [3] = 7$ ，通过 path可知， $v_0$ 到 $v_3$ 的最短(带权)路径： $v_0 \to v_4 \to v_3$ ；

源点 $v_0$ 到 $v_4$ 的最短(带权)路径⻓度为： $d i s t [4] = 5$ ，通过 path可知， $v_0$ 到 $v_4$ 的最短(带权)路径： $v_0 \to v_4$ 。

4.代码实现（Java）

    /***  @descript 最短路径算法：dijkstra算法*  @param start*/public int[] dijkstra(int start) {// 初始化boolean[] shortestPathSet = new boolean[vertexList.size()]; // 存放所有已知实际最短路径值的顶点,true代表已知其最短路径int[] path = new int[vertexList.size()]; // 表示从源点到顶点之间的最短路径的前驱结点int[] dist = new int[vertexList.size()]; // 表示从源点到顶点之间的弧上的权值for (int i = 0; i < vertexList.size(); i++) {shortestPathSet[i] = false; // 顶点i的最短路径还没获取到。path[i] = 0;  // 顶点i的前驱顶点为0。dist[i] = arcs[start][i]==0 ? INF : arcs[start][i];  // 顶点i的最短路径为起点到顶点i的权值}shortestPathSet[start] = true;dist[start] = 0;// 迭代计算最短路径int k=0;for (int i = 1; i < vertexList.size(); i++) {// 寻找当前最小的路径；// 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。int min = INF;for (int j = 0; j < vertexList.size(); j++) {if (!shortestPathSet[j] && dist[j]<min) {min = dist[j];k = j;}}shortestPathSet[k] = true; // 第k个顶点已找到最短路径// 更新最短路径dist和前驱顶点pathfor (int j = 0; j < vertexList.size(); j++) {if (!shortestPathSet[j]&& arcs[k][j] != 0 && min!=INF && (min + arcs[k][j] < dist[j]) ) {dist[j] = (arcs[k][j]==INF ? INF : (min + arcs[k][j]));path[j] = k;}}}// 打印最短路径和最短路径长度for (int i = 0; i < vertexList.size(); i++) {if (i != start) {System.out.print("Shortest Path of "+ vertexList.get(start) +" to " + vertexList.get(i)+ " : " + dist[i]+"\t");int index = i;Stack<Integer> stack = new Stack<>();stack.push(index);while (path[index] != start) {stack.push(path[index]);index = path[index];}stack.push(start);while (!stack.isEmpty()) {System.out.print(vertexList.get(stack.pop()));if (!stack.isEmpty()) {System.out.print("->");}}System.out.println();}}return dist;}

注意事项：

边上带有负权值时，Dijkstra 算法并不适用。若允许边上带有负权值，则在与final（已求得最短路径的顶点集，归入final内的结点的最短路径不再变更）内某点（记为a）以负边相连的点（记为b）确定其最短路径时，其最短路径长度加上这条负边的权值结果可能小于a原先确定的最短路径长度，而此时a 在 Diikstra 算法下是无法更新的。

三、弗洛伊德（Frolyd）算法

弗洛伊德（Floyd-Warshall，Floyd ）算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德（Robert W. Floyd）命名。

Floyd 算法以动态规划为基础，该算法通过不断更新顶点之间的最短路径长度，以找到任意两个顶点之间的最短路径长度。

1. 算法思想

弗洛伊德算法的算法思想是通过动态规划的方式来求解图中所有点对之间的最短路径。该算法的核心思想是利用一个中间顶点集合，逐步缩小这个集合的规模，更新并维护每对顶点之间的最短路径长度。

具体而言，弗洛伊德算法通过多次迭代，尝试在已知顶点之间的最短路径基础上，考虑添加一个新的中间顶点后是否可以缩短路径长度。如果存在更短的路径，就更新当前已知的最短路径长度；否则保持原状。不断重复这个过程，最终得到所有点对之间的最短路径长度矩阵。

弗洛伊德算法的动态规划思想在于利用已知的最短路径信息来推导出更长路径的最短路径，通过不断更新和迭代，最终得到所有顶点之间的最短路径长度。在图中，分别计算不允许在其他顶点中转的最短路径、以其中某一个顶点作为中转的最短路径、以其中某两个顶点作为中转的最短路径等等，直到迭代计算出以所有顶点都可以作为中转顶点情况下的最短路径。

2. 算法步骤

初始化： 创建一个二维数组 A，其中 $A [i] [j]$ 表示顶点 $v_i$ 到顶点 $v_j$ 的最短路径长度。将 $A [i] [j]$ 初始化为连接顶点 $v_i$ 和 $v_j$ 的边的权重。如果不存在直接相连的边，则将 $A [i] [j]$ 初始化为无穷大 $\infty$ 。
更新最短路径： 对于每对顶点 $v_i$ 和 $v_j$ ，遍历所有顶点 $v_k$ ，比较通过顶点 $v_k$ 是否可以使顶点 $v_i$ 和 $v_j$ 的路径变得更短，即检查 $A [i] [k] + A [k] [j]$ 是否小于当前已知的 $A [i] [j]$ ，如果是，则更新 $A [i] [j] = A [i] [k] + A [k] [j]$ 。（此过程即在前一轮迭代计算的基础上，新增顶点 $v_k$ 作为计算最短距离的可中转点）
迭代计算： 重复执行步骤2，直到所有顶点对之间的最短路径长度都被计算出来。
返回结果： 最终得到所有点对之间的最短路径长度矩阵。

3. 算法案例

对如下图，Frolyd算法计算最短路径的流程如下：
在这里插入图片描述
（1）初始化

算法初始化，在矩阵（二维数组）中根据图中边的权值注入属性值，若两顶点不相邻，则置为 $\infty$ 。
在这里插入图片描述
（2）迭代计算

第一轮

第一轮为当选取顶点 $v_0$ 作为中转，即 $k = 0$ 。
遍历每两个顶点之间的距离，依次比较其与以顶点 $v_0$ 作为中转后的距离，发现在以 $v_0$ 和 $v_1$ 作为中转后：
所有顶点之间的距离都没有找到更短的路径，所以矩阵 A 和 path 不变。
在这里插入图片描述
第二轮

第二轮为当选取顶点 $v_0$ 和 $v_1$ 作为中转，即 $k = 1$ 。
遍历每两个顶点之间的距离，依次比较其与以顶点 $v_0$ 和 $v_1$ 作为中转后的距离，发现在以 $v_0$ 和 $v_1$ 作为中转后：
顶点 $v_2$ 和 $v_3$ 在路径 $v_2 \to v_1 \to v_3$ 的距离是2（1+1），而 $v_2$ 和 $v_3$ 不连通，所以 $A [2] [3] = 2$ ， $p a t h [2] [3] = 1$ ；
顶点 $v_2$ 和 $v_4$ 在路径 $v_2 \to v_1 \to v_4$ 的距离是6（1+5），小于当前已知的的最短距离 $A [2] [4] = 7$ ，即 $A [2] [1] + A [1] [4] < A [2] [4]$ ，所以更新最短路路径 $A [2] [4] = 6$ ， $p a t h [2] [3] = 1$ 。
在这里插入图片描述
第三轮

第三轮为当选取顶点 $v_0$ 、 $v_1$ 和 $v_2$ 作为中转，即 $k = 2$ 。
遍历每两个顶点之间的距离，依次比较其与以顶点 $v_0$ 、 $v_1$ 和 $v_2$ 作为中转后的距离，发现在以 $v_0$ 、 $v_1$ 和 $v_2$ 作为中转后：
顶点 $v_0$ 和 $v_1$ 在路径 $v_0 \to v_2 \to v_1$ 的距离是2（1+1），而 $v_0$ 和 $v_1$ 不连通，所以 $A [0] [1] = 2$ ， $p a t h [0] [1] = 2$ ；
顶点 $v_0$ 和 $v_3$ 在路径 $v_0 \to v_2 \to v_1 \to v_3$ 的距离是3（1+1+1），而 $v_0$ 和 $v_3$ 不连通，所以 $A [0] [3] = 3$ ， $p a t h [0] [3] = 2$ ；
顶点 $v_0$ 和 $v_4$ 在路径 $v_0 \to v_2 \to v_1 \to v_4$ 的距离是7（1+1+5），小于当前已知的的最短距离 $A [0] [4] = 10$ ，即 $A [0] [2] + A [2] [4] = A [0] [2] + A [2] [1] + A [1] [4] < A [0] [4]$ ，所以更新最短路路径 $A [0] [4] = 7$ ， $p a t h [0] [4] = 2$ 。
在这里插入图片描述

第四轮

第四轮为当选取顶点 $v_0$ 、 $v_1$ 、 $v_2$ 和 $v_3$ 作为中转，即 $k = 3$ 。
遍历每两个顶点之间的距离，依次比较其与以顶点 $v_0$ 、 $v_1$ 、 $v_2$ 和 $v_3$ 作为中转后的距离，发现在以 $v_0$ 、 $v_1$ 、 $v_2$ 和 $v_3$ 作为中转后：
顶点 $v_1$ 和 $v_4$ 在路径 $v_1 \to v_3 \to v_4$ 的距离是2（1+1），小于当前已知的的最短距离 $A [1] [4] = 5$ ，即 $A [1] [3] + A [3] [4] < A [1] [4]$ ，所以更新最短路路径 $A [1] [4] = 2$ ， $p a t h [1] [4] = 3$ 。
在这里插入图片描述
第五轮

第五轮为当选取顶点 $v_0$ 、 $v_1$ 、 $v_2$ 、 $v_3$ 和 $v_4$ 作为中转，即 $k = 4$ 。
遍历每两个顶点之间的距离，依次比较其与以顶点 $v_0$ 、 $v_1$ 、 $v_2$ 、 $v_3$ 和 $v_4$ 作为中转后的距离，发现在以 $v_0$ 、 $v_1$ 、 $v_2$ 、 $v_3$ 和 $v_4$ 作为中转后：
所有顶点之间的距离都没有找到更短的路径，所以矩阵 A 和 path 不变。
在这里插入图片描述
（3）返回结果
$v_0$ 到 $v_1$ 最短路径长度为 $A [0] [1] = 2$ ，路径为 $v_0 \to v_2 \to v_1$ ；
$v_0$ 到 $v_2$ 最短路径长度为 $A [0] [2] = 1$ ，路径为 $v_0 \to v_2$ ；
$v_0$ 到 $v_3$ 最短路径长度为 $A [0] [3] = 3$ ，路径为 $v_0 \to v_2 \to v_1 \to v_3$ ；
$v_0$ 到 $v_4$ 最短路径长度为 $A [0] [4] = 4$ ，路径为 $v_0 \to v_2 \to v_1 \to v_4$ ；
$v_1$ 到 $v_3$ 最短路径长度为 $A [1] [3] = 1$ ，路径为 $v_1 \to v_3$ ；
$v_1$ 到 $v_4$ 最短路径长度为 $A [1] [4] = 2$ ，路径为 $v_1 \to v_3 \to v_4$ ；
$v_2$ 到 $v_1$ 最短路径长度为 $A [2] [1] = 1$ ，路径为 $v_2 \to v_1$ ；
$v_2$ 到 $v_3$ 最短路径长度为 $A [2] [3] = 2$ ，路径为 $v_2 \to v_1 \to v_3$ ；
$v_2$ 到 $v_4$ 最短路径长度为 $A [2] [4] = 3$ ，路径为 $v_2 \to v_1 \to v_4$ ；
$v_3$ 到 $v_4$ 最短路径长度为 $A [3] [4] = 1$ ，路径为 $v_3 \to v_4$ 。

3.代码实现（Java）

    /***  @descript 最短路径算法：Floyd算法*/public int[][] floyd() {// 初始化int[][] dist = new int[vertexNumber][vertexNumber]; // 矩阵 作为距离int[][] path = new int[vertexNumber][vertexNumber]; // 前驱结点for (int i = 0; i < vertexNumber; i++) {for (int j = 0; j < vertexNumber; j++) {dist[i][j] = arcs[i][j]==0 ? INF: arcs[i][j];}}// 动态规划思想迭代计算for (int k = 0; k < vertexNumber; k++) {for (int i = 0; i < vertexNumber; i++) {for (int j = 0; j < vertexNumber; j++) {if (arcs[i][k] != 0 && arcs[k][j] != 0) {dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); // 更新递推公式}}}}// 打印for (int i = 0; i < vertexNumber; i++) {for (int j = 0; j < vertexNumber; j++) {if (i != j && arcs[i][j] != 0) {System.out.println("Shortest Path of " + vertexList.get(i) + " to " + vertexList.get(j) + " : " + dist[i][j]);}}}return dist;}

注意事项：

Frolyd 算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。

四、完整测试代码

本文实现代码地址：
https://github.com/helloWorldchn/DataStructure

package graph;import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Queue;
import java.util.Stack;// 邻接矩阵
public class AdjacencyMatrixGraph {ArrayList<String> vertexList; //存储顶点集合int[][] arcs; // 邻接矩阵int vertexNumber; // 图的当前顶点的数目int edgeNumber; // 图的当前边的数目// 初始化public AdjacencyMatrixGraph(int maxVertex) {vertexList = new ArrayList<String>(maxVertex);arcs = new int[maxVertex][maxVertex];vertexNumber = 0;edgeNumber = 0;for (int i = 0; i < maxVertex; i++) {for (int j = 0; j < maxVertex; j++) {arcs[i][j] = 0;}}}//插入顶点public void insertVertex(String vertex) {vertexList.add(vertex); // 把要插入的值添加到vertexList中即可。vertexNumber ++;System.out.println(vertex + " has been entered!");}/*** 添加边（a->b的边）* @param a * @param b* @param weight 权重（不带权的图即weight=1）*/public void insertEdge(int a, int b, int weight) {if(a < vertexNumber && b < vertexNumber) {if (arcs[a][b] == 0) {arcs[a][b] = weight; // 将权重添加到arcs[a][b]中即可System.out.println(vertexList.get(a)+"->"+vertexList.get(b)+" connect edge!");}edgeNumber ++;}}// 得到index顶点的第一个邻接结点的下标public int getFirstNeighbor(int index) {for (int j = 0; j < vertexNumber; j++) {if (arcs[index][j] > 0) { // arcs[index][j]即为第一个邻接点的权重
//            	System.out.println(vertexList.get(j) + " is the first neighbor");return j;}}return -1;}//根据前一个邻接结点的下标来获取下一个邻接结点public int getNextNeighbor (int a, int b) {for (int j = b+1; j < vertexNumber; j++) {if (arcs[a][j] > 0) { // arcs[a][j]即为下一个邻接点的权重
//            	System.out.println(vertexList.get(j) + " is the next neighbor");return j;}}     return -1;}// 返回结点对应的顶点值 0:"A" 1:"B" 2:"C" 3:"D" 4:"E"public String getValueByIndex(int index) {return vertexList.get(index);}// 获取a->b的权值public int getWeight(int a, int b) {return arcs[a][b];}/***  Deep First Search Algorithm: 深度优先搜索算法(dfs)*  @return: java.util.List<java.lang.String>*/public List<Object> deepFirstSearch() {return deepFirstSearch(0);}public List<Object> deepFirstSearch(int startIndex) {List<Object> dfsList = new ArrayList<Object>();boolean[] isVisited = new boolean[vertexList.size()]; // 定义给数组boolean[], 记录某个结点是否被访问//遍历所有的结点，进行dfs[回溯]for (int i = startIndex; i < vertexNumber+startIndex; i++) {int index = i%vertexNumber;if (!isVisited[index]) {deepFirstSearch(isVisited, index ,dfsList);}}return dfsList;}public void deepFirstSearch(boolean[] isVisited, int index, List<Object> dfsList) {dfsList.add(vertexList.get(index)); // 首先我们访问该结点,输出
//    	System.out.print(vertexList.get(index) + " "); // 首先我们访问该结点,输出isVisited[index] = true; // index已经在上一行被访问过了，所以变为true// 深度优先搜索，重复找第一个邻接节点，直到找不到了为止int w = getFirstNeighbor(index); // 得到index顶点的第一个邻接结点的下标while (w != -1) { // 如果有邻接顶点就循换，直到没有了为止if (!isVisited[w]) { // 如果w没被访问过deepFirstSearch(isVisited, w, dfsList);}// 如果w结点已经被访问过，说明一轮深度搜索已完成！寻找下一个邻接顶点w = getNextNeighbor(index, w);}}/***  Breadth First Search Algorithm: 广度优先搜索算法(bfs)*  @return: java.util.List<java.lang.Object>*/public List<Object> breadthFirstSearch() {return breadthFirstSearch(0);}public List<Object> breadthFirstSearch(int startIndex) {List<Object> bfsList = new ArrayList<Object>();boolean[] isVisited = new boolean[vertexList.size()]; // 定义给数组boolean[], 记录某个结点是否被访问isVisited = new boolean[vertexList.size()];//遍历所有的结点，依次进行bfsfor (int i = startIndex; i < vertexNumber+startIndex; i++) {int index = i%vertexNumber;if (!isVisited[index]) {breadthFirstSearch(isVisited, index, bfsList);}}return bfsList;}public void breadthFirstSearch(boolean[] isVisited, int index, List<Object> bfsList) {int u; // u代表队列的头结点对应的下标。int w; // w代表邻接节点Queue<Integer> queue = new ArrayDeque<>(); // 辅助队列bfsList.add(vertexList.get(index));
//    	System.out.print(vertexList.get(index) + " "); // 首先我们访问该结点,输出isVisited[index] = true; // index已经在上一行被访问过了，所以变为truequeue.add(index); // 使A进入队列// 对队列中的几个元素依次执行广度遍历while (!queue.isEmpty()) {u = queue.poll();// 取出队列的头w = getFirstNeighbor(u); // 得到第一个邻接点的下标while (w != -1) { // 如果有邻接顶点就循换，直到没有了为止if (!isVisited[w]) { // 如果w没被访问过//如果第一个邻接点未被访问则访问第一个邻接节点bfsList.add(getValueByIndex(w));
//                    System.out.print(getValueByIndex(w) + " ");isVisited[w] = true;queue.add(w);}// 如果w结点已经被访问过，寻找u的下一个邻接顶点。实现广度遍历w = getNextNeighbor(u, w);}}}// 显示图对应的矩阵public void display() {for (int i = 0; i < vertexNumber; i++) {System.out.print(vertexList.get(i)+"\t");}System.out.println();for (int i = 0; i < vertexNumber; i++) {for (int j = 0; j < vertexNumber; j++) {System.out.print(arcs[i][j] + "\t");}System.out.println();}}private static final int INF = Integer.MAX_VALUE;/***  @descript 最小生成树算法：prim算法*  @param: graph*/public void prim(int[][] graph) {int vertices = graph.length;int[] parent = new int[vertices]; // 用于存储最小生成树的父节点int[] key = new int[vertices]; // 用于存储顶点与最小生成树的最小权重boolean[] mstSet = new boolean[vertices]; // 用于记录顶点是否已加入最小生成树Arrays.fill(key, INF);  // 初始化所有顶点的权重为无穷大Arrays.fill(mstSet, false); // 初始化所有顶点均未加入最小生成树key[0] = 0; // 初始顶点的权重为0，即将其作为起始节点parent[0] = -1;  // 初始节点没有父节点// 依次加入(n-1)个顶点到最小生成树中for (int i = 0; i < vertices - 1; i++) {int u = minKey(key, mstSet, vertices); // 选择权重最小的顶点u加入最小生成树mstSet[u] = true;// 更新相邻顶点的权重和父节点信息for (int v = 0; v < vertices; v++) {if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {parent[v] = u;key[v] = graph[u][v];}}}// 打印最小生成树的边和权重System.out.println("Edge" + "\t" + "Weight");for (int i = 1; i < graph.length; i++) {if (parent[i] != -1) { // 避免打印起始节点的边System.out.println(vertexList.get(parent[i]) + " -> " + vertexList.get(i) + "\t" + graph[parent[i]][i]);}}}// 寻找权重最小的未加入最小生成树的顶点private int minKey(int[] key, boolean[] mstSet, int vertices) {int min = INF, minIndex = -1;for (int v = 0; v < vertices; v++) {if (!mstSet[v] && key[v] < min) {min = key[v];minIndex = v;}}return minIndex;}/***  @descript 最小生成树算法：kruskal算法*  @param graph*/public void kruskal(int[][] graph) {int vertices = graph.length;List<Edge> edges = new ArrayList<>(); // 用于存储图中的所有边// 将图的边存储在edges列表中for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {if (graph[i][j] != 0) {Edge edge = new Edge(i, j, graph[i][j]);  // 边的起点、终点和权值edges.add(edge);}}}// 按权重对边进行排序Collections.sort(edges, Comparator.comparingInt(e -> e.weight));int[] parent = new int[vertices]; // 用于存储每个顶点的父节点Arrays.fill(parent, -1);List<Edge> mst = new ArrayList<>();  // 用于存储最小生成树的边int edgeCount = 0;// 遍历所有边for (Edge edge : edges) {int x = find(parent, edge.src); // 查找边的起点的根节点int y = find(parent, edge.dest); // 查找边的终点的根节点// 如果边的两个顶点不在同一个连通分量中，则加入最小生成树if (x != y) {mst.add(edge);  // 将边加入最小生成树union(parent, x, y); // 合并两个顶点的连通分量edgeCount++;  // 增加边的数量if (edgeCount == vertices - 1) { // 已找到n-1条边，则退出循环break;}}}// 输出最小生成树的边和权重System.out.println("Edge" + "\t" + "Weight");for (Edge edge : mst) {System.out.println(vertexList.get(edge.src) + " -> " + vertexList.get(edge.dest) + "\t" +  edge.weight);}}// 查找顶点i的根节点private int find(int[] parent, int i) {if (parent[i] == -1) {return i; // 如果顶点i的父节点为-1，表示i是根节点}return find(parent, parent[i]); // 递归查找i的根节点}// 合并两个顶点x和y的连通分量private void union(int[] parent, int x, int y) {int rootX = find(parent, x);// 查找顶点x的根节点int rootY = find(parent, y);// 查找顶点y的根节点parent[rootX] = rootY; // 将顶点x的根节点的父节点设为顶点y的根节点}// 辅助类表示边的信息class Edge {int src;int dest;int weight;public Edge(int src, int dest, int weight) {this.src = src;this.dest = dest;this.weight = weight;}}/***  @descript 最短路径算法：dijkstra算法*  @param start*/public int[] dijkstra(int start) {// 初始化boolean[] shortestPathSet = new boolean[vertexList.size()]; // 存放所有已知实际最短路径值的顶点,true代表已知其最短路径int[] path = new int[vertexList.size()]; // 表示从源点到顶点之间的最短路径的前驱结点int[] dist = new int[vertexList.size()]; // 表示从源点到顶点之间的弧上的权值for (int i = 0; i < vertexList.size(); i++) {shortestPathSet[i] = false; // 顶点i的最短路径还没获取到。path[i] = 0;  // 顶点i的前驱顶点为0。dist[i] = arcs[start][i]==0 ? INF : arcs[start][i];  // 顶点i的最短路径为起点到顶点i的权值}shortestPathSet[start] = true;dist[start] = 0;// 迭代计算最短路径int k=0;for (int i = 1; i < vertexList.size(); i++) {// 寻找当前最小的路径；// 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。int min = INF;for (int j = 0; j < vertexList.size(); j++) {if (!shortestPathSet[j] && dist[j]<min) {min = dist[j];k = j;}}shortestPathSet[k] = true; // 第k个顶点已找到最短路径// 更新最短路径dist和前驱顶点pathfor (int j = 0; j < vertexList.size(); j++) {if (!shortestPathSet[j]&& arcs[k][j] != 0 && min!=INF && (min + arcs[k][j] < dist[j]) ) {dist[j] = (arcs[k][j]==INF ? INF : (min + arcs[k][j]));path[j] = k;}}}// 打印最短路径和最短路径长度for (int i = 0; i < vertexList.size(); i++) {if (i != start) {System.out.print("Shortest Path of "+ vertexList.get(start) +" to " + vertexList.get(i)+ " : " + dist[i]+"\t");int index = i;Stack<Integer> stack = new Stack<>();stack.push(index);while (path[index] != start) {stack.push(path[index]);index = path[index];}stack.push(start);while (!stack.isEmpty()) {System.out.print(vertexList.get(stack.pop()));if (!stack.isEmpty()) {System.out.print("->");}}System.out.println();}}return dist;}/***  @descript 最短路径算法：Floyd算法*/public int[][] floyd() {// 初始化int[][] dist = new int[vertexNumber][vertexNumber]; // 矩阵 作为距离int[][] path = new int[vertexNumber][vertexNumber]; // 前驱结点for (int i = 0; i < vertexNumber; i++) {for (int j = 0; j < vertexNumber; j++) {dist[i][j] = arcs[i][j]==0 ? INF: arcs[i][j];}}// 动态规划思想迭代计算for (int k = 0; k < vertexNumber; k++) {for (int i = 0; i < vertexNumber; i++) {for (int j = 0; j < vertexNumber; j++) {if (arcs[i][k] != 0 && arcs[k][j] != 0) {dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); // 更新递推公式}}}}// 打印for (int i = 0; i < vertexNumber; i++) {for (int j = 0; j < vertexNumber; j++) {if (i != j && arcs[i][j] != 0) {System.out.println("Shortest Path of " + vertexList.get(i) + " to " + vertexList.get(j) + " : " + dist[i][j]);}}}return dist;}public static void main(String[] args) {AdjacencyMatrixGraph adjacencyMatrixGraph = new AdjacencyMatrixGraph(5);adjacencyMatrixGraph.insertVertex("A");adjacencyMatrixGraph.insertVertex("B");adjacencyMatrixGraph.insertVertex("C");adjacencyMatrixGraph.insertVertex("D");adjacencyMatrixGraph.insertVertex("E");adjacencyMatrixGraph.insertEdge(0, 1, 15);adjacencyMatrixGraph.insertEdge(0, 4, 9);adjacencyMatrixGraph.insertEdge(1, 2, 3);adjacencyMatrixGraph.insertEdge(2, 3, 2);adjacencyMatrixGraph.insertEdge(3, 0, 11);adjacencyMatrixGraph.insertEdge(3, 1, 7);adjacencyMatrixGraph.insertEdge(4, 2, 21);adjacencyMatrixGraph.insertEdge(1, 0, 15);adjacencyMatrixGraph.insertEdge(4, 0, 9);adjacencyMatrixGraph.insertEdge(2, 1, 3);adjacencyMatrixGraph.insertEdge(3, 2, 2);adjacencyMatrixGraph.insertEdge(0, 3, 11);adjacencyMatrixGraph.insertEdge(1, 3, 7);adjacencyMatrixGraph.insertEdge(2, 4, 21);System.out.println("==========Adjacency Matrix==========");adjacencyMatrixGraph.display();
//		adjacencyMatrixGraph.getFirstNeighbor(1);
//		adjacencyMatrixGraph.getNextNeighbor(3, 0);System.out.println("============Deep First Search============");List<Object> dfsList = adjacencyMatrixGraph.deepFirstSearch(); // A B C D E System.out.println(dfsList);System.out.println("==========Breadth First Search===========");List<Object> bfsList = adjacencyMatrixGraph.breadthFirstSearch(); // A B E C DSystem.out.println(bfsList);System.out.println("============Prim============");adjacencyMatrixGraph.prim(adjacencyMatrixGraph.arcs);System.out.println("============Kruskal============");adjacencyMatrixGraph.kruskal(adjacencyMatrixGraph.arcs);System.out.println("============Dijkstra============");adjacencyMatrixGraph.dijkstra(0);System.out.println("============Floyd============");adjacencyMatrixGraph.floyd();/*  *		A	B	C	D	E	*	A	0	15	0	11	9	*	B	15	0	3	7	0	*	C	0	3	0	2	21	*	D	11	7	2	0	0	*	E	9	0	21	0	0	*/}
}