试题 算法提高 多源最短路 java 题解 1057

资源限制

时间限制:3.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<=n<=1000,0<边长<=10000。


解题思路:

需要求的最短距离为任意两顶点的距离,属于多源最短距离问题,可以应用floyd算法求解。

需要注意的是,需要将给定不可达的距离为0的值重新赋为“无穷大”的值。

floyd具体算法见:

floyd算法试题 算法提高 多源最短路 java 题解 1057https://blog.csdn.net/weixin_48898946/article/details/121019298

java代码:

import java.io.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int INF = 65535;
		int [][]dis = new int[n][n];
		for(int i = 0; i < n;i++) {
			String[] split = br.readLine().split(" ");
			for(int j = 0; j < n;j++) {
				if(Integer.parseInt(split[j]) == 0) {
					dis[i][j] = INF;
				}else {
					dis[i][j] = Integer.parseInt(split[j]);
				}
			}
		}
		Graph1057 graph = new Graph1057(dis);
		graph.floyd();
		graph.print();
	}
	
}
class Graph1057{
	int n;
	int [][]dis;
	int INF = 65535;

	public Graph1057(int[][] dis) {
		this.dis = dis;
		n = dis.length;
	}
	
	public void floyd() {
		for(int k = 0; k < n;k++) {
			for(int i = 0; i < n;i++) {
				for(int j = 0; j < n;j++) {
					int len = dis[i][k] + dis[k][j];
					if(len < dis[i][j]) {
						dis[i][j] = len;
					}
				}
			}
		}
	}
	
	public void print() {
		for(int i = 0; i < n;i++) {
			for(int j = 0; j < n;j++) {
				if(i == j) {
					System.out.print("0 ");
				}else if(dis[i][j] == INF){
					System.out.print("-1 ");
				}else {
					System.out.print(dis[i][j] + " ");
				}
			}
			System.out.println();
		}
	}
}

提交截图:

试题 算法提高 多源最短路 java 题解 1057

 

上一篇:dfs实现多段图的最短路径


下一篇:玩具(Toy)