本文共 872 字，大约阅读时间需要 2 分钟。
Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 注意：其实很多题目不是直接问你floyd怎么求最短路径，而是要你利用floyd的动态规划思想解决类似floyd的问题。
Floyd算法可以算边权值非负的最短路径问题。下面给出算法模板
#include using namespace std; #define INF 1e9 const int maxn=100+10; int n,m;//点数,边数,点从0到n-1编号 int dist[maxn][maxn];//记录距离矩阵 int path[maxn][maxn];//path[i][j]=x表示i到j的路径上(除i外)的第一个点是x. void init() { for(int i=0;i dist[i][k]+dist[k][j]) { dist[i][j] = dist[i][k]+dist[k][j]; path[i][j] = path[i][k]; } else if(dist[i][j] == dist[i][k]+dist[k][j] &&path[i][j]>path[i][k]) { path[i][j] = path[i][k]; //最终path中存的是字典序最小的路径 } } }
输出路径例程：
printf("Path: %d", u);int beg = path[u][v];while (1){printf("-->%d", beg);if (beg == v) { cout << endl; break; }beg = path[beg][v];} 转载地址：http://buyci.baihongyu.com/