前回のダイクストラ法では始点が一点のみでした。今回はどの点を始点にしても最短経路を求められるにします。
フロイド・ワーシャル法を用います。点Aから点Bへ行くのに点Cを経由した方が良いかどうかを全ての点の組み合わせでチェックして最短距離を更新します。
従って計算量はO(V^3)となりますが実装はとても簡単です。前回と同じ題材を使用します。
public class FloydWarshall {
public static void main(String[] args) {
String[] stations = { "横浜", "武蔵小杉", "品川", "渋谷", "新橋", "溜池山王" };
int n = stations.length;
int inf = Integer.MAX_VALUE;
int[][] cost = { { 0, 12, 28, inf, inf, inf },
{ 12, 0, 10, 13, inf, inf }, { 28, 10, 0, 11, 7, inf },
{ inf, 13, 11, 0, inf, 9 }, { inf, inf, 7, inf, 0, 4 },
{ inf, inf, inf, 9, 4, 0 } };
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
// j -> kへ行くのにiを経由した方が良いかどうか(オーバーフローを考慮してlongで計算)
long c = (long) cost[j][i] + cost[i][k];
if (c < cost[j][k]) {
cost[j][k] = (int) c;
}
}
}
}
for (int i = 0; i < n; i++) {
System.out.printf("== 始点%s ==%n", stations[i]);
for (int j = 0; j < n; j++) {
System.out.printf("%s→%s %s分%n", stations[i], stations[j],
cost[i][j]);
}
System.out.println();
}
}
}
実行結果
== 始点横浜 ==
横浜→横浜 0分
横浜→武蔵小杉 12分
横浜→品川 22分
横浜→渋谷 25分
横浜→新橋 29分
横浜→溜池山王 33分
== 始点武蔵小杉 ==
武蔵小杉→横浜 12分
武蔵小杉→武蔵小杉 0分
武蔵小杉→品川 10分
武蔵小杉→渋谷 13分
武蔵小杉→新橋 17分
武蔵小杉→溜池山王 21分
== 始点品川 ==
品川→横浜 22分
品川→武蔵小杉 10分
品川→品川 0分
品川→渋谷 11分
品川→新橋 7分
品川→溜池山王 11分
== 始点渋谷 ==
渋谷→横浜 25分
渋谷→武蔵小杉 13分
渋谷→品川 11分
渋谷→渋谷 0分
渋谷→新橋 13分
渋谷→溜池山王 9分
== 始点新橋 ==
新橋→横浜 29分
新橋→武蔵小杉 17分
新橋→品川 7分
新橋→渋谷 13分
新橋→新橋 0分
新橋→溜池山王 4分
== 始点溜池山王 ==
溜池山王→横浜 33分
溜池山王→武蔵小杉 21分
溜池山王→品川 11分
溜池山王→渋谷 9分
溜池山王→新橋 4分
溜池山王→溜池山王 0分