Floyd-Warshall算法,简称Floyd算法,用于求解任意两点间的最短距离,时间复杂度为O(n^3)。
使用条件&范围
通常可以在任何图中使用,包括有向图、带负权边的图。
Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边,这个算法通过考虑最佳子路径来得到最佳路径。
算法思想
// dist(i,j) 为从节点i到节点j的最短距离
For i←1 to n do
For j←1 to n do
dist(i,j) = weight(i,j)
For k←1 to n do // k为“媒介节点”
For i←1 to n do
For j←1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径?
dist(i,j) = dist(i,k) + dist(k,j)
实现
public class Floyd {
private int[][] dist;
private int[][] path;
public void floyd(int[][] value) {
int len = value.length;
dist = new int[len][len];
path = new int[len][len];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
path[i][j] = -1;
dist[i][j] = value[i][j];
}
}
for (int k = 0; k < len; k++) {
for (int i = 0; i < len; i++ ) {
for (int j = 0; j < len; j++) {
if (dist[i][k] != Integer.MAX_VALUE &&
dist[k][j] != Integer.MAX_VALUE &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
}
}
}
}
}
public void path(int i, int j) {
int k = path[i][j];
if (k == -1)
return;
path(i, k);
System.out.print("->" + k);
path(k, j);
}
public void disPatch(int i , int j) {
System.out.println("min dist is: " + dist[i][j]);
System.out.print(i);
path(i, j);
System.out.print("->" + j);
}
}
dist[][]数组初始化为各顶点间的原本距离,最后存储各顶点间的最短距离。
path[][]数组保存最短路径,与当前迭代的次数有关。初始化都为-1,表示没有中间顶点。在求dist[i][j]过程中,path[i][j]存放从顶点vi到顶点vj的中间顶点编号不大于k的最短路径上前一个结点的编号。在算法结束时,由二维数组path的值回溯,可以得到从顶点vi到顶点vj的最短路径。
分享到:
相关推荐
java实现弗洛伊德算法 经典java实现弗洛伊德算法 经典java实现弗洛伊德算法 经典java实现弗洛伊德算法 经典java实现弗洛伊德算法 经典
弗洛伊德算法 源代码 求出一对顶点之间的嘴短路径
采用弗洛伊德算法,计算每对顶点之间的最短路径
弗洛伊德算法实现最短路径问题、数学建模大赛警务平台的建立分析题解
该课件采用C++面向对象思想,对最短路径中的弗洛伊德算法进行完美演示,开发工具VC6.0,对于初学数据结构的学生比较合适。
数据结构中的关键路径实现,可视化界面,迪杰斯特拉算法,和弗洛伊德算法
计算机课程数据结构 校园导游 - 弗洛伊德算法
本代码是数据结构(c语言)中图的弗洛伊德算法的实现
更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd...
VC++2012编程演练数据结构《30》弗洛伊德算法
数据结构与算法,图,求每一对顶点间的最短路径问题,弗洛伊德算法完整实现,带注释
java版的弗洛伊德求最短路径的算法,仅供参考
医院选址完成的是几个村庄之间将要建立一个医院的问题,转化为我们的C++语言的代码时,采用弗洛伊德算法,即各个点之间的最短距离算法,分为代码中几个部分:print,距离,算法核心,偏心度计算及解释,最后的操作见...
这是算法课的作业,读取文件中的距离矩阵,计算最短路径
有了这个,理解弗洛伊德算法就不在是问题
此代码描述是描述两点之间的最短路径的算法,对于我们求解最短距离很有帮助