`
eriol
  • 浏览: 407814 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

弗洛伊德算法

阅读更多

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年提出,适用于有权重的完全图,能够处理有负权重的边,但不包括负...

    java实现弗洛伊德算法

    弗洛伊德算法,全称为弗洛伊德-沃普斯(Warshall-Floyd)算法,是一种用于查找图中所有顶点对之间的最短路径的算法。在Java中实现该算法,可以解决复杂的网络问题,如计算最经济的旅行路线、优化数据传输路径等。下面...

    关键路径实现,迪杰斯特拉算法,弗洛伊德算法

    本篇文章将深入探讨这些主题,特别是关键路径的实现、迪杰斯特拉算法和弗洛伊德算法。 首先,关键路径(Critical Path Method, CPM)是一种项目管理技术,用于确定项目中最长的依赖路径,这条路径决定了项目的最短...

    弗洛伊德算法c语言实现

    根据提供的文件信息,我们可以深入探讨弗洛伊德算法在C语言中的实现及其应用场景。 ### 弗洛伊德算法概述 弗洛伊德算法是一种解决**任意两点之间最短路径问题**的经典算法,适用于带权有向图。它通过动态规划的...

    医院选址弗洛伊德算法.doc

    《医院选址弗洛伊德算法》 在信息科学与技术学院的数据结构课程设计中,学生常银恒选择了“医院选址”作为课题,采用弗洛伊德算法进行优化解决。这个课题旨在通过算法来解决实际生活中的问题,为大学生提供了一个...

    c语言源代码基于弗洛伊德算法的走迷宫找出路程序

    《C语言实现弗洛伊德算法解迷宫问题详解》 在编程领域,解决迷宫问题是一项有趣的挑战,尤其在C语言这样的低级语言中,它能帮助我们深入理解算法和数据结构。本文将详细讲解如何使用C语言,结合弗洛伊德算法,来...

    图的弗洛伊德算法

    《图的弗洛伊德算法详解与C/C++实现》 在计算机科学领域,图论是一种重要的理论基础,而求解图中的最短路径问题则是图论中的核心问题之一。弗洛伊德算法(Floyd-Warshall Algorithm)就是解决这类问题的有效方法,...

    算法 Floyd 弗洛伊德算法

    **弗洛伊德算法(Floyd Algorithm)**是一种用于寻找图中所有顶点对之间最短路径的动态规划算法。该算法由Robert W. Floyd在1962年提出,适用于有向图或无向图,能处理带有负权边的情况。在实际应用中,例如在交通...

    VC++2012编程演练数据结构《30》弗洛伊德算法

    在本资源中,我们主要探讨的是使用VC++2012进行编程演练,特别是针对数据结构的一个重要算法——弗洛伊德算法(Floyd-Warshall Algorithm)。这个算法主要用于求解图中的所有最短路径问题,它能找出图中任意两个顶点...

    弗洛伊德算法详解

    ### 弗洛伊德算法详解 #### 知识点概览 弗洛伊德算法是一种用于求解所有点对之间最短路径的经典算法,适用于稠密图或具有负权重边的图,尤其在处理所有点对最短路径问题时表现出色。与Dijkstra算法不同,后者主要...

    java实现弗洛伊德算法 经典java实现弗洛伊德算法 经典

    弗洛伊德算法,也称为弗洛伊德-沃瑟斯坦算法(Floyd-Warshall Algorithm),是一种在图论中用于查找所有顶点对之间的最短路径的经典算法。该算法适用于有向图或无向图,并且可以处理负权边的情况。在Java中实现这个...

    校园导游 - 弗洛伊德算法

    计算机课程数据结构 校园导游 - 弗洛伊德算法

    floyd弗洛伊德算法

    更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd...

Global site tag (gtag.js) - Google Analytics