djikstra.cpp

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

#define INF INT_MAX

// 重みを保存する(隣接行列)
int len = 7;
int matrix[7][7] = {
    { 0, 2, 3, 0, 0, 0, 0 },
    { 0, 4, 0, 1, 2, 0, 0 },
    { 0, 0, 0, 0, 0, 1, 0 },
    { 0, 0, 3, 0, 3, 0, 2 },
    { 0, 0, 0, 0, 0, 0, 2 },
    { 0, 0, 0, 0, 0, 0, 4 },
    { 0, 0, 0, 0, 0, 0, 0 }
};

// パスを出力し，最短路長を返す
int djikstra(vector <vector <int> > m, int len) {
    int shortest[len];          // 各ノードまでの最短路
    int prev[len];          // 最短路を通るとき，そのノードより前に通るノード
    prev[0] = -1;
    shortest[0] = 0;
    for (int i = 1; i < len; i++) {
        shortest[i] = INF;
    }

    for (int i = 0; i < len; i++) {
        // 最短路が未確定なノードのうち，最短で行けるノードを決める
        // O(n)
        int v = -1;
        int min_val = INF;
        for (int j = i; j < len; j++) {
            if (shortest[j] != INF && shortest[j] < min_val) {
                min_val = shortest[j];
                v = j;
            }
        }

        if (min_val == INF) break;    // 辿る枝がない

        // vの隣接ノードに対して更新する
        // 外のforループも入れてO(m)
        for (int j = 0; j < len; j++) {
            if (v == j || m[v][j] == 0) continue; // 自身か枝がない
            if (shortest[v]+m[v][j] < shortest[j]) {
                 // 更新
                shortest[j] = shortest[v]+m[v][j];
                prev[j] = v;
            }
        }
    }


    vector <int> path;
    int node = len-1;           // goal node
    path.push_back(node);
    while (prev[node] != -1) {
        node = prev[node];
        path.push_back(node);
    }
    int pathlen = (int)path.size();
    for (int i = 0; i < pathlen; i++) {
        cout << path[pathlen-i-1];
        i == pathlen-1 ? cout << endl : cout << " -> ";
    }

    return shortest[len-1];
}

int main(int argc, char **argv)
{
    vector <vector <int> > m(len, vector <int>(len));
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            m[i][j] = matrix[i][j];
        }
    }

    cout << djikstra(m, len) << endl;
    return 0;
}