算法12--最短路径--弗洛伊德(Floyd)算法 PPT

最短路径Floyd算法
Floyd算法是一种用于解决最短路径问题的动态规划算法，其时间复杂度为O(n^3 )。

Floyd算法可以求出任意两点之间的最短路径，并且可以处理负权边（但不能处理负权环）。

算法思想
Floyd算法的基本思想是：对于图中的每一对顶点i和j，看看是否存在一个顶点k，使得从i 到k 再到j 比已知的路径更短。

如果是更短的，就修改当前路径为更短的那个路径。

算法步骤
1.初始化：将图中任意两点之间的最短路径长度初始化为它们之间的权值，如果两点之间没有直接的边，则权值为∞。

2.对于每一个中间节点k，依次考察所有的节点对(i,j)，如果从i到j经过节点k比原来的路径更短，则更新最短路径长度。

3.最后得到的矩阵即为任意两点之间的最短路径长度。

Matlab代码
function [D,P] = floyd(W)
% W为邻接矩阵
% D为最短距离矩阵
% P为最短路径矩阵
n = size(W,1);
for k=1:n
for i=1:n
for j=1:n
if W(i,k)+W(k,j)<W(i,j)
W(i,j)=W(i,k)+W(k,j);
P(i,j)=k;
end
end
end
end。

Floyd算法Floyd算法是一种经典的图论算法，用于求解带权有向图中任意两个顶点之间的最短路径问题。

该算法由美国数学家罗伯特·弗洛伊德（Robert Floyd）于1962年提出，因此得名为Floyd算法。

Floyd算法是一种动态规划算法，它采用了“分治”的思想，将问题分解为更小的子问题，然后逐步解决子问题，最终得到解决整个问题的结果。

本文将从算法的背景、基本思想、实现方法及优缺点等方面对Floyd 算法进行详细阐述和分析。

一、算法的背景在讲Floyd算法之前，我们先来了解一下最短路径问题。

顾名思义，最短路径问题就是在给定图中找到两个给定节点之间的一条最短路径，也就是路径上各边权值之和最小的路径。

这个问题在现实生活中有很多应用，比如网络路由、地图路径规划、航线安排等等。

在数学和计算机科学领域中，我们可以通过图论的方法来描述和解决这个问题。

一般来说，给定一张带权有向图G=(V, E)，其中V表示节点的集合，E表示边的集合。

每条边E(i,j)的权重为w(i,j)，表示从节点i到节点j的距离或成本。

那么最短路径问题就是在图中找到从节点s到节点t的一条最短路径P，并且P上的边权之和最小。

最初求解的思路是按照类似深度优先搜索的方式，逐个遍历所有路径，然后依次比较它们的距离，找到最短路径。

但这种方式显然是不可行的，因为它的时间复杂度非常高。

所以，我们需要设计一种更高效的算法，以求得最短路径问题的最优解。

二、算法的基本思想Floyd算法就是一种高效地解决最短路径问题的方法。

它采用了“动态规划”的思想，通过逐步求解子问题，最终得到完整的最短路径。

而解决子问题的方式则是采用了“分治”的思想，将问题分解为更小的子问题，然后逐步解决。

具体地说，Floyd算法采用了“中转节点”的概念，我们可以将问题转化为这样一个子问题：对于每个节点i和节点j，假设我们已经知道了它们之间的最短路径长度为d[i][j]，那么考虑一下节点k作为中转节点，它可以为i和j之间的路径P提供一个“中转服务”，将P拆分为两条路径：i-->k和k-->j。

v 弗洛伊德算法弗洛伊德算法（Floyd’s algorithm），又称为插点法，是一种通过动态规划求解最短路径问题的算法。

该算法在图论中有着广泛的应用，能够快速求解出两点之间的最短路径。

本文将为大家介绍弗洛伊德算法的原理以及实际应用。

1. 算法原理弗洛伊德算法的核心思想是利用中间点来更新起点到终点的距离。

假设图中任意两点之间的距离都为$d[i][j]$，则我们假设存在一个中间点$k$，可以将起点$i$和终点$j$之间的最短路径分成两部分，即起点到中间点的路径$d[i][k]$和中间点到终点的路径$d[k][j]$。

所以我们可以得到如下的状态转移方程：$$d[i][j]=\min(d[i][j],d[i][k]+d[k][j])$$通过不断地更新所有点之间的最短路径，我们最终可以得到所有节点之间的最短路径。

2. 算法实现弗洛伊德算法的实现中，最重要的一步就是更新状态转移方程。

