Java教程

多元最短路-Floyd算法

本文主要是介绍多元最短路-Floyd算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

时间限制:5.0s 内存限制:256.0MB

问题描述

   给定\(n\)个结点两两之间的单向边的长度,求两两之间的最短路径。

输入格式

   输入第一行包含一个整数\(n\),表示点数。
   接下来\(n\)行,每行包含\(n\)个整数,第\(i\)行表示第\(i\)个点到每个点的边的长度,如果没有边,则用\(0\)表示。

输出格式

   输出\(n\)行,第\(i\)行表示第\(i\)个点到其他点的最短路径长度,如果没有可达的路径,则输出\(-1\)。

样例输入

 3
 0 1 0
 0 0 6
 0 2 0

样例输出

 0 1 7
 -1 0 6
 -1 2 0

数据规模和约定

   \(1\leq n\leq 1000\),\(0<\)边长\(\leq 10000\)。

解析

Floyd 算法:

   \(a_{ij} 表示\)i\(到\)j\(之间的边长,当\)i\(到\)j$之间没有变时取无限大.
   \(f_{kij}\) 表示\(i\)到\(j\)允许使用节点\(1~k\)作为中间节点.
   目标:\(f_{nij}\)
   初值:\(f_{0ij} = a_{ij}\) 表示从\(i\)到\(j\)不允许经过其他节点作为中间节点,所以\(i\)到\(j\)的距离就是\(a_{ij}\)。
   转移方程:$f_{kij} = min(f_{k-1ij}, f_{k-1ik} + f_{k-1kj})
不用k点作为中间节点 用
   因为用三维数组内存超大,需要优化

优化:

   可以压缩一个维度————k
   可以使用滚动数组,只需f[2][n][n],大大减小了数组内存占用
   于是f[k % 2][i][j] = min(f[(k - 1) % 2][i][j], f[(k - 1) % 2][i][k] + f[(k - 1) % 2][k][j])

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 1e9;
int a[1005][1005];
int f[2][1005][1005];

int main(int argc, char** argv) {
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
			if (a[i][j] != 0) f[0][i][j] = a[i][j];
			else if (i != j) f[0][i][j] = INF;
		}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				f[k % 2][i][j] = min(f[(k - 1) % 2][i][j], f[(k - 1) % 2][i][k] + f[(k - 1) % 2][k][j]);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (f[n % 2][i][j] == INF) cout << -1 << " ";
			else cout << f[n % 2][i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}
这篇关于多元最短路-Floyd算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!