floyd算法学习
博客专区 > aqia358 的博客 > 博客详情
floyd算法学习
aqia358 发表于4年前
floyd算法学习
  • 发表于 4年前
  • 阅读 19
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

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();
		}
	}

}




标签: floyd java
共有 人打赏支持
粉丝 6
博文 81
码字总数 30297
×
aqia358
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: