HiHocoder题目链接 1089 最短路径二Floyd算法

2017/04/01 Algorithm

tips: 最短路径Floyd的实现

HiHocoder题目链接:

#1089 : 最短路径·二:Floyd算法

描述

万圣节的中午,小Hi和小Ho在吃过中饭之后,来到了一个新的鬼屋!鬼屋中一共有N个地点,分别编号1..N,这N个地点之间互相有一些道路连通,两个地点之间可能有多条道路连通,但是并不存在一条两端都是同一个地点的道路。由于没有肚子的压迫,小Hi和小Ho决定好好的逛一逛这个鬼屋,逛着逛着,小Hi产生了这样的问题:鬼屋中任意两个地点之间的最短路径是多少呢?提示:其实如果你开心的话,完全可以从每个节点开始使用Dijstra算法_(:з」∠)_。

输入

每个测试点(输入文件)有且仅有一组测试数据。

在一组测试数据中:

第1行为2个整数N、M,分别表示鬼屋中地点的个数和道路的条数。

接下来的M行,每行描述一条道路:其中的第i行为三个整数u_i, v_i, length_i,表明在编号>为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。

对于100%的数据,满足N<=10^2,M<=10^3, 1 <= length_i <= 10^3。

对于100%的数据,满足迷宫中任意两个地点都可以互相到达。

输出

对于每组测试数据,输出一个N*N的矩阵A,其中第i行第j列表示,从第i个地点到达第j个地点的最短路径的长度,当i=j时这个距离应当为0。

样例输入

5 12
1 2 967
2 3 900
3 4 771
4 5 196
2 4 788
3 1 637
1 4 883
2 4 82
5 2 647
1 4 198
2 4 181
5 2 665

样例输出

0 280 637 198 394 
280 0 853 82 278 
637 853 0 771 967 
198 82 771 0 196 
394 278 967 196 0 

分析

其实执行n遍Dijkstra算法确实可以解决问题,但是HiHoCoder一句话很有道理:

O(N^2)的算法执行N次就够了,的确不用学一个O(N^3)的算法!但是,如果这个算法只有5行呢?

Floyd流程:

  1. 初始化:用minDis[i,j]代表i与j的最短距离,初始化minDis[i,j]表示在不借助任何节点的情况下,i与j的最短距离,即,i与j最短的直接相连的边的长度。

  2. 松弛,用第0个点松弛任意两个节点的距离。在用第0个点松弛的基础上,加上用第1个点松弛。依次加入新的点,直至所有点均加入。 只有4行伪代码:

for(k = 0; k < N; k++)
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
			minDis[i,j] = min(minDis[i,k] + minDis[k,j], minDis[i,j];

源代码:

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = null;
		
		scanner = new Scanner(System.in);
		int N,M;
		N = scanner.nextInt();
		M = scanner.nextInt();
		
		int[][] minDistance = new int[N][N];
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(i == j){
					minDistance[i][j] = 0;
				}else{
					minDistance[i][j] = Integer.MAX_VALUE;
				}
			}
		}
		
		for(int i = 0; i < M; i++){
			int u = scanner.nextInt() - 1;
			int v = scanner.nextInt() - 1;
			int dis = scanner.nextInt();
			
			minDistance[u][v] = minDistance[v][u] = Math.min(minDistance[u][v],dis);
		}//初始化:有边相连的节点距离为最短相连边的长度,没有边相连的距离为正无穷
		
		scanner.close();
		
		for(int k = 0; k < N; k++){//依次加入第0,1...N个点松弛最短距离
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					if(minDistance[i][k] != Integer.MAX_VALUE && minDistance[k][j] != Integer.MAX_VALUE){
						minDistance[i][j] = Math.min(minDistance[i][j], minDistance[i][k] + minDistance[k][j]);
					}
				}
			}
		}
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				System.out.print(minDistance[i][j] + " ");
			}
			System.out.println();
		}

	}

}

Search

    Table of Contents