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的最短路径。
分享到:
相关推荐
### 弗洛伊德算法详解及源代码分析 #### 一、弗洛伊德算法简介 弗洛伊德算法(Floyd's Algorithm)是一种解决图论中的所有对之间最短路径问题的经典算法。该算法可以处理带权图,并且允许权重为负值,但不能有负权...
弗洛伊德算法,全称为弗洛伊德-沃瑟曼算法(Floyd-Warshall Algorithm),是图论中一种著名的解决所有顶点对之间最短路径问题的算法。它适用于有向图或无向图,能找出图中任意两个顶点之间的最短路径,并且在计算...
弗洛伊德算法,也称为弗洛伊德-沃普斯方法(Floyd-Warshall Algorithm),是图论中一种著名的解决多源最短路径问题的算法。它由美国计算机科学家罗伯特·弗洛伊德在1962年提出,主要用来找到图中所有顶点对间的最短...
弗洛伊德算法(Floyd-Warshall Algorithm)是解决这一问题的一种经典方法,它能找出图中所有顶点之间的最短路径。这个算法由Robert W. Floyd于1962年提出,适用于有权重的完全图,能够处理有负权重的边,但不包括负...
弗洛伊德算法,全称为弗洛伊德-沃普斯(Warshall-Floyd)算法,是一种用于查找图中所有顶点对之间的最短路径的算法。在Java中实现该算法,可以解决复杂的网络问题,如计算最经济的旅行路线、优化数据传输路径等。下面...
本篇文章将深入探讨这些主题,特别是关键路径的实现、迪杰斯特拉算法和弗洛伊德算法。 首先,关键路径(Critical Path Method, CPM)是一种项目管理技术,用于确定项目中最长的依赖路径,这条路径决定了项目的最短...
根据提供的文件信息,我们可以深入探讨弗洛伊德算法在C语言中的实现及其应用场景。 ### 弗洛伊德算法概述 弗洛伊德算法是一种解决**任意两点之间最短路径问题**的经典算法,适用于带权有向图。它通过动态规划的...
《医院选址弗洛伊德算法》 在信息科学与技术学院的数据结构课程设计中,学生常银恒选择了“医院选址”作为课题,采用弗洛伊德算法进行优化解决。这个课题旨在通过算法来解决实际生活中的问题,为大学生提供了一个...
《C语言实现弗洛伊德算法解迷宫问题详解》 在编程领域,解决迷宫问题是一项有趣的挑战,尤其在C语言这样的低级语言中,它能帮助我们深入理解算法和数据结构。本文将详细讲解如何使用C语言,结合弗洛伊德算法,来...
《图的弗洛伊德算法详解与C/C++实现》 在计算机科学领域,图论是一种重要的理论基础,而求解图中的最短路径问题则是图论中的核心问题之一。弗洛伊德算法(Floyd-Warshall Algorithm)就是解决这类问题的有效方法,...
**弗洛伊德算法(Floyd Algorithm)**是一种用于寻找图中所有顶点对之间最短路径的动态规划算法。该算法由Robert W. Floyd在1962年提出,适用于有向图或无向图,能处理带有负权边的情况。在实际应用中,例如在交通...
在本资源中,我们主要探讨的是使用VC++2012进行编程演练,特别是针对数据结构的一个重要算法——弗洛伊德算法(Floyd-Warshall Algorithm)。这个算法主要用于求解图中的所有最短路径问题,它能找出图中任意两个顶点...
### 弗洛伊德算法详解 #### 知识点概览 弗洛伊德算法是一种用于求解所有点对之间最短路径的经典算法,适用于稠密图或具有负权重边的图,尤其在处理所有点对最短路径问题时表现出色。与Dijkstra算法不同,后者主要...
弗洛伊德算法,也称为弗洛伊德-沃瑟斯坦算法(Floyd-Warshall Algorithm),是一种在图论中用于查找所有顶点对之间的最短路径的经典算法。该算法适用于有向图或无向图,并且可以处理负权边的情况。在Java中实现这个...
计算机课程数据结构 校园导游 - 弗洛伊德算法
更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd...