文档章节

floyd算法学习

aqia358
 aqia358
发布于 2014/06/05 09:52
字数 651
阅读 20
收藏 0
点赞 0
评论 0

1、问题引入

  带权有向图中单源点的最短路径问题可以用地杰斯特拉算法求解,如果要求解图中每一对顶点之间的最短路径,类似可以想到的方法为:每次以一个顶点为源点,重复执行地杰斯特拉算法算法n次,这样,便可以求得每一对顶点之间的最短路径,总的执行时间为O(n3)。

  这里可以采用另外一种求解算法:Floyd算法。

2、Floyd的基本思想为:

  从邻接矩阵a开始进行n次迭代,第一次迭代后a[i,j]的值是从vi到vj且中间不经过变化大于1的顶点的最短路径长度;第k次迭代后a[i,j]的值是从vi到vj且中间不经过变化大于k的顶点的最短路径长度 第n次迭代后a[i,j]的值就是从vi到vj的最短路径长度。

3、算法描述:

  (1) 用数组d[i][j]来记录i,j之间的最短距离。初始化d[i][j],若i=j则d[i][j]=0,
    若i,j之间有边连接则d[i][j]的值为该边的权值,否则d[i][j]的值为max 。
  (2) 对所有的k值从1到n,修正任意两点之间的最短距离,计算d[i][k]+d[k][j]的值,
    若小于d[i][j],则d[i][j]= d[i][k]+d[k][j],否则d[i][j]的值不变。

4、具体实现:

  带权有向图如下:

在b.txt文件中保存的带权有向图的数据为:

其中第一个数据4表述图中有4个节点,其他的四行四列数据表示各个节点之间的路径长度,9999表示两个节点之间不可达。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Floyd {

	public static int N;
	public static int[][] f;
	public static int[][] path;
	
	public static void floyd(){
		int i,j,k;
		i = j = k = 0;
		for(i = 0; i < N; ++i)
			for(j = 0; j < N; ++j)
				for(k = 0; k < N; ++k)
					if(f[i][j] > f[i][k] + f[k][j]){
						f[i][j] = f[i][k] + f[k][j];
						path[i][j] = k;
					}
		print();
	}
	
	public static void print(){
		for(int i = 0; i < N; ++i){
			for(int j = 0; j < N; ++j){
				printPath(i, j);
				System.out.print("="+f[i][j]+"\t");
			}
			System.out.println();
		}
	}
	
	public static void printPath(int i, int j){
		if(i == j || path[i][j] == -1)
			System.out.print(i+"->"+j);
		else{
			printPath(i,path[i][j]);
			System.out.print("->"+j);
		}
	}
	
	public static void main(String[] args) {
		String p = "d:/b.txt";
		try {
			Scanner s = new Scanner(new File(p));
			while(s.hasNext()){
				N = s.nextInt();
				f = new int[N][N];
				path = new int[N][N];
				for(int i = 0; i < N; ++i){
					for(int j =0; j < N; ++j){
						f[i][j] = s.nextInt();
						path[i][j] = -1;
					}
				}
				floyd();
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

}




© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 81
码字总数 30297
作品 0
海淀
程序员
考研复试系列——第七节 最短路径

考研复试系列——第七节 最短路径 前言 Floyd算法 //经过1号节点for(i=1;i<=n;i++)//遍历二维数组{for(j=1;j<=n;j++){if(e[i][j] > e[i][1] + e[1][j])//判断经过节点1是否距离更短e[i][j] =...

cassiepython ⋅ 2017/03/06 ⋅ 0

优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆 ⋅ 2011/12/03 ⋅ 0

RCP:gef智能寻路算法(A star)

本路由继承自AbstactRouter,参数只有EditPart(编辑器内容控制器),gridLength(寻路用单元格大小),style(FLOYD,FLOYDFLAT,FOURDIR)。 字符集编码为GBK,本文只做简单的代码解析,源码...

anrainie ⋅ 2014/06/12 ⋅ 0

Dijkstra算法--单源最短路径

在http://blog.csdn.net/hackerzhidian/article/details/54898064这一篇博客中总结了一下在求图的最短路中的一个算法-Floyd算法,Floyd算法用于求图的多源最短路径(多源最短路径:图的所有顶...

Hacker_ZhiDian ⋅ 2017/02/07 ⋅ 0

加权有向图----多源最短路径问题(Floyd算法)

Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。 Floyd算法能够处理带负权重的边的有向图但不能包含负权重环。 算法的基本思想是:从起始顶点...

Superheros ⋅ 2017/12/24 ⋅ 0

最短路径-Dijkstra算法和Floyd算法

Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dij...

pointerException ⋅ 2015/08/07 ⋅ 0

Johnson 全源最短路径算法

前言 上一篇文章已经阐述了Floyd-Warshall算法,适用于存在负权重路径的稠密图。本文讲述的算法适用于稀疏图。 全源最短路径求解其实是单源最短路径的推广,求解单源最短路径的两种算法时间复...

某昆 ⋅ 2017/12/15 ⋅ 0

这个代码在提交OJ时提示输出超限,求大神们解决

题目描述 由n个点和m条无向边构成的无向连通图,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 请用Dijkstr...

Arice徐新凯 ⋅ 2014/06/16 ⋅ 0

弗洛伊德算法

floyd 也就是弗洛伊德算法,是图论中用来计算任意两点间最短路径的算法。 算法的过程是: 1.把图转换成一个带权重的n阶邻接矩阵。 2.依次把1-n的节点当作桥梁,也就是中间点,例如结点u,v和中...

若晨辰 ⋅ 2012/11/14 ⋅ 0

第12周【项目 - 验证算法】

/**Copyright(c)2017,烟台大学计算机学院*All right reserved.*文件名称:20171213.cpp*作者:李小同*完成日期;2017年12月13日*版本号;v1.1**问题描述:如下*输入描述:功能需求*程序输出:...

tingke_ ⋅ 2017/12/13 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

sbt网络问题解决方案

http://dblab.xmu.edu.cn/blog/maven-network-problem/

狐狸老侠 ⋅ 5分钟前 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 48分钟前 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 54分钟前 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

马氏距离与欧氏距离

马氏距离 马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度。 如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧氏距离,如果协方差矩阵为对角阵,则其也...

漫步当下 ⋅ 昨天 ⋅ 0

聊聊spring cloud的RequestRateLimiterGatewayFilter

序 本文主要研究一下spring cloud的RequestRateLimiterGatewayFilter GatewayAutoConfiguration @Configuration@ConditionalOnProperty(name = "spring.cloud.gateway.enabled", matchIfMi......

go4it ⋅ 昨天 ⋅ 0

Spring clound 组件

Spring Cloud技术应用从场景上可以分为两大类:润物无声类和独挑大梁类。 润物无声,融合在每个微服务中、依赖其它组件并为其提供服务。 Ribbon,客户端负载均衡,特性有区域亲和、重试机制。...

英雄有梦没死就别停 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部