アルゴリズム概要

• 適用範囲: 非負重み付き有向グラフ/無向グラフにおける最短経路探索
• 計算量: 隣接行列実装の場合O(V²)、優先度付きキュー使用でO((E+V)logV)
• 特徴: 始点から最短距離が確定したノード群を段階的に拡張する手法

実装ロジック

1. 初期化: 距離配列を無限大で埋め、始点距離を0に設定
2. 未確定ノードの中から最小距離のノードを選択
3. 選択ノードを経由することで短縮可能な距離を更新
4. 全ノードが確定するまで反復

データ構造

コード例（C++）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 510;

int graph[MAX][MAX], dist[MAX];
bool visited[MAX];

int dijkstra(int nodes) {
    memset(dist, INF, sizeof dist);
    dist[1] = 0;
    
    for(int i=1; i<=nodes-1; ++i) {
        int minNode = -1;
        for(int j=1; j<=nodes; ++j) {
            if(!visited[j] && (minNode == -1 || dist[j] < dist[minNode])) {
                minNode = j;
            }
        }
        
        if(minNode == -1) break;
        visited[minNode] = true;
        
        for(int k=1; k<=nodes; ++k) {
            if(dist[k] > dist[minNode] + graph[minNode][k]) {
                dist[k] = dist[minNode] + graph[minNode][k];
            }
        }
    }
    
    return dist[nodes] == INF ? -1 : dist[nodes];
}

int main() {
    int n, m;
    cin >> n >> m;
    
    memset(graph, INF, sizeof graph);
    for(int i=0; i> a >> b >> c;
        if(graph[a][b] > c) graph[a][b] = c;
    }
    
    cout << dijkstra(n) << endl;
    return 0;
}

応用改造

任意の終点までの経路探索を行う場合、関数パラメータに終点指定機能を追加できます。

int dijkstra(int nodes, int target) {
    // ...略
    return dist[target] == INF ? -1 : dist[target];
}

// 呼び出し例
int target;
cin >> target;
cout << dijkstra(n, target) << endl;

注意点

• 重みが負の辺が存在する場合は使用不可
• 多重辺が存在する場合、最小重みのみを保持
• 自己ループは自動的に排除される