単一始点からグラフ内の全頂点への最短距離を算出する代表的な手法として、ダイクストラ法（Dijkstra's Algorithm）が広く利用されています。本アルゴリズムは、すべての辺の重みが非負である場合に限り、正確な最適解を保証します。

アルゴリズムの動作原理

処理の手順は以下の通りです。

1. 始点の距離を 0 に設定し、他の全頂点の距離を無限大（∞）で初期化します。同時に、全頂点を「未確定」状態にします。
2. 未確定の頂点群の中から、現在の距離値が最小の頂点を選択し、それを「確定」状態へ遷移させます。
3. 確定頂点から伸びるすべての出辺を走査します。隣接頂点までの距離が、「始点から確定頂点までの距離 ＋ 辺の重み」よりも短くなる場合（緩和条件）、隣接頂点の距離を更新します。
4. 全頂点が確定状態になるまで、手順2～3を繰り返します。

辺の重みが負でない場合、一度確定された最短距離は他の経路によって上書きされることはありません。この貪欲法の性質により、逐次的に最短経路木が構築されていきます。負の重みが存在する場合、この仮定が崩れるためアルゴリズムは機能しません。

隣接リストによるグラフの表現

メモリ効率を考慮し、頂点とその接続情報を隣接リスト形式で管理します。配列を用いて各頂点の最初の辺のインデックスを保持し、辺構造体には接続先、重み、次の辺へのリンクを格納します。

struct EdgeData {
    int destination;
    long long weight;
    int next_link;
};

EdgeData adj_list[200010];
int first_edge_idx[100010];
int edge_counter = 0;

void register_edge(int src, int dest, long long w) {
    edge_counter++;
    adj_list[edge_counter].destination = dest;
    adj_list[edge_counter].weight = w;
    adj_list[edge_counter].next_link = first_edge_idx[src];
    first_edge_idx[src] = edge_counter;
}

特定の頂点 u に接続された辺を反復処理する際は、以下のようにリンクを辿ります。

for (int idx = first_edge_idx[u]; idx != 0; idx = adj_list[idx].next_link) {
    int v = adj_list[idx].destination;
    long long cost = adj_list[idx].weight;
    if (shortest_dist[v] > shortest_dist[u] + cost) {
        shortest_dist[v] = shortest_dist[u] + cost;
        path_prev[v] = u;
        min_heap.push({shortest_dist[v], v});
    }
}

問題設定と完全な実装

典型的な応用例として、N 頂点・M 辺の重み付き無向グラフが与えられ、頂点 1 から頂点 N への最短経路を出力する課題を考えます。到達不能の場合は -1 を返します。制約は 2 ≤ N, M ≤ 10^5、辺の重みは 1 ≤ w ≤ 10^6 です。自己ループや多重辺の存在も許容されます。

実装上の留意点として、無向グラフのため辺の格納領域は入力数の倍確保する必要があります。また、経路総和が 32 ビット整数の上限を超える可能性があるため、距離計算には long long 型を採用し、初期の無限大には 1e18 程度の値を設定します。経路復元には直前の頂点を記録する配列を用い、ゴールから始点へ逆方向に辿ることで解を構築します。

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

using ll = long long;
const ll INF_VAL = 1e18;
const int MAX_NODES = 100005;

struct Edge {
    int to_node;
    ll cost;
    int next_idx;
};

Edge graph[MAX_NODES * 2];
int head_ptr[MAX_NODES];
int edge_count = 0;

void link_nodes(int u, int v, ll w) {
    graph[++edge_count].to_node = v;
    graph[edge_count].cost = w;
    graph[edge_count].next_idx = head_ptr[u];
    head_ptr[u] = edge_count;
}

ll dist_table[MAX_NODES];
int predecessor[MAX_NODES];
bool finalized[MAX_NODES];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    memset(head_ptr, 0, sizeof(head_ptr));
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        link_nodes(u, v, w);
        link_nodes(v, u, w);
    }

    fill(dist_table, dist_table + n + 1, INF_VAL);
    memset(finalized, 0, sizeof(finalized));
    dist_table[1] = 0;

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [current_d, u] = pq.top();
        pq.pop();

        if (finalized[u]) continue;
        finalized[u] = true;

        for (int e = head_ptr[u]; e != 0; e = graph[e].next_idx) {
            int v = graph[e].to_node;
            ll w = graph[e].cost;
            if (dist_table[v] > dist_table[u] + w) {
                dist_table[v] = dist_table[u] + w;
                predecessor[v] = u;
                pq.push({dist_table[v], v});
            }
        }
    }

    if (dist_table[n] == INF_VAL) {
        cout << -1 << "\n";
    } else {
        vector<int> route;
        int curr = n;
        while (true) {
            route.push_back(curr);
            if (curr == 1) break;
            curr = predecessor[curr];
        }
        for (int i = route.size() - 1; i >= 0; --i) {
            cout << route[i] << (i == 0 ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}