/* ダイクストラ法を使ってグラフの最短経路を求めるサンプルプログラム。
 *
 * このプログラムではC言語を使って簡単なグラフの構築とダイクストラ法の解説を行っている。
 * コードのライセンスはMITとする。
 *
 * グラフはノードと辺（エッジ）で構築されるデータ構造である。
 * エッジには重さが設定されており、これは距離や時間などに等しい。
 * ノードにはコストが書き込まれるがこれも始点ノードからの距離や時間になる。
 * ノードからは無数の辺が伸び、他のノードに繋がる。
 * このように経路の循環も許した構造がグラフの特徴である。
 *
 * ダイクストラ法はグラフから最短経路を求めるアルゴリズム。
 * アルゴリズムの詳細については後述。
 *
 * 執筆日: 2023-04-09
 */
#include <stdio.h>

enum {
    NODES_SIZE = 7,  // グラフのノード群の数
    EDGES_SIZE = 5,  // ノードが持つ辺の最大数
};

struct Node;  // 前方参照

// グラフの辺を表す構造体
typedef struct Edge {
    int weight;  // 重さ（この値はコストに加算される）
    struct Node *node;  // 辺の先に繋がっているノードへのポインタ
} Edge;

typedef struct Node {
    int name;  // ノードの名前。これはアルファベットで'A', 'B'などが代入される
    int cost;  // ノードに書き込まれるコスト。このコストは始点からのコスト（時間など）になる
    int state;  // ノードの確定状態。0 未確定, 1 確定済み
    struct Node *prev;  // 経路を探索するときに更新される辺で繋がっている1つ前のノード
                        // このポインタを終点ノードから始点に向かって辿っていくことで最短経路が求められる
    Edge edges[EDGES_SIZE];  // ノードから伸びる辺
} Node;

int main(void) {
    // 構築するグラフで使用されるノード群
    Node nodes[NODES_SIZE] = {
        { 'A', 0 },  // costに0が設定されているがこのノードが始点になる
        { 'B', -1 },  // -1は無限大を表す値。始点以外のノードの初期状態
        { 'C', -1 },
        { 'D', -1 },
        { 'E', -1 },
        { 'F', -1 },
        { 'G', -1 },
    };

    // nodesを使ってグラフを構築する
    // ノードのエッジ（辺）を初期化し経路を作っていく
    // たとえば
    // 
    //      nodes[0].edges[0] = (Edge) { 1, &nodes[1] };
    // 
    // というコードでは'A'のノードの0番目のエッジをweight=1, node='B'で初期化している
    // 
    nodes[0].edges[0] = (Edge) { 1, &nodes[1] };
    nodes[0].edges[1] = (Edge) { 3, &nodes[2] };
    nodes[1].edges[0] = (Edge) { 1, &nodes[0] };
    nodes[1].edges[1] = (Edge) { 4, &nodes[2] };
    nodes[1].edges[2] = (Edge) { 6, &nodes[3] };
    nodes[1].edges[3] = (Edge) { 3, &nodes[5] };
    nodes[2].edges[0] = (Edge) { 3, &nodes[0] };
    nodes[2].edges[1] = (Edge) { 4, &nodes[1] };
    nodes[2].edges[2] = (Edge) { 2, &nodes[3] };
    nodes[2].edges[3] = (Edge) { 5, &nodes[4] };
    nodes[3].edges[0] = (Edge) { 6, &nodes[1] };
    nodes[3].edges[1] = (Edge) { 2, &nodes[2] };
    nodes[3].edges[2] = (Edge) { 7, &nodes[4] };
    nodes[3].edges[3] = (Edge) { 1, &nodes[6] };
    nodes[4].edges[0] = (Edge) { 7, &nodes[3] };
    nodes[4].edges[1] = (Edge) { 5, &nodes[2] };
    nodes[4].edges[2] = (Edge) { 4, &nodes[6] };
    nodes[5].edges[0] = (Edge) { 3, &nodes[1] };
    nodes[5].edges[1] = (Edge) { 5, &nodes[6] };
    nodes[6].edges[0] = (Edge) { 5, &nodes[5] };
    nodes[6].edges[1] = (Edge) { 1, &nodes[3] };
    nodes[6].edges[2] = (Edge) { 4, &nodes[4] };

    // 以下、ダイクストラ法のアルゴリズム
    for (;;) {
        // まずノード群から未確定（state==0）ノードの中でもっともcostの値が低いノードを探す
        int min_cost = -1;
        int min_index = -1;
        for (int i = 0; i < NODES_SIZE; i++) {
            Node *node = &nodes[i];
            if (node->state == 0) {  // 未確定ノード（state==0）
                if (min_cost == -1 || 
                    (node->cost != -1 && node->cost < min_cost)) {
                    // コストが無限大だった場合を考慮し、node->costがmin_costより低いかチェック
                    // コストがmin_costより低ければmin_costとmin_indexを更新し、
                    // 最小コストのノードの添え字を求める
                    min_cost = node->cost;
                    min_index = i;
                }
            }
        }        
        // min_indexが-1という状態は先ほどの最小コストのノードの検索でノードが見つからなかった状態を表す
        // つまり確定させるノードの数が0の状態になるので、この状態になったら経路構築を終了する
        if (min_index == -1) {
            break;
        }
        Node *node = &nodes[min_index];  // 最小のコストを持つ未確定のノード
        node->state = 1;  // 最小コストのノードが求まったらそのノードの確定状態を確定（state==1）させる

        // 最小コストのノードから伸びている辺に繋がっているノードのコストを更新する
        for (int i = 0; i < EDGES_SIZE; i++) {
            Edge *edge = &node->edges[i];  // 辺のポインタ
            if (edge->node == NULL) {
                // edge->nodeがNULLというのは、この辺は使われていないことを示す
                // node->edgesは連番で初期化されていくので、nodeがNULLならこれ以降の辺は使われていない
                // 処理する辺がないのでループから抜ける
                break;
            }
            if (edge->node->state == 1) {
                // 辺に繋がっているノードの確定状態が確定済み（state==1）であるとき、
                // そのノードのコストは更新しない
                // ノードのコストの更新は未確定ノードに対してのみ行う
                continue;
            }
            // 辺の重さと最小コストのノードのコストから辺に繋がっているノードに書き込むコスト値を求める
            int cost = edge->weight + node->cost;
            if (edge->node->cost == -1 || 
                cost < edge->node->cost) {
                // 辺に繋がっているノードのコストが-1あるいはcostが辺のノードのコストより低ければ、
                // 辺に繋がっているノードのコストを更新する
                // ノードのコストの更新条件は算出した辺の重さと1つ前のノードのコストの合計値が、辺のノードより
                // 低い場合である。大きい場合は更新対象にはならない
                // これは最小コストを求めていって最短経路を算出するためである
                edge->node->cost = cost;  // 辺のノードのコストを更新
                edge->node->prev = node;  // 辺のノードのprevに最小コストのノードのポインタを繋げる
                                          // このprevのリンクが最短経路を取得する時に使われる
            }
        }
    }

    // 最短経路を算出したグラフから最短経路のノード群を求める
    Node *route[NODES_SIZE] = {0};  // 最短経路を表すノード群
    int route_index = 0;
    Node *cur = &nodes[6];  // ここのcurが終点ノードを表す。ここでは'G'のノードを指定している
                            // これはつまり始点'A'のノードから終点'G'のノードまでの最短経路を取得するということになる

    // curがNULLじゃない間、ノードのprevを始点に向かって辿っていく
    while (cur) {
        route[route_index++] = cur;  // 辿っていく過程のノードがそのまま最短経路を表すノードになる
        cur = cur->prev;
    }

    // routeを逆から出力する
    // この出力が最短経路を表すノードの繋がりになる
    for (int i = route_index - 1; i >= 0; i--) {
        Node *node = route[i];
        printf("node %c %d\n", node->name, node->cost);
    }

    // 出力結果
    // 
    // node A 0
    // node C 3
    // node D 5
    // node G 6
    // 
    return 0;
}