ワーシャルフロイド法について

またまたAtCoderの記事です。
Web開発の記事は次回の予定です。

ちなみに前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

ワーシャルフロイド法とは

全頂点の最小の重みの和（最短経路など）を求めるときに使います。
ダイクストラ法と違い、重みに負の値があるときも計算可能です。
計算量はO(V^3)なので、時間はかかります。

ただし、負の閉路（重みの和が負となる閉路）があるときは正しい答えを出せません。
しかし、負の閉路があることの検出は可能です。

説明についてはこちらのサイトがわかりやすいかなと思います。
triple-four.hatenablog.com

どのように解くのか（Javaの場合）

ライブラリを作って以下のサイトに上げました。
github.com

使い方は以下のような感じです。

//重さを格納する配列
long[][] w = new long[N][N];

//大きい値の設定
long INF = 10000000L;

//ワーシャルフロイド法用のインスタンスを作成
WF wf = new WF(c, INF);

//各重みを設定
for(int i=0; i<N; i++) {
	for(int j=0; j<N; j++) {
		c[i][j] = sc.nextLong();
	}
}

//すべての頂点間の最小の重みの和（最短距離）を返す
long[][] min_w = wf.getAllDis();

//負の閉路検出(必ずgetAllDisの後で行う)
boolean isNegativeCycle = wf.isNegativeCycle();

作ったライブラリを使って２問ほど解いてみました。

1つ目は、AtCoder Beginner Contest 079 D - Wall です。
atcoder.jp

この問題はワーシャルフロイド法を使うことさえわかってしまえば、あとは1と各数字との最小の重みの和を求めるだけです。

このように、最短経路でないときも使えるんですね。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int H = sc.nextInt();
		int W = sc.nextInt();

		long[][] c = new long[10][10];
		long INF = 10000000;
		WF wf = new WF(c, INF);
		for(int i=0; i<10; i++) {
			for(int j=0; j<10; j++) {
				c[i][j] = sc.nextLong();
			}
		}
		long[][] min_c = wf.getAllDis();

		long min_maryoku = 0;
		int[][] A = new int[H][W];
		for(int i=0; i<H; i++) {
			for(int j=0; j<W; j++) {
				A[i][j] = sc.nextInt();

				if(A[i][j] != -1 && A[i][j] != 1) {
					min_maryoku += min_c[A[i][j]][1];
				}
			}
		}

		System.out.println(min_maryoku);

	}

	//ワーシャルフロイド法
	public static class WF{
		long[][] d;
		long INF;

		public WF(long[][] d, long INF) {
			this.d = d;
			this.INF = INF;

			//初期化
			for(int i=0; i<d.length; i++) {
				Arrays.fill(d[i], INF);
			}

			//自分自身との距離を0に設定
			for(int i=0; i<d.length; i++) {
				d[i][i] = 0;
			}
		}

		//全頂点間の最短距離(重みに負の値あり)(ワーシャルフロイド法)(O(V^3))
		public long[][] getAllDis(){

			long[][] new_d = new long[d.length][d.length];
			System.arraycopy(d, 0, new_d, 0, d.length);
			for(int k=0; k<new_d.length; k++) {
				for(int i=0; i<new_d.length; i++) {
					for(int j=0; j<new_d.length; j++) {
						if(new_d[i][k] != INF && new_d[k][j] != INF) {
							new_d[i][j] = Math.min(new_d[i][j], new_d[i][k]+new_d[k][j]);
						}
					}
				}
			}

			return new_d;
		}

		//負の閉路検出(O(V))
		public boolean isNegativeCycle() {
			for(int i=0; i<d.length; i++) {
				if(d[i][i] < 0) {
					return true;
				}
			}

			return false;
		}
	}
}

2つ目は、AtCoder Beginner Contest 074 D - Restoring Road Network です。
atcoder.jp

この問題は水色diffです。
水色レベルになってくると、考察が必要になってきます。

各頂点間の最短距離がすでに与えられているので、
ワーシャルフロイド法を使って、
他の頂点を経由した方が距離が短くなる場合は-1、
別の経由地を使って最短距離と同じになる場合はその2点間のエッジを切ればよいです。

この解答ではグラフを使わず、あらかじめ与えられる最短距離をすべて加え、
エッジを切る際は代わりにその2点間の最短距離を引きます。

この時注意するのは、エッジを切った情報を記録しておかないと2種類以上最短経路がある場合種類の数だけ引いてしまうので、エッジを切った情報を記録するようにする点です。
（ここでWAを出しました。）

最終的な解答はこちらです。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		long[][] A = new long[N][N];
		long ans = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				A[i][j] = sc.nextLong();
				ans += A[i][j];
			}
		}

		//2点間がつながっているか
		boolean[][] connected = new boolean[N][N];
		for(int i=0; i<N; i++) {
			Arrays.fill(connected[i], true);
		}
		for(int i=0; i<N; i++) {
			connected[i][i] = false;
		}

		for(int k=0; k<N; k++) {
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					//別の経由地を通ったほうが距離が短くなる場合
					if(A[i][j] > A[i][k] + A[k][j]) {
						System.out.println(-1);
						return;
					}
					//別の経由地を通っても最短距離になる場合
					else if(connected[i][j] && i != k && j != k && A[i][j] == A[i][k] + A[k][j]) {
						ans -= A[i][j];
						connected[i][j] = false;	//2重で引くのを防ぐ
					}
				}
			}
		}

		//無向グラフなので2で割る
		ans /= 2;

		System.out.println(ans);

	}

}

というわけで、ワーシャルフロイド法についての記事でした。
まだ、ベルマンフォード法と最小全域木問題があるので、そこについても勉強したいと思います。
今週末はABCがないみたいなので、次回のABCまでにこの2つを勉強したいと思います。