具体来说，我们需要使用三层循环嵌套遍历所有点，将当前节点到所有其他节点的最短距离更新一遍即可。

下面就是使用 Python 语言实现弗洛伊德算法的代码片段：```pythonn = len(graph)for k in range(n):for i in range(n):for j in range(n):graph[i][j] = min(graph[i][j], graph[i][k] +graph[k][j])```在这段代码中，$graph$是一个$n \times n$的矩阵，表示所有节点之间的距离。

其中$n$是节点的数量。

3. 算法应用弗洛伊德算法的主要应用是求解带权图中各个节点之间的最短路径。

在实际生活中，我们可以将节点看作是城市，将距离看作是两个城市之间的道路距离。

这样，就可以使用弗洛伊德算法来计算任意两座城市之间的最短路程，帮助人们规划出更加便捷的旅行路线。

另外，在计算机网络中，弗洛伊德算法也被广泛应用于路由协议的设计中。

最短路径在一个无权的图中，若从一个顶点到另一个顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。

由于从一个顶点到另一个顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，把路径长度最短（即经过的边数最少）的那条路径叫作最短路径或者最短距离。

对于带权的图，考虑路径上各边的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或带权路径长度。

从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径长度或最短距离。

最短路径算法Dijkstra算法：该算法是用于求解单源点最短路径的实用算法。

Dijkstra算法的基本思想如下：设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S其中，V为网中所有顶点集合。

按最短路径长度递增的顺序逐个用V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。

Dijkstra算法的具体步骤；（1）设源点为V1，则S中只包含顶点V1，令W=V-S，则W中包含除V1外图中所有顶点。

V1对应的距离值为0，即D[1]=0。

W中顶点对应的距离值是这样规定的：若图中有弧 <v1,vk>，则Vj顶点的距离为此弧权值，否则为一个无穷大的数；（2）从W中选择一个其距离值最小的顶点 vk，并加入到S中；（3）每往S中加入一个顶点vk后，就要对W中各个顶点的距离值进行一次修改。

若加进vk做中间顶点，使<v1,vk> + <vk+vj>的值小于<v1,vj> 值，则用<v1,vk> + <vk+vj>代替原来vj 的距离值；（4）重复步骤2和3，即在修改过的W中的选距离值最小的顶点加入到S 中，并修改W中的各个顶点的距离值，如此进行下去，知道S中包含图中所有顶点为之，即S=V。

最短路最短路问题（short-path problem）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。

最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

单源最短路径包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。

在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

）算法可以采用Dijkstra 算法。

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法代码1#include <string.h>2#include<algorithm>3using namespace std;45const int maxnum = 100;6const int maxint = 99999999;78int dist[maxnum];9int prev[maxnum];//记录当前点的前一个结点10int c[maxnum][maxnum];11int n,line;1213void dijkstra(int n,int v,int *dist,int *prev,int c[maxnum][maxnum])//v代表源点14{15 bool s[maxnum];//判断是否已存入该点到S中16 for(int i = 1;i <= n;++i)17 {18 dist[i] = c[v][i];19 s[i] = 0;20 if(dist[i] == maxint)//代表当前点与源点没有直接相连21 prev[i] = 0;22 else23 prev[i] = v;//代表当前点的前一个节点是v，即源点24 }25 dist[v] = 0;//源点到源点的距离初始化为026 s[v] = 1;//源点已被遍历过，标记为12728 for(int i = 2;i <= n;++i)29 {30 int tmp = maxint;31 int u = v;32 for(int j = 1;j <= n;++j)33 {34 if((!s[j]) && dist[j] <tmp)//该点没有被遍历到并且源点到j点的距离小于记录的距离35 {36u = j;//记录下这一点37tmp = dist[j];//记录下这一点到源点的距离38 }39 }40 //找到距离最短的点退出循环41 s[u] = 1;//标记该点已经遍历过4243 for(int j = 1;j <= n;++j)44 {45 if((!s[j]) && c[u][j] <maxint)//j没有被遍历过并且从u到j还有这条路径46 {47 int newdist = dist[u] + c[u][j];//新的距离是从源点到u的距离加上从u到的距离48 if(newdist <dist[j])//如果新的距离比原来到j的距离要短49 {50 dist[j] = newdist;//则更新dist数组51 prev[j] = u;//标记j的前一个节点是u52 }53 }54 }55 }56}5758void searchpath(int *prev,int v,int u)//查找从v到u的最短路径59{60 int que[maxnum];//保存路径61 int tot = 1;62 que[tot] = u;//把终点存入路径数组63 tot++;64 int tmp = prev[u];65 while(tmp != v)66 {67 que[tot] = tmp;68 tot++;69tmp = prev[tmp];70 }71 que[tot] = v;72 for(int i = tot;i >= 1;--i)73 {74 if(i != 1)75 printf("%d->",que[i]);76 else77 printf("%d\n",que[i]);78 }79}808182int main()83{84 scanf("%d",&n);//输入结点数85 scanf("%d",&line);//输入路径数目86 int p,q,len;87 for(int i = 1;i <= n;++i)//初始化存储数组88 {89 for(int j = 1;j <= n;++j)90 {91 c[i][j] = maxint;92 }93 }94 for(int i = 1;i <= line;++i)//往存储数组里存放路径95 {96 scanf("%d%d%d",&p,&q,&len);97 if(len <c[p][q])//如果两个点之间有多条路，取路径较短的那一条98 c[p][q] = len;99 c[q][p] = len;//该语句根据实际情况写，用于无向路径中100 }101 for(int i = 1;i <= n;++i)//初始化标记数组102 dist[i] = maxint;//该数组记录从起点到该点的最短路径长度103104105 dijkstra(n,1,dist,prev,c);106 printf("从源点到最后一个顶点的最短路径长度为：%d\n",dist[n]);107 printf("从源点到最后一个顶点的路径为：");108 searchpath(prev,1,n);109}全局最短路求图中所有的最短路径。

