---
title: フロイド・ワーシャル法で全点対最短経路問題
tags: []
categories: ["Programming", "Algorithm", "Search", "FloydWarshall"]
date: 2011-07-23T17:30:24Z
updated: 2011-07-23T17:30:24Z
---

[前回][1]のダイクストラ法では始点が一点のみでした。今回はどの点を始点にしても最短経路を求められるにします。

フロイド・ワーシャル法を用います。点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分

  [1]: http://blog.ik.am/entry/view/id/79/title/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95%E3%81%A7%E5%8D%98%E4%B8%80%E5%A7%8B%E7%82%B9%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E8%A8%88%E7%AE%97/125