本文主要是介绍最短路径-Floyd(弗洛伊德)算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
-
最短路径-Floyd(弗洛伊德)算法
-
简介：
相较Dijkstra，Floyd是一个完全穷举图中每个点到末尾点的最短路径
-
算法思想：
按惯例说两个工具
Path[MAX_SIZE][MAX_SIZE]：保存所有的最短路径（指向）
Short_Path[MAX_SIZE][MAX_SIZE]：保存所有的最短路径长度（数组）
状态转移：
Short_Path[v][w]=min{ D[v][w] , D[v][k] + D[k][w] }
v-w为一路径，中间经过k，取最小路径的经过点k
-
Dijkstra算法：
传送门：最短路径-Dijkstra(迪杰斯特拉)算法
Dijkstra算法复杂度：O(n^n)
Floyd算法复杂度：O(n^3)
-
Floyd模板：
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX_SIZE 1024//邻接图
struct MGrapth
{int Vexs[MAX_SIZE]; //顶点表int Arc[MAX_SIZE][MAX_SIZE]; //邻接矩阵int Num_Vertext,Num_Edges; //顶点数，边数
};
MGrapth Map;int Path[MAX_SIZE][MAX_SIZE]; /*路径矩阵*/
int Short_Path[MAX_SIZE][MAX_SIZE]; /*最短路矩阵*/void Floyd()
{int v,w,k;for(v=0;v<Map.Num_Vertext;++v){for(w=0;w<Map.Num_Vertext;w++){Short_Path[v][w]=Map.Arc[v][w];Path[v][w]=w;}}for(k=0;k<Map.Num_Vertext;k++){for(v=0;v<Map.Num_Vertext;v++){for(w=0;w<Map.Num_Vertext;w++){if(Short_Path[v][w]>Short_Path[v][k]+Short_Path[k][w]){Short_Path[v][w]=Short_Path[v][k]+Short_Path[k][w];Path[v][w]=Path[v][k];}}}}
}void Print_Path()
{int v,w,k;for(v=0;v<Map.Num_Vertext;v++) //打印所有v-w的路径{for(w=v+1;w<Map.Num_Vertext;w++){printf("v%d-v%d weight: %d",v,w,Short_Path[v][w]);k=Path[v][w];printf(" Path: %d",v);while(k!=w){printf(" -> %d",k);k=Path[k][w];}printf("-> %d\n",w );}printf("\n");}
}
这篇关于最短路径-Floyd(弗洛伊德)算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