Floyd（弗洛伊德）算法（C语⾔）转载：Floyd算法的介绍算法的特点弗洛伊德算法是解决任意两点间的最短路径的⼀种算法，可以正确处理有向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被⽤于计算有向图的传递闭包。

算法的思路通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引⼊两个矩阵，矩阵S中的元素a[i][j]表⽰顶点i(第i个顶点)到顶点j(第j个顶点)的距离。

矩阵P中的元素b[i][j]，表⽰顶点i到顶点j经过了b[i][j]记录的值所表⽰的顶点。

假设图G中顶点个数为N，则需要对矩阵D和矩阵P进⾏N次更新。

初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。

接下来开始，对矩阵D进⾏N次更新。

第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i] [0]+a[0][j]表⽰”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。

同理，第k次更新时，如果”a[i][j]的距离” >“a[i][k-1]+a[k-1][j]”，则更新a[i][j]为”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。

更新N次之后，操作完成！补充：以下⾯图为例⼦，b[i][j]中存储的是Vi~Vj之间的中介点，b[i][j]初始值为j，⽐如V0~V3最短路径是V0-->V2-->V1-->v3，在计算最短路径时转换为V0-->V2的距离加上V2-->V3的最短距离，接下来类似于递归，V2-->V3的最短路径就是以V1为中介点，V2-->V1的距离加上V1-->V3的距离。

