Java利用Dijkstra和Floyd分别求取图的最短路径
短信预约 -IT技能 免费直播动态提醒
本文详细介绍了图的最短路径的概念，然后介绍了求最短路径的两种算法：Dijkstra算法和Floyd算法的原理，最后提供了基于邻接矩阵和邻接表的图对两种算法的Java实现。
阅读本文需要一定的图的基础，如果对于图不是太明白的可以看看这篇文章：Java数据结构之图的原理与实现。
1 最短路径的概述
在生活中，图形结构的应用是最广泛的。比如常见的交通路线选择，站点可以看作顶点，站点之间如果有路径，则算作两点之间的边或者弧，站点之间的通行时间，可以看作边或者弧的权值。
上图就是生活中出行路线的选择映射到图形结构的案例。顶点作为站点，站点之间能够到达则拥有边，站点的之间的通行时间则是边的权值。
对于出行路线的选择，不同的人有不同的选择。其中有一种很常见的选择是要求出发地和目的地之间的总通行时间最短，而不在乎中途到底有几站。毕竟通行时间对于很多人来说是宝贵的！
这样的问题转转换为数学模型，就是求带权图的最短路径，就是求带权图形两顶点之间的权值最小的路径。即如果从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和（称为路径长度）达到最小。
实际上最短路径有两重含义，一个两顶点之间的路径数量最少，另一个是两顶点之间的路径距离最短，本次主要解决路径距离最短的问题，即最小权值和。常见的解决算法一般是两种，迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd)算法。
2 杰斯特拉（Dijkstra）算法
2.1 原理
迪杰斯特拉（Dijkstra）算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是寻找给定的加权图中指定顶点间最短路径问题的算法
Dijkstra算法并不是一下子就求出了起点到终点的最短路径，而是采用的是贪心算法策略，一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到起点和终点的最短路径。
通用步骤如下：
1.指定两个集合S和U。S的作用是记录已求出最短路径的顶点，而U则是记录还未求出最短路径的顶点，以及这些顶点到起始顶点的权。
2.指定一个起始顶点A，存入集合S中，其他顶点以及到顶点A的权存入集合U中，从U中找出并移除路径最短的顶点B，并将其加入到S中，并且更新U中对应的路径权值（更新源点将新加入节点作为中间节点到达其它节点的距离）；重复该操作直到遍历所有顶点，此时S中的集合就是起点A到其他各个顶点的最短路径。
迪杰斯特拉算法只支持非负权图，它计算的是单源最短路径，即单个源点到剩余节点的最短路径，时间复杂度为O(n²)，对稀疏图运行更快。如果想知道所有顶点到所有顶点的最短路径，那么等于在原有算法的基础上，再来一次循环，此时整个算法的时间复杂度就成了O(n³)。
2.2 案例分析
该案例对应着下面实现代码中的案例，设起始点为A，初始化A到其他点的路径数组{0, 99, 8, 2, 99, 3, 99}，初始化标志位数组{true, false, false, false, false, false, false}。
开始第一轮循环，排除已找到的路径，即排除0，寻找到A的最短路径，找到了A-D，即索引为3的顶点,设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的D可达的顶点路径到A点的最短路径，如果经过D点的路径比数组中已存在的最短路径小，那么更新值。
这里D点可达C、B，D-C+A-D=7<8，因此更新A-C的最短路径为7；D-B+A-D=11<99，因此更新A-B的最短路径为11，第一轮循环结束，此时最短路径数组为{0, 11, 7, 2, 99, 3, 99}，标志位数组为{true, false, false, true, false, false, false}:
开始第二轮循环，排除已找到的路径，即排除0、2，寻找到A的最短路径，这里找到3，即索引为5的顶点，即A-F，设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的F可达的顶点路径到A点的最短路径，如果经过F点的路径比数组中已存在的最短路径小，那么更新值。
这里F点可达G，F-G+A-F=12<99，因此更新A-G的最短路径为12，第二轮循环结束，此时最短路径数组为{0, 11, 7, 2, 99, 3, 12}，标志位数组为{true, false, false, true, false, true, false}。
开始第三轮循环，排除已找到的路径，即排除0、2、3，寻找到A的最短路径，这里找到7，即索引为2的顶点，即A-C，设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的C可达的顶点路径到A点的最短路径，如果经过C点的路径比数组中已存在的最短路径小，那么更新值。
这里C点可达B，C-B+A-C=11 = 11，因此不更新A-B的最短路径，第三轮循环结束，此时最短路径数组为{0, 11, 7, 2, 99, 3, 12}，标志位数组为{true, false, true, true, false, true, false}。
开始第四轮循环，排除已找到的路径，即排除0、2、3、7，寻找到A的最短路径，这里找到11，即索引为1的顶点，即A-B，设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的B可达的顶点路径到A点的最短路径，如果经过B点的路径比数组中已存在的最短路径小，那么更新值。
这里B点可达E，B-E+A-B=18 < 99，因此更新A-E的最短路径为18，第四轮循环结束，此时最短路径数组为{0, 11, 7, 2, 18, 3, 12}，标志位数组为{true, true, true, true, false, true, false}。
开始第五轮循环，排除已找到的路径，即排除0、2、3、7、11，寻找到A的最短路径，这里找到12，即索引为6的顶点，即A-G，设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的G可达的顶点路径到A点的最短路径，如果经过G点的路径比数组中已存在的最短路径小，那么更新值。
排除已找到的顶点，这里G点可达E，G-E+A-G=18 = 18，因此不更新最短路径，第五轮循环结束，此时最短路径数组为{0, 11, 7, 2, 18, 3, 12}，标志位数组为{true, true, true, true, false, true, true}。
开始第六轮循环，排除已找到的路径，即排除0、2、3、7、11、12，寻找到A的最短路径，这里找到18，即索引为4的顶点，即A-E，设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的E可达的顶点路径到A点的最短路径，如果经过E点的路径比数组中已存在的最短路径小，那么更新值。
排除已找到的顶点，这里不更新最短路径，第四轮循环结束，此时最短路径数组为{0, 11, 7, 2, 18, 3, 12}，标志位数组为{true, true, true, true, true, true, true}。
此时大循环结束，Dijkstra算法结束，顶点A到各个顶点的最短路径已经找到，即A到{A,B,C,D,E,F,G}的最短路径为{0, 11, 7, 2, 18, 3, 12}。
3 弗洛伊德（Floyd）算法
3.1 原理
弗洛伊德（Floyd）算法又称插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。算出来的结果是所有的节点到其余各节点之间的最短距离。
通用步骤如下：
1.设图顶点数为N。首先需要准备一个长度为N的距离矩阵S，矩阵S中的元素a[i][j]=sum的表示顶点i到顶点j的最短路径为sum；
2.然后对S矩阵进行初始化，距离矩阵S中顶点a[i][j]的值为顶点i到顶点j的直接权值；
3.然后对S矩阵循环进行N次更新，在第k次更新时，如果S矩阵的a[i][j] > a[i][k]+a[k][j]，那么更新a[i][j]=a[i][k]+a[k][j]。循环更新完毕，则算法完成，所有的节点到其余各节点之间的最短距离已经找到了。
相比于Dijkstra 算法，Floyd算法支持带有负权边的图，但是不能解决带有“负权回路”（或者叫“负权环”）的图，实际上如果一个图中带有“负权回路”那么这个图则没有最短路径。
Floyd算法的时间复杂度同样是时间复杂度O(n³)，空间复杂度是O(n²)，代码非常简单，但是思想相却是非常的巧妙，将所有的可能都枚举出来一一对比，取最小值，这样最终会得到最小值。
3.2 案例分析
该案例对应着下面实现代码中的案例：
首先初始化距离矩阵S如下：
然后就是三层嵌套循环，开始第一轮大循环，即当k=0，循环遍历S矩阵，判断是否小于 shortestPath[i][j]，即所有的路径都经过A点中转，如果经过A中转后的路径shortestPath[i][0] + shortestPath[k][0]< shortestPath[i][j]，自然更新路径：shortestPath[i][j]= shortestPath[i][0] + shortestPath[k][0]。一轮大循环之后的数组如下：
然后经过一共经过N次的大循环，表示经过所有的顶点，最终取得的矩阵如下：
4 邻接矩阵加权图实现
这里的实现能够构造一个基于邻接矩阵实现无向加权图的类，并且提供深度优先遍历和广度优先遍历的方法，提供获取边集数组的方法，提供Prim和Kruskal两种求最小生成树的方法，提供Dijkstra和Floyd两种求最短路径的方法。
public class MatrixDijkstraAndFloyd<E> {
private Object[] vertexs;
private int[][] matrix;
private Edge<E>[] edges;
private static final int NO_EDGE = 99;
private static class Edge<E> {
private E from;
private E to;
private int weight;
public Edge(E from, E to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
public MatrixDijkstraAndFloyd(Object[] vertexs, Edge<E>[] edges) {
//初始化边数组
this.edges = edges;
// 初始化顶点数组,并添加顶点
this.vertexs = Arrays.copyOf(vertexs, vertexs.length);
// 初始化边矩阵,并预先填充边信息
this.matrix = new int[vertexs.length][vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
if (i == j) {
this.matrix[i][j] = 0;
} else {
this.matrix[i][j] = NO_EDGE;
}
}
}
for (Edge<E> edge : edges) {
// 读取一条边的起始顶点和结束顶点索引值
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
//对称的两个点位都置为edge.weight,无向图可以看作相互可达的有向图
this.matrix[p1][p2] = edge.weight;
this.matrix[p2][p1] = edge.weight;
}
}
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == e) {
return i;
}
}
return -1;
}
public void DFS() {
//新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点
boolean[] visited = new boolean[vertexs.length];
//初始化所有顶点都没有被访问
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
System.out.print("\t");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
DFS(i, visited);
}
}
System.out.println();
}
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
// 遍历该顶点的所有邻接点。若该邻接点是没有访问过，那么继续递归遍历领接点
for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
if (!visited[w]) {
DFS(w, visited);
}
}
}
public void BFS() {
// 辅组队列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点
boolean[] visited = new boolean[vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
System.out.print("\t");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
indexLinkedList.add(i);
}
if (!indexLinkedList.isEmpty()) {
//j索引出队列
Integer j = indexLinkedList.poll();
//继续访问j的邻接点
for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k] + " ");
//继续入队列
indexLinkedList.add(k);
}
}
}
}
System.out.println();
}
private int firstVertex(int v) {
//如果索引超出范围,则返回-1
if (v < 0 || v > (vertexs.length - 1)) {
return -1;
}
for (int i = 0; i < vertexs.length; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) {
return i;
}
}
return -1;
}
private int nextVertex(int v, int w) {
//如果索引超出范围,则返回-1
if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
return -1;
}
for (int i = w + 1; i < vertexs.length; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) {
return i;
}
}
return -1;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
stringBuilder.append(matrix[i][j]).append("\t");
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
public void prim() {
System.out.println("prim: ");
//对应节点应该被连接的前驱节点,用来输出
//默认为0,即前驱结点为第一个节点
int[] mid = new int[matrix.length];
//如果某顶点作为末端顶点被连接，对应位置应该为true
//第一个顶点默认被连接
boolean[] connected = new boolean[matrix.length];
connected[0] = true;
//存储未连接顶点到已连接顶点的最短距离(最小权)
int[] dis = new int[matrix.length];
//首先将矩阵第一行即其他顶点到0索引顶点的权值拷贝进去
System.arraycopy(matrix[0], 0, dis, 0, matrix.length);
//存储路径长度
int sum = 0;
//最小权值
int min;
for (int k = 1; k < matrix.length; k++) {
min = NO_EDGE;
//最小权值的顶点的索引
int minIndex = 0;
for (int i = 1; i < matrix.length; i++) {
//排除已连接的顶点,排除权值等于0的值,这里权值等于0表示已生成的最小生成树的顶点都未能与该顶点连接
if (!connected[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIndex = i;
}
}
//如果没找到,那么该图可能不是连通图,直接返回了,此时最小生成树没啥意义
if (minIndex == 0) {
return;
}
//权值和增加
sum += min;
//该新连接顶点对应的索引值变成true,表示已被连接,后续判断时跳过该顶点
connected[minIndex] = true;
//输出对应的前驱顶点到该最小顶点的权值
System.out.println("\t" + vertexs[mid[minIndex]] + " ---> " + vertexs[minIndex] + " 权值:" + min);
for (int i = 1; i < matrix.length; i++) {
//如果该顶点未连接
if (!connected[i]) {
if (matrix[minIndex][i] != 0 && dis[i] > matrix[minIndex][i]) {
//更新最小权值
dis[i] = matrix[minIndex][i];
//更新前驱节点索引为新加入节点索引
mid[i] = minIndex;
}
}
}
}
System.out.println("\t" + "sum: " + sum);
}
public void kruskal() {
System.out.println("Kruskal: ");
//由于创建图的时候保存了边集数组,这里直接使用就行了
//Edge[] edges = getEdges();
//this.edges=edges;
//对边集数组进行排序
Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
// 用于保存已有最小生成树中每个顶点在该最小树中的最终终点的索引
int[] vends = new int[this.edges.length];
//能够知道终点索引范围是[0,this.edges.length-1],因此填充edges.length表示没有终点
Arrays.fill(vends, this.edges.length);
int sum = 0;
for (Edge<E> edge : this.edges) {
// 获取第i条边的起点索引from
int from = getPosition(edge.from);
// 获取第i条边的终点索引to
int to = getPosition(edge.to);
// 获取顶点from在"已有的最小生成树"中的终点
int m = getEndIndex(vends, from);
// 获取顶点to在"已有的最小生成树"中的终点
int n = getEndIndex(vends, to);
// 如果m!=n，意味着没有形成环路,则可以添加,否则直接跳过,进行下一条边的判断
if (m != n) {
//添加设置原始终点索引m在已有的最小生成树中的终点为n
vends[m] = n;
System.out.println("\t" + vertexs[from] + " ---> " + vertexs[to] + " 权值:" + edge.weight);
sum += edge.weight;
}
}
System.out.println("\t" + "sum: " + sum);
//System.out.println(Arrays.toString(this.edges));
}
private int getEndIndex(int[] vends, int i) {
//这里使用循环查找的逻辑,寻找的是最终的终点
while (vends[i] != this.edges.length) {
i = vends[i];
}
return i;
}
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
//如果存在边
if (matrix[i][j] != NO_EDGE && matrix[i][j] != 0) {
edges.add(new Edge<>(vertexs[i], vertexs[j], matrix[i][j]));
//edges[index++] = new Edge(vertexs[i], vertexs[j], matrix[i][j]);
}
}
}
return edges.toArray(new Edge[0]);
}
public void kruskalAndPrim() {
System.out.println("kruskalAndPrim: ");
//已经找到的边携带的顶点对应的索引将变为true,其余未找到边对应的顶点将是false
boolean[] connected = new boolean[matrix.length];
//这里选择第一个顶点为起点,表示以该顶点开始寻找包含该顶点的最小边
connected[0] = true;
int sum = 0, n1 = 0, n2 = 0;
//最小权值
int min;
while (true) {
min = NO_EDGE;
//第一维
for (int i = 0; i < matrix.length; i++) {
//第二维
for (int j = i + 1; j < matrix.length; j++) {
//排除等于0的,排除两个顶点都找到了的,这里实际上已经隐含了排除环的逻辑,如果某条边的两个顶点都找到了,那么如果算上该条边,肯定会形成环
//寻找剩下的最小的权值的边
if (matrix[i][j] != 0 && connected[i] != connected[j] && matrix[i][j] < min) {
min = matrix[i][j];
n1 = i;
n2 = j;
}
}
}
//如果没找到最小权值,该图可能不是连通图,或者已经寻找完毕,直接返回
if (min == NO_EDGE) {
System.out.println("\t" + "sum:" + sum);
return;
}
//已经找到的边对应的两个顶点都置为true
connected[n1] = true;
connected[n2] = true;
//输出找到的边和最小权值
System.out.println("\t" + vertexs[n1] + " ---> " + vertexs[n2] + " 权值:" + min);
sum += min;
}
}
public void dijkstra(int start) {
checkIndex(start);
int[] shortestPathance = getShortestDistance(start, vertexs.length);
// 打印Dijkstra最短路径的结果
System.out.println("Dijkstra(" + vertexs[start] + "):");
for (int i = 0; i < vertexs.length; i++) {
System.out.println("\t(" + vertexs[start] + " ---> " + vertexs[i] + ")最短路径:" + shortestPathance[i]);
}
}
private int[] getShortestDistance(int start, int end) {
int[] shortestPathance = new int[vertexs.length];
//初始化数据
//首先设置起始点到顶点i到的最短路径为起始点到顶点i的权。
System.arraycopy(matrix[start], 0, shortestPathance, 0, matrix.length);
boolean[] shortest = new boolean[vertexs.length];
//首先设置起始点到自己的的路径已经找到了,为0
shortest[start] = true;
int k;
int min;
for (int i = 1; i < vertexs.length; i++) {
k = 0;
// 寻找当前最小的路径；
min = NO_EDGE;
for (int j = 0; j < vertexs.length; j++) {
//排除已经找到的最短路径之后，找到离start最近的顶点(k)。
if (!shortest[j] && shortestPathance[j] < min) {
min = shortestPathance[j];
k = j;
}
}
//先设置起始点到新顶点k的最短路径已经找到
shortest[k] = true;
if (end != vertexs.length && k == end) {
break;
}
//更新未获取最短路径的顶点的最短路径,因为其他已找到的顶点的最短路径已经找到了,这里指需要更新新加入的已找到的可达顶点的路径.
for (int j = 0; j < vertexs.length; j++) {
int tmp = matrix[k][j];
//排除已经找到的最短路径，排除未连接的路径，排除等于0的路径（连接自己）之后
//找到离start最如果新的最短路径比以前的最短路径还要短，则更新最短路径。
if (!shortest[j] && tmp != NO_EDGE && tmp != 0 && ((tmp = min + tmp) < shortestPathance[j])) {
shortestPathance[j] = tmp;
}
}
}
return shortestPathance;
}
private void checkIndex(int... index) {
for (int i : index) {
if (i < 0 || i >= vertexs.length) {
throw new ArrayIndexOutOfBoundsException("索引越界:" + i);
}
}
}
public void dijkstra(int start, int end) {
checkIndex(start, end);
int[] shortestPathance = getShortestDistance(start, end);
// 打印Dijkstra最短路径的结果
System.out.println("Dijkstra(" + vertexs[start] + " ---> " + vertexs[end] + ")最短路径:" + shortestPathance[end]);
}
public void floyd() {
//路径矩阵(两顶点最短路径,即最小权值)
int[][] shortestPath = new int[matrix.length][matrix.length];
for (int i = 0; i < matrix.length; i++) {
System.arraycopy(matrix[i], 0, shortestPath[i], 0, vertexs.length);
}
// 计算最短路径
for (int k = 0; k < matrix.length; k++) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
//要求经过下标k顶点的两个路径都不能等于NO_EDGE,否则就是没有路径,NO_EDGE应该选取的足够的大,否则可能出错
int tmp = (shortestPath[i][k] == NO_EDGE || shortestPath[k][j] == NO_EDGE) ? NO_EDGE : (shortestPath[i][k] + shortestPath[k][j]);
// 如果经过下标为k顶点路径比原两点间路径更短，则更新shortestPath[i][j]
if (shortestPath[i][j] > tmp) {
// i到j最短路径对应的值设为经过k的更小的一个
shortestPath[i][j] = tmp;
}
}
}
}
System.out.println("Floyd: ");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
System.out.print("\t" + shortestPath[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
//顶点数组
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//边数组,加权值
Edge[] edges = {
new Edge<>('A', 'C', 8),
new Edge<>('D', 'A', 2),
new Edge<>('A', 'F', 3),
new Edge<>('B', 'C', 4),
new Edge<>('C', 'D', 5),
new Edge<>('E', 'G', 6),
new Edge<>('E', 'B', 7),
new Edge<>('D', 'B', 9),
new Edge<>('F', 'G', 9)};
//构建图
MatrixDijkstraAndFloyd<Character> matrixDijkstraAndFloyd = new MatrixDijkstraAndFloyd<Character>(vexs, edges);
//输出图
System.out.println(matrixDijkstraAndFloyd);
//深度优先遍历
matrixDijkstraAndFloyd.DFS();
//广度优先遍历
matrixDijkstraAndFloyd.BFS();
//Prim算法输出最小生成树
matrixDijkstraAndFloyd.prim();
//Kruskal算法输出最小生成树
matrixDijkstraAndFloyd.kruskal();
//Kruskal算法结合Prim算法输出最小生成树,可能会有Bug,目前未发现
matrixDijkstraAndFloyd.kruskalAndPrim();
// Dijkstra算法获取某个索引的顶点到其它各个顶点的最短距离
// 这里参数是索引,也可以是一个顶点,需要稍微修改代码获取顶点的索引,比较简单这里就不做了
matrixDijkstraAndFloyd.dijkstra(0);
// Dijkstra算法获取一个顶点到另一个顶点的最短距离
matrixDijkstraAndFloyd.dijkstra(2, 0);
// Floyd算法获取所有顶点到所有顶点的最短路径
matrixDijkstraAndFloyd.floyd();
}
}
5 邻接表加权图实现
这里的实现能够构造一个基于邻接表实现无向加权图的类；并且提供深度优先遍历和广度优先遍历的方法，提供获取边集数组的方法，提供Prim和Kruskal两种求最小生成树的方法，提供Dijkstra和Floyd两种求最短路径的方法。
public class ListDijkstraAndFloyd<E> {
private class Node<E> {
E data;
LNode firstLNode;
public Node(E data, LNode firstLNode) {
this.data = data;
this.firstLNode = firstLNode;
}
}
private class LNode {
int vertex;
int weight;
LNode nextLNode;
}
private static class Edge<E> {
private E from;
private E to;
private int weight;
public Edge(E from, E to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
private Node<E>[] vertexs;
private Edge<E>[] edges;
private static final int NO_EDGE = 99;
public ListDijkstraAndFloyd(E[] vexs, Edge<E>[] edges) {
this.edges = edges;
vertexs = new Node[vexs.length];
for (int i = 0; i < vertexs.length; i++) {
vertexs[i] = new Node<>(vexs[i], null);
}
for (Edge<E> edge : edges) {
// 读取一条边的起始顶点和结束顶点索引值
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
int weight = edge.weight;
// 初始化lnode1边节点
LNode lnode1 = new LNode();
lnode1.vertex = p2;
lnode1.weight = weight;
// 将LNode链接到"p1所在链表的末尾"
if (vertexs[p1].firstLNode == null) {
vertexs[p1].firstLNode = lnode1;
} else {
linkLast(vertexs[p1].firstLNode, lnode1);
}
// 初始化lnode2边节点
LNode lnode2 = new LNode();
lnode2.vertex = p1;
lnode2.weight = weight;
// 将lnode2链接到"p2所在链表的末尾"
if (vertexs[p2].firstLNode == null) {
vertexs[p2].firstLNode = lnode2;
} else {
linkLast(vertexs[p2].firstLNode, lnode2);
}
}
}
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i].data == e) {
return i;
}
}
return -1;
}
private void linkLast(LNode first, LNode node) {
while (true) {
if (first.vertex == node.vertex) {
return;
}
if (first.nextLNode == null) {
break;
}
first = first.nextLNode;
}
first.nextLNode = node;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
stringBuilder.append(i).append("(").append(vertexs[i].data).append("): ");
LNode node = vertexs[i].firstLNode;
while (node != null) {
stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append("-").append(node.weight).append(")");
node = node.nextLNode;
if (node != null) {
stringBuilder.append("->");
} else {
break;
}
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
private void DFS(int i, boolean[] visited) {
//索引索引标记为true ,表示已经访问了
visited[i] = true;
System.out.print(vertexs[i].data + " ");
//获取该顶点的边表头结点
LNode node = vertexs[i].firstLNode;
//循环遍历该顶点的邻接点,采用同样的方式递归搜索
while (node != null) {
if (!visited[node.vertex]) {
DFS(node.vertex, visited);
}
node = node.nextLNode;
}
}
public void DFS() {
//新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点
boolean[] visited = new boolean[vertexs.length];
//初始化所有顶点都没有被访问
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
System.out.print("\t");
for (int i = 0; i < vertexs.length; i++) {
//如果对应索引的顶点的访问标记为false,则搜索该顶点
if (!visited[i]) {
DFS(i, visited);
}
}
System.out.println();
}
public void BFS() {
// 辅组队列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点
boolean[] visited = new boolean[vertexs.length];
//初始化所有顶点都没有被访问
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
System.out.print("\t");
for (int i = 0; i < vertexs.length; i++) {
//如果访问方剂为false,则设置为true,表示已经访问,然后开始访问
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i].data + " ");
indexLinkedList.add(i);
}
//判断队列是否有值,有就开始遍历
if (!indexLinkedList.isEmpty()) {
//出队列
Integer j = indexLinkedList.poll();
LNode node = vertexs[j].firstLNode;
while (node != null) {
int k = node.vertex;
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k].data + " ");
//继续入队列
indexLinkedList.add(k);
}
node = node.nextLNode;
}
}
}
System.out.println();
}
public void prim() {
System.out.println("prim: ");
//对应节点应该被连接的前驱节点,用来输出
//默认为0,即前驱结点为第一个节点
int[] mid = new int[vertexs.length];
int start = 0;
int min, tmp, sum = 0;
int num = vertexs.length;
//顶点间边的权值
//存储未连接顶点到已连接顶点的最短距离(最小权)
int[] dis = new int[num];
// 初始化"顶点的权值数组"，
// 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
//首先将其他顶点到0索引顶点的权值存储进去
for (int i = 0; i < num; i++) {
dis[i] = getWeight(start, i);
}
//如果某顶点作为末端顶点被连接，对应位置应该为true
//第一个顶点默认被连接
boolean[] connected = new boolean[vertexs.length];
connected[0] = true;
for (int k = 1; k < num; k++) {
min = NO_EDGE;
//最小权值的顶点的索引
int minIndex = 0;
// 在未被加入到最小生成树的顶点中，找出权值最小的顶点。
for (int i = 1; i < vertexs.length; i++) {
//排除已连接的顶点,排除权值等于0的值,因为这里默认顶点指向自己的权值为0
if (!connected[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIndex = i;
}
}
//如果没找到,那么该图可能不是连通图,直接返回了,此时最小生成树没啥意义
if (minIndex == 0) {
return;
}
//权值和增加
sum += min;
//该新连接顶点对应的索引值变成true,表示已被连接,后续判断时跳过该顶点
connected[minIndex] = true;
//输出对应的前驱顶点到该最小顶点的权值
System.out.println("\t" + vertexs[mid[minIndex]].data + " ---> " + vertexs[minIndex].data + " 权值:" + min);
for (int i = 1; i < num; i++) {
//如果该顶点未连接
if (!connected[i]) {
// 获取minindex顶点到未连接顶点i的权值
tmp = getWeight(minIndex, i);
if (tmp != 0 && dis[i] > tmp) {
dis[i] = tmp;
//更新前驱节点索引为新加入节点索引
mid[i] = minIndex;
}
}
}
}
System.out.println("\t" + "sum: " + sum);
}
private int getWeight(int start, int end) {
//如果start=end，则返回0
if (start == end) {
return 0;
}
//获取该顶点的边表的第一个值
LNode node = vertexs[start].firstLNode;
//循环查找边表,看能否找到对应的索引=end,找不到就返回NO_EDGE,表示两个顶点未连接。
while (node != null) {
if (end == node.vertex) {
return node.weight;
}
node = node.nextLNode;
}
return NO_EDGE;
}
public void kruskal() {
System.out.println("Kruskal: ");
//由于创建图的时候保存了边集数组,这里直接使用就行了
//Edge[] edges = getEdges();
//this.edges=edges;
//对边集数组进行排序
Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
// 用于保存已有最小生成树中每个顶点在该最小树中的最终终点的索引
int[] vends = new int[this.edges.length];
//能够知道终点索引范围是[0,this.edges.length-1],因此填充edges.length表示没有终点
Arrays.fill(vends, this.edges.length);
int sum = 0;
for (Edge<E> edge : this.edges) {
// 获取第i条边的起点索引from
int from = getPosition(edge.from);
// 获取第i条边的终点索引to
int to = getPosition(edge.to);
// 获取顶点from在"已有的最小生成树"中的终点
int m = getEndIndex(vends, from);
// 获取顶点to在"已有的最小生成树"中的终点
int n = getEndIndex(vends, to);
// 如果m!=n，意味着没有形成环路,则可以添加,否则直接跳过,进行下一条边的判断
if (m != n) {
//添加设置原始终点索引m在已有的最小生成树中的终点为n
vends[m] = n;
System.out.println("\t" + vertexs[from].data + " ---> " + vertexs[to].data + " 权值:" + edge.weight);
sum += edge.weight;
}
}
System.out.println("\t" + "sum: " + sum);
//System.out.println(Arrays.toString(this.edges));
}
private int getEndIndex(int[] vends, int i) {
//这里使用循环查找的逻辑,寻找的是最终的终点
while (vends[i] != this.edges.length) {
i = vends[i];
}
return i;
}
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
//遍历顶点数组
for (int i = 0; i < vertexs.length; i++) {
LNode node = vertexs[i].firstLNode;
while (node != null) {
//只需添加起点索引小于终点索引的边就行了
if (node.vertex > i) {
edges.add(new Edge<>(vertexs[i].data, vertexs[node.vertex].data, node.weight));
}
node = node.nextLNode;
}
}
return edges.toArray(new Edge[0]);
}
public void dijkstra(int start) {
checkIndex(start);
int[] distance = getShortestDistance(start, vertexs.length);
// 打印dijkstra最短路径的结果
System.out.println("dijkstra(" + vertexs[start].data + "):");
for (int i = 0; i < vertexs.length; i++) {
System.out.println("\t(" + vertexs[start].data + " ---> " + vertexs[i].data + ")最短路径:" + distance[i]);
}
}
public void dijkstra(int start, int end) {
checkIndex(start, end);
int[] shortestPathance = getShortestDistance(start, end);
// 打印dijkstra最短路径的结果
System.out.println("Dijkstra(" + vertexs[start].data + " ---> " + vertexs[end].data + ")最短路径:" + shortestPathance[end]);
}
private int[] getShortestDistance(int start, int end) {
int[] distance = new int[vertexs.length];
//初始化数据
for (int i = 0; i < vertexs.length; i++) {
//首先设置起始点到顶点i到的最短路径为起始点到顶点i的权。
distance[i] = getWeight(start, i);
}
boolean[] shortest = new boolean[vertexs.length];
//首先设置起始点到自己的的路径已经找到了,为0
shortest[start] = true;
int k;
int min;
for (int i = 1; i < vertexs.length; i++) {
k = 0;
// 寻找当前最小的路径；
min = NO_EDGE;
for (int j = 0; j < vertexs.length; j++) {
//排除已经找到的最短路径之后，找到离start最近的顶点(k)。
if (!shortest[j] && distance[j] < min) {
min = distance[j];
k = j;
}
}
//先设置起始点到新顶点k的最短路径已经找到
shortest[k] = true;
if (end != vertexs.length && k == end) {
break;
}
//更新未获取最短路径的顶点的最短路径,因为其他已找到的顶点的最短路径已经找到了,这里指需要更新新加入的已找到的可达顶点的路径.
for (int j = 0; j < vertexs.length; j++) {
int tmp = getWeight(k, j);
//排除已经找到的最短路径，排除未连接的路径，排除等于0的路径（连接自己）之后
//找到离start最如果新的最短路径比以前的最短路径还要短，则更新最短路径。
if (!shortest[j] && tmp != NO_EDGE && tmp != 0 && ((tmp = min + tmp) < distance[j])) {
distance[j] = tmp;
}
}
}
return distance;
}
private void checkIndex(int... index) {
for (int i : index) {
if (i < 0 || i >= vertexs.length) {
throw new ArrayIndexOutOfBoundsException("索引越界:" + i);
}
}
}
public void floyd() {
//路径矩阵(两顶点最短路径,即最小权值)
int[][] shortestPath = new int[vertexs.length][vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
//获取两点的直接权值
//如果是频繁调用该方法,因此可以创建一个属于对象的权值矩阵用来保存权值,这里为了简单没做
shortestPath[i][j] = getWeight(i, j);
}
}
// 计算最短路径
for (int k = 0; k < vertexs.length; k++) {
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
//要求经过下标k顶点的两个路径都不能等于NO_EDGE,否则就是没有路径,NO_EDGE应该选取的足够的大,否则可能出错
int tmp = (shortestPath[i][k] == NO_EDGE || shortestPath[k][j] == NO_EDGE) ? NO_EDGE : (shortestPath[i][k] + shortestPath[k][j]);
// 如果经过下标为k顶点路径比原两点间路径更短，则更新shortestPath[i][j]
if (shortestPath[i][j] > tmp) {
// i到j最短路径对应的值设为经过k的更小的一个
shortestPath[i][j] = tmp;
}
}
}
}
System.out.println("Floyd: ");
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
System.out.print("\t" + shortestPath[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
//顶点数组
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//边数组,加权值
Edge[] edges = {
new Edge<>('A', 'C', 8),
new Edge<>('D', 'A', 2),
new Edge<>('A', 'F', 3),
new Edge<>('B', 'C', 4),
new Edge<>('C', 'D', 5),
new Edge<>('E', 'G', 6),
new Edge<>('E', 'B', 7),
new Edge<>('D', 'B', 9),
new Edge<>('F', 'G', 9)};
//构建图
ListDijkstraAndFloyd<Character> listDijkstraAndFloyd = new ListDijkstraAndFloyd<Character>(vexs, edges);
//输出图
System.out.println(listDijkstraAndFloyd);
//深度优先遍历
//DFS:
//A C B E G F D
listDijkstraAndFloyd.DFS();
//广度优先遍历
//BFS:
//A C D F B G E
listDijkstraAndFloyd.BFS();
//Prim算法求最小生成树
listDijkstraAndFloyd.prim();
//Kruskal算法求最小生成树
listDijkstraAndFloyd.kruskal();
// Dijkstra算法获取某个索引的顶点到其它各个顶点的最短距离
// 这里参数是索引,也可以是一个顶点,需要稍微修改代码获取顶点的索引,比较简单这里就不做了
listDijkstraAndFloyd.dijkstra(0);
// Dijkstra算法获取一个顶点到另一个顶点的最短距离
listDijkstraAndFloyd.dijkstra(2, 0);
// Floyd算法获取所有顶点到所有顶点的最短路径
listDijkstraAndFloyd.floyd();
}
}
以上就是Java利用Dijkstra和Floyd分别求取图的最短路径的详细内容，更多关于Java求最短路径的资料请关注编程网其它相关文章！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
