<>14.9弗洛伊德算法(Floyd)

Floyd算法介绍:
1、 和 Dijkstra 算法一样,弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法
2、 弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径,迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径
3、 弗洛伊德算法 VS 迪杰斯特拉算法:迪杰斯特拉算法通过选定的被访问顶点,求出从出发访问顶点到其他顶点
的最短路径;弗洛伊德算法中每一个顶点都是出发访问点,所以需要将每一个顶点看做被访问顶点,求出从每 一个顶点到其他顶点的最短路径

Floyd算法分析:
1、 设置顶点 vi 到顶点 vk 的最短路径已知为 Lik,顶点 vk 到 vj 的最短路径已知为 Lkj,顶点 vi 到 vj 的路径为 Lij, 则
vi 到 vj 的最短路径为:min((Lik+Lkj),Lij),vk 的取值为图中所有顶点,则可获得 vi 到 vj 的最短路径
2、 至于 vi 到 vk 的最短路径 Lik 或者 vk 到 vj 的最短路径 Lkj,是以同样的方式获得

Floyd算法实践:求每一个村庄分别到其他村庄的最短路径问题

package com.atguigu22.floyd; import java.lang.reflect.Array; import java.util.
Arrays; /** * @author peng * @date 2021/12/7 - 16:32 * <p> *
使用弗洛伊德算法求各村庄到其他各村庄的最短路径问题 */ public class FloydAlgorithm { public static void
main(String[] args) { char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int[]
[] matrix = new int[vertex.length][vertex.length]; final int N = 65535; matrix[0
] = new int[]{0, 5, 7, N, N, N, 2}; matrix[1] = new int[]{5, 0, N, 9, N, N, 3};
matrix[2] = new int[]{7, N, 0, N, 8, N, N}; matrix[3] = new int[]{N, 9, N, 0, N,
4, N}; matrix[4] = new int[]{N, N, 8, N, 0, 5, 4}; matrix[5] = new int[]{N, N, N
, 4, 5, 0, 6}; matrix[6] = new int[]{2, 3, N, N, 4, 6, 0}; Graph graph = new
Graph(vertex.length, matrix, vertex); graph.floyd(); graph.show(); } } /** *
创建图 */ class Graph { private char[] vertex;//存放节点是数组 private int[][] dis;
//保存出发顶点到各个顶点的距离 private int[][] pre;//保存到达目标顶点的前驱顶点 /** * @param length:村庄的数量
* @param matrix:村庄之间的二维数组信息 * @param vertex:村庄的名字 */ public Graph(int length,
int[][] matrix, char[] vertex) { this.vertex = vertex; this.dis = matrix; this.
pre= new int[length][length]; //对pre数组进行初始化 for (int i = 0; i < length; i++) {
//刚开始的时候,各个村庄的前驱结点都是自己本身 Arrays.fill(pre[i], i); } } /** * 显示dis数组和pre数组 */
public void show() { char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; for (
int i = 0; i < vertex.length; i++) { for (int j = 0; j < pre.length; j++) {
System.out.print(vertex[pre[i][j]] + "\t"); } System.out.println(); for (int k =
0; k < dis.length; k++) { System.out.print(vertex[i] + "到" + vertex[k] +
"的最短路径是:" + dis[i][k] + "\t"); } System.out.println(); } } /** * 实现弗洛伊德算法的主要思想:
* 假设有i,k, j三个村庄,可能存在的路线有:i--->、或者是i--->k--->j *
也就是说有两条路线,一条是直接i村庄指向j村庄,还有一个就是i村庄先到k村庄,再到j村庄,也就是以k村庄作为中间结点 *
现在要做的就是比较这两条路线之间哪一条的路线比较短,将短的那一条路线作为i到j的路线 */ public void floyd() { int len;
//存储路径的长度 for (int k = 0; k < dis.length; k++) { for (int i = 0; i < dis.length;
i++) { for (int j = 0; j < dis.length; j++) { len = dis[i][k] + dis[k][j];
//这个是i先到k,再到j的路线 if (len < dis[i][j]) {
//如果以k为村庄为中转的路线,比由i直接到j的路线还要短,就要将由i到j的路线改为中转的那一条路线 dis[i][j] = len;
//同时,本来j的前驱节点是i的,现在是经过中转之后才到j, 所以j的前驱接点就应该修改为k pre[i][j] = pre[k][j]; } } } } }
}

技术
©2019-2020 Toolsou All rights reserved,
C语言——qsort函数CSS实现溢出显示省略号网络层协议——ICMP协议C语言小游戏-俄罗斯方块Qt入门教程【基础控件篇】QCalendarWidget日历控件用python来控制wifi连接vue中input框只能输入数字Python内置函数C语言数据结构-顺序表删除重复V2.0.0abaqus质量缩放系数取值_ABAQUS的质量缩放