Floyd算法

/* Floyd算法（用于解决全源最短路问题）流程如下： 枚举顶点k∈[1,n] 以顶点k作为中介点，枚举所有顶点对i和j（i∈[1,n],j∈[1,n]） 如果dis[i][k]+dis[k][j]<dis[i][j]成立 赋值dis[i][j] = dis[i][k] + dis[k][j] */ //下面是Floyd算法应用的代码 #include<cstdio> #include<algorithm> using namespace std; const int INF = 1000000000; const int MAXV = 200;//MAXV为最大顶点数 int n, m;//n为顶点数，m为边数 int dis[MAXV][MAXV];//dis[i][j]表示顶点i和顶点j的最短距离 void Floyd() { for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dis[i][k] != INF&&dis[k][j] != INF &&dis[i][k] + dis[k][j] < dis[i][j]) dis[i][j] = dis[i][k] + dis[k][j];//找到更短的路径 } } } } int main() { int u, v, w; fill(dis[0], dis[0] + MAXV*MAXV, INF);//dis数组赋初值 scanf("%d%d", &n, &m);//顶点数n、边数m for (int i = 0; i < n; i++) { dis[i][i] = 0;//顶点i到顶点i的距离初始化为0 } for (int i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &w); dis[u][v] = w;//以有向图为例进行输入 } Floyd();//Floyd算法入口 for (int i = 0; i < n; i++)//输出dis数组 { for (int j = 0; j < n; j++) { printf("%d ", dis[i][j]); } printf("\n"); } return 0; }