shortpath.java

来自「这是本人对Shortpath编的算法,希望对大家有所帮助」· Java 代码 · 共 46 行

import java.util.Scanner;

public class ShortPath {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			int n = scan.nextInt();
			int[][] dis = new int[n][n];
			for (int i = 0; i < n; i++)
				// 出发的节点
				for (int j = 0; j < n; j++) {// 目标节点
					dis[i][j] = scan.nextInt();
				}

			boolean changed;
			do {
				changed = false;
				// 一次
				for (int i = 0; i < n; i++)
					// 出发的节点
					for (int j = 0; j < n; j++) {// 目标节点
						for (int z = 0; z < n; z++) {// 中介节点
							if (dis[i][j]<0||dis[i][j] > dis[i][z] + dis[z][j]) {
								dis[i][j] = dis[i][z] + dis[z][j];
								changed = true;
							}
						}
					}
			} while (changed);

			for (int i = 0; i < n; i++) {// 出发的节点
				for (int j = 0; j < n; j++) {// 目标节点
					System.out.print(dis[i][j] + " ");
				}
				System.out.println();
			}
		}
	}

}