因此，b[0][3]=2实例说明将整体分为两个步骤1.计算metrixD矩阵(两顶点之间的最短距离)和P矩阵(两顶点的中介点)#include <stdio.h>#include <stdlib.h>void Create_metrixD_P(int** metrixD, int **P ,int VerNum, int EdgNum){int x, y, Weight, edg_count = 0;int i, j, k;for (i = 0; i < VerNum; ++i) {for (j = 0; j < VerNum; ++j) {metrixD[i][j] = INT_MAX;P[i][j] = j;}}while (edg_count < EdgNum) {scanf("%d%d%d", &x, &y, &Weight);metrixD[x - 1][y - 1] = Weight;edg_count++;}}//Floyd algorithmvoid Floyd(int **metirxD, int **P, int VerNum) {int n, x, y, temp = 0;//The triple loop looks for shortest paths and weightsfor (n = 0; n < VerNum; ++n) {for (x = 0; x < VerNum; ++x) {for (y = 0; y < VerNum; ++y) {//The distance between two vertices is compared to the distance through a vertextemp = (metirxD[x][n] == INT_MAX || metirxD[n][y] == INT_MAX) ? INT_MAX : (metirxD[x][n] + metirxD[n][y]);if (temp < metirxD[x][y]) {//Update matrix informationmetirxD[x][y] = temp;P[x][y] = n;}}}}}void Show_metrixD_P(int** metrixD, int **P, int VerNum){int x, y;printf("metrixD:\n");for (x = 0; x < VerNum; ++x) {for (y = 0; y < VerNum; ++y) {if (metrixD[x][y] == INT_MAX) {printf("∞ ");}else {printf("%d ", metrixD[x][y]);}}printf("\n");}printf("P:\n");for (x = 0; x < VerNum; ++x) {for (y = 0; y < VerNum; ++y) {printf("%d ", P[x][y]);}printf("\n");}}int main(void){int VerNum, EdgNum, i;int** metrixD, ** P;printf("Enter the number of vertices and edges:");scanf("%d%d", &VerNum, &EdgNum);metrixD = (int**)malloc(VerNum * sizeof(int));P = (int**)malloc(VerNum * sizeof(int));for (i = 0; i < VerNum; ++i) {metrixD[i] = (int*)malloc(VerNum * sizeof(int));P[i] = (int*)malloc(VerNum * sizeof(int));}printf("Input vertices and weights:");Create_metrixD_P(metrixD, P, VerNum, EdgNum);Floyd(metrixD, P, VerNum);Show_metrixD_P(metrixD, P, VerNum);for (i = 0; i < VerNum; ++i) {free(metrixD[i]);free(P[i]);}free(metrixD);free(P);return0;}2.输出顶点之间的最短距离与路径#include <stdio.h>#include <stdlib.h>#define VEXNUM 5//Adjacency matrix: shows the distance between verticesint metirxD[VEXNUM][VEXNUM] = {INT_MAX,10, 5, INT_MAX,INT_MAX,INT_MAX,INT_MAX,2, 1, INT_MAX,INT_MAX,3, INT_MAX,9, 2,INT_MAX,INT_MAX,INT_MAX,INT_MAX,4,7, INT_MAX,INT_MAX,5, INT_MAX};//Path: passing vertex between two verticesint P[VEXNUM][VEXNUM] = {0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4};//Floyd algorithmvoid Floyd() {int n, x, y, temp = 0;//The triple loop looks for shortest paths and weightsfor (n = 0; n < VEXNUM; ++n) {for (x = 0; x < VEXNUM; ++x) {for (y = 0; y < VEXNUM; ++y) {//The distance between two vertices is compared to the distance through a vertextemp = (metirxD[x][n] == INT_MAX || metirxD[n][y] == INT_MAX) ? INT_MAX : (metirxD[x][n] + metirxD[n][y]);if (temp < metirxD[x][y]) {//Update matrix informationmetirxD[x][y] = temp;P[x][y] = n;}}}}}void Show_Path() {int x, y, temp = 0;//Output the shortest path between two verticesfor (x = 0; x < VEXNUM - 1; ++x) {for (y = x + 1; y < VEXNUM; ++y) {printf("V%d-->V%d weight:%d path:V%d", x, y, metirxD[x][y], x);temp = P[x][y];while (temp != y) {printf("-->V%d", temp);temp = P[temp][y];}printf("-->V%d", y);printf("\n");}}}int main(void){Floyd();Show_Path();return0;}完整代码#include <stdio.h>#include <stdlib.h>void Create_metrixD_P(int** metrixD, int **P ,int VerNum, int EdgNum){int x, y, Weight, edg_count = 0;int i, j, k;for (i = 0; i < VerNum; ++i) {for (j = 0; j < VerNum; ++j) {metrixD[i][j] = INT_MAX;P[i][j] = j;}}while (edg_count < EdgNum) {scanf("%d%d%d", &x, &y, &Weight);metrixD[x - 1][y - 1] = Weight;edg_count++;}}//Floyd algorithmvoid Floyd(int **metirxD, int **P, int VerNum) {int n, x, y, temp = 0;//The triple loop looks for shortest paths and weightsfor (n = 0; n < VerNum; ++n) {for (x = 0; x < VerNum; ++x) {for (y = 0; y < VerNum; ++y) {//The distance between two vertices is compared to the distance through a vertextemp = (metirxD[x][n] == INT_MAX || metirxD[n][y] == INT_MAX) ? INT_MAX : (metirxD[x][n] + metirxD[n][y]);if (temp < metirxD[x][y]) {//Update matrix informationmetirxD[x][y] = temp;P[x][y] = n;}}}}}void Show_metrixD_P(int** metrixD, int **P, int VerNum){int x, y;printf("metrixD:\n");for (x = 0; x < VerNum; ++x) {for (y = 0; y < VerNum; ++y) {if (metrixD[x][y] == INT_MAX) {printf("∞ ");}else {printf("%d ", metrixD[x][y]);}}printf("\n");}printf("P:\n");for (x = 0; x < VerNum; ++x) {for (y = 0; y < VerNum; ++y) {printf("%d ", P[x][y]);}printf("\n");}}void Show_Path(int **metirxD, int **P, int VerNum) {int x, y, temp = 0;//Output the shortest path between two verticesfor (x = 0; x < VerNum - 1; ++x) {for (y = x + 1; y < VerNum; ++y) {printf("V%d-->V%d weight:%d path:V%d", x, y, metirxD[x][y], x); temp = P[x][y];while (temp != y) {printf("-->V%d", temp);temp = P[temp][y];}printf("-->V%d", y);printf("\n");}}}int main(void){int VerNum, EdgNum, i;int** metrixD, ** P;printf("Enter the number of vertices and edges:");scanf("%d%d", &VerNum, &EdgNum);metrixD = (int**)malloc(VerNum * sizeof(int));P = (int**)malloc(VerNum * sizeof(int));for (i = 0; i < VerNum; ++i) {metrixD[i] = (int*)malloc(VerNum * sizeof(int));P[i] = (int*)malloc(VerNum * sizeof(int));}printf("Input vertices and weights:");Create_metrixD_P(metrixD, P, VerNum, EdgNum);Floyd(metrixD, P, VerNum);Show_metrixD_P(metrixD, P, VerNum);Show_Path(metrixD, P, VerNum);for (i = 0; i < VerNum; ++i) {free(metrixD[i]);free(P[i]);}free(metrixD);free(P);return0;}。

