大家好,又见面了,我是你们的朋友全栈君。
/**
floyed 是用动态规划解决完全最短路的算法,一次调用即可得到任意两个点间的最短路径
复杂度为O(n^3),适用于稠密图,顶点数一般在100 以内适用
结构简单,易于编写
floyed算法还可解决传递闭包,判断图是否为连通图
在解题时候一般不会只考 floyed 而是利用floyed 得到的结果,进行下一步解题
就像二分算法一样,提一下竞赛必考二分枚举
*/
const int inf = 0x3f3f3f3f;
const int M = 100;
int map[M][M]; //初始化map[][] = inf;
void addEdge(int u, int v, int w) {
map[u][v] = w;
map[v][u] = w; //floyed 也可以解决有向图
}
void floyed(int nv) {
int i, j, k;
for (i=1; i<=nv; i++)
for (j=1; j<=nv; j++)
for (k=1; k<=nv; k++)
map[i][j] = min(map[i][j], map[i][k]+map[k][j]);
}
/**
注意:连接矩阵添边都应该注意是否有重边,floyed 算法既可以解决有向图又可以解决
无向图,但是不能解决带负权回路的图
*/
收藏于 2011-11-18
来自于百度空间
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/149044.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...