フロイドワーシャル法

gistfile1.cpp

#include <iostream>
#include <vector>
#include <map>
#include <climits>

using namespace std;

typedef pair<int, int> Edge;
typedef map<int, int> Vertex;
typedef vector<Vertex> Graph;

void allPairsShortest(Graph const &graph,            // input
                      vector< vector<int> > &dist,   // output
                      vector< vector<int> > &pred) { // output

    int n = graph.size();
    for (int u = 0; u < n; u++) {
        dist[u].assign(n, INT_MAX);
        pred[u].assign(n, -1);
        dist[u][u] = 0;
        for (auto ci = graph[u].begin(); ci != graph[u].end(); ++ci) {
            int v = ci->first;
            dist[u][v] = ci->second;
            pred[u][v] = u;
        }
    }

    // 節点i => k => jの最短経路を計算する
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dist[i][k] == INT_MAX) {continue;} // i => kへの経路が見つかっていない
            for (int j = 0; j < n; j++) {
                long newLen = dist[i][k];
                newLen += dist[k][j];

                if (newLen < dist[i][j]) {
                    dist[i][j] = newLen;     // i => jの最短距離を書き換える
                    pred[i][j] = pred[k][j]; // i => jへの最短敵路は最後にk => jを通る
                }
            }
        }
    }

}

int main(int argc, char** argv) {

    // create graph
    Graph graph;

    Vertex v0;
    v0.insert(Edge(1, 2));
    v0.insert(Edge(4, 4));
    graph.push_back(v0);

    Vertex v1;
    v1.insert(Edge(2,3));
    graph.push_back(v1);

    Vertex v2;
    v2.insert(Edge(4,1));
    v2.insert(Edge(3,5));
    graph.push_back(v2);

    Vertex v3;
    v3.insert(Edge(0,8));
    graph.push_back(v3);

    Vertex v4;
    v4.insert(Edge(3,7));
    graph.push_back(v4);

    int n = graph.size();
    vector< vector<int> > dist(n);
    vector< vector<int> > pred(n);

    // calc
    allPairsShortest(graph, dist, pred);

    // print answer
    int src = 0;
    int dest = 3;
    cout << src << " => " << dest << "の最短距離は" << dist[src][dest] << endl;
    vector<int> route;
    int t = dest;
    while (true) {
        if (t == -1) {break;}
        route.push_back(t);
        int v = pred[src][t];
        t = v;
    }
    string delim = "";
    for (auto it = route.rbegin(); it != route.rend(); ++it) {
        cout << delim << *it;
        delim = " => ";
    }
    cout << endl;

    return 0;
}