算法｜三重循环与Floyd（弗洛伊德）多源最短路径算法通常，数组用循环来处理，一般来说，一维数组的数据处理可以使用单重循环或双重循环。

如输出数组元素值，从一个数组中挑选最大值或最小值等可以使用单重循环。

而对于数组的排序一般使用双重循环，因为单重循环可以挑出一个元素的最大值或最小值，而有n个元素的数组则通过n次挑选便可完成整个数组的排序，所以在单重循环外再嵌套一个循环即可。

对于二维数组的数据处理，通常可以使用双重循环或三重循环，如二维数组元素值的输出，便可以使用双重循环，而矩阵（二维数组）乘法，便可以使用三重循环：const int maxn=105; int a[maxn][maxn],b[maxn][maxn]; int ans[maxn][maxn]; int a_n,a_m,b_n,b_m; void mul(){ for(int i=0; i<a_m; i ){ // i循环数组a的行 for(int j=0; j<b_n; j ){// j循环数组b 的列for(int k=0; k<a_n; k ){ // k循环数组a的列，数组b的行，ans[i][j] =a[i][k]*b[k][j]; } } }三重循环的另一个经典应用就是Floyd算法求多源最短路径。

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。

该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

其算法的核心是在顶点 i 和顶点 j 之间，插入顶点k，看是否能够缩短 i 和 j 之间的距离（松驰操作）。

暑假，小哼准备去一些城市旅游。

有些城市之间有公路，有些城市之间则没有，如下图。

为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。

可以画成如下的简图↓上图中有4个城市8条公路，公路上的数字表示这条公路的长短。

最短路径法
最短路径法是用于在给定条件下从一点A到一点B找到一条最短的路径的一种算法。

它是用于求解带有权重的有向图的最短路径的方法。

它的目的是要在图的给定顶点之间找到一条最短的路径，主要是通过考察不同的路径，从而找到效率最高的路径，以期达到最优化的目的。

最短路径算法的原理是：设定一个源节点并且把它设置为一个较小的值0这就是称作“最小花费”，其他非源节点初始设置一个任意值。

从源节点开始，当你可以到达目标节点时，就从图中得到一条路径。

接下来，所有连接源节点的边都会被检索，然后把源节点附近任一某点当作新的源节点，重复上述步骤，一直到找到目标节点。

最短路径算法常用的方法有：贪心法、迪杰斯特拉算法和弗洛伊德算法。

贪心法(Greedy Algorithm)根据每一步的最优选择来处理问题，而迪杰斯特拉算法(Dijkstra's Algorithm)是一种基于动态规划来求解最短路径的简单的单源最短路径算法，这个算法无法处理权重为负值的情况，而弗洛伊德算法(Floyd-Warshall Algorithm)则可以处理负权重情况，这是一种基于动态规划的方法，它可以求出一个有向图中任意给定两点之间最短路径。

最短路径算法可以应用于许多场景，如寻找交通路线的最短距离、物流路线的最佳排序等，其应用领域较为广泛。

最短路径算法拥有给定时间复杂度，可在具有稀疏性特征的图上进行有效求解，以及不断发展改进的算法，这使它被广泛应用于实际中。