C言語で実装するダイクストラ法：非負重みグラフの最短経路アルゴリズムを解説

この記事では、C言語でダイクストラ法を実装する方法について解説します。

非負重みグラフで始点から各頂点への最短経路を求める仕組みを順を追って説明し、使用するデータ構造や実装上のポイントについても触れます。

ダイクストラ法の基本知識

ダイクストラ法は、各辺の重みが全て非負であるグラフにおいて、ある始点から各頂点への最短距離を求めるアルゴリズムです。

C言語で実装する際、シンプルな設計でありながら、アルゴリズムの特性をしっかり把握することが求められます。

非負重みグラフの定義と特徴

非負重みグラフとは、グラフ内の各辺の重みが必ず $w(u,v)\ge 0$ となるグラフのことです。

この特徴により、以下のような利点があります。

• 始点から任意の頂点までの最短距離が確定的に求められること
• 負の重みが存在しないため、探索中に距離が再度増加するケースがなく、アルゴリズムが安定して動作すること

これらの性質のおかげで、ダイクストラ法はループや再計算のコストを削減でき、効率的に最短経路が求まるアルゴリズムとなっています。

ダイクストラ法の動作原理

ダイクストラ法は、探索済みの頂点集合と未探索の頂点集合を明確に分け、始点からの暫定的な距離を更新しながら「次に最も短い距離を持つ頂点」を選択していく流れです。

初期状態は、始点の距離を 0、その他の頂点の距離を十分大きな値(無限大とみなす数値)に設定します。

アルゴリズムの進行とともに、未探索頂点の中から最も短い距離を持つ頂点を選び、その頂点から隣接する全ての頂点への距離を更新していきます。

頂点選択と距離更新の流れ

ダイクストラ法の核となる流れは以下の通りです。

• まず、すべての頂点の距離を初期化します。始点のみ距離が 0 に設定され、他は $\mathrm{\infty }$ に近い値(プログラム上では大きな定数)に設定されます。
• 未探索頂点の中から、最も小さい暫定距離を持つ頂点 u を選択します。
• 選択された頂点 u に隣接するすべての頂点 v について、経由することによって距離が短縮されるかどうかを確認します。具体的には、

$$\text{if }(distance[u]+weight(u,v)<distance[v])$$

の条件が成立すれば、distance[v] を更新します。

• このプロセスを、すべての頂点が探索対象から除外されるまで繰り返します。

使用するデータ構造の役割

ダイクストラ法の実装では、以下のようなデータ構造が主要な役割を果たします。

• 配列：各頂点の現在の最短距離を保持するために使用します。
• フラグ配列：各頂点が既に最短距離確定済みかどうかを判断するために使用します。
• 優先度付きキュー(ヒープ)：頂点選択の際、暫定距離が最も短い頂点を効率的に取り出すために利用します。
  • ただし、シンプルな実装では配列を全探索して選ぶ方法もありますが、データ数が増加するとパフォーマンス低下が顕著になります。

これらのデータ構造を適切に用いることで、アルゴリズムが正確かつ効率的に動作するようになります。

C言語実装の準備

C言語でダイクストラ法を実装する場合、まずプログラム全体の設計と構成を明確にすることが重要です。

各要素がどの役割を担うかを把握することで、コードの見通しが良くなり、後のデバッグなども容易になります。

プログラム構成と設計方針

プログラムは主に以下のようなパートに分けられます。

• データ構造の定義
  • 頂点やエッジ、グラフ自体を表現するための構造体を定義します。
• 定数設定・ヘッダファイルのインクルード
  • 重要な定数(例：無限大を表す定数 INF)や必要なライブラリ(例：stdio.h、stdlib.h)をインクルードします。
• アルゴリズム実装
  • ダイクストラ法の主要な計算部分を dijkstra() 関数として実装し、必要に応じて補助関数も作成します。
• 入出力処理
  • グラフの入力処理や、最終的な最短経路の出力処理を別個に実装します。

こうしたモジュール分けにより、プログラムが大規模になった場合でも管理が容易になります。

ヘッダファイルと定数定義

ヘッダファイルでは、標準ライブラリの他に、グラフ構造やアルゴリズムで利用する定数を定義します。

例えば、以下のような定義が考えられます。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>   // INT_MAX を使用する場合に必要
#define INF 1000000   // 無限大の代わりに利用する大きな定数
#define MAX_VERTICES 100  // グラフの最大頂点数の例

このような定義は、後の実装部分でも共通して使用され、可読性の向上に寄与します。

グラフ表現方法の選択

グラフの表現方法として、主に以下の2通りの方法が考えられます。

• 隣接行列方式
  • $O(V^2)$ のメモリを使用し、頂点数が小さい場合に適しています。
• 隣接リスト方式
  • メモリ使用量を節約でき、大規模なグラフに適しています。

以下の表は、両方式の比較を示しています。

実装するグラフの規模に合わせた表現方法を選択することが重要です。

開発環境とライブラリ

ダイクストラ法の実装は、C言語の標準ライブラリのみで十分に行うことができます。

開発環境は既に構築済みとして、以下の点を確認してください。

• コンパイラは GCC などの標準的な C コンパイラを使用
• ビルド手法は、Makefile を用いるか、コンパイルコマンドを直接使用するかを検討してください。
• 必要に応じてデバッガ(gdbなど)を利用し、動作確認を行います。

コンパイラ設定とビルド手法

サンプルコードのコンパイルには、以下のようなコマンドがよく利用されます。

gcc -Wall -Wextra -o dijkstra dijkstra.c

• -Wall と -Wextra は、警告を表示するためのオプションです。
• 出来上がった実行ファイルは ./dijkstra で実行可能です。

また、Makefile を利用する場合、コンパイル手順が自動化されるため、複数ファイルからなるプロジェクトでは特に有効です。

実装手順と詳細解説

実際の実装では、各処理を関数に分割し、役割ごとに実装内容を整理することが大切です。

ここでは初期の設定から、主要なアルゴリズム計算部分に至るまでの手順について解説します。

初期化処理の実装

初期化処理では、まず全頂点の距離を初期化し、各頂点の状態(訪問済みか未訪問か)を管理するための配列を準備します。

例えば、以下のような処理が行われます。

• distance 配列を INF で初期化し、始点だけ 0 に設定する。
• visited 配列を全頂点分用意し、初期状態ではすべて false に設定する。
• グラフのデータ構造の各要素を確保し、エッジ情報を取得するための領域を動的確保する。

こうした初期化は、アルゴリズム全体の正しい動作の基礎となるため、慎重に実装する必要があります。

ダイクストラ法のメインループ

ダイクストラ法のメインループは、未探索頂点の中から最小の距離を持つ頂点を選択し、その頂点から隣接する各頂点への距離を更新する部分です。

ループの各ステップで、最小距離の頂点の選択と、距離更新が正確に行われるかどうかがアルゴリズムの成否を分けます。

アルゴリズムフローの処理

アルゴリズムの流れは以下のとおりです。

1. 未探索頂点から、distance 配列の値が最も小さい頂点 u を選択する。
2. もし u の距離が INF であれば、残りの頂点は到達不能と判断し、ループを終了する。
3. 頂点 u を訪問済みとしてマークし、隣接する各頂点 v について、

$$distance[u]+weight(u,v)<distance[v]$$

の場合に distance[v] を更新する。

4. 以上の処理を、すべての頂点が訪問済みになるまで繰り返す。

この流れにより、経由する経路が更新され、最終的に始点から各頂点への最短経路が確定されます。

距離更新ロジックの実装

距離更新の部分は、隣接する頂点 v に対して実際に候補経路の評価を行う処理です。

具体的には、以下のようなコードが典型的です。

// 頂点 u から頂点 v への距離を更新する例
if (!visited[v] && (distance[u] + weight[u][v] < distance[v])) {
    distance[v] = distance[u] + weight[u][v];  // 最短経路の距離を更新
    // 必要に応じて、経路の前駆頂点情報を更新する
}

この処理により、各頂点への最短距離が適切に再計算され、アルゴリズム全体の正確性が保たれます。

エラー処理とメモリ管理

C言語における動的メモリ管理は、実装の信頼性に直結します。

以下の点に注意してください。

• 動的に確保したメモリが正しく NULL チェックされているか
• 不要になったメモリが必ず free() で解放されるか
• ファイル入出力や標準入力からの読み込みにおいて、エラーケースを想定した処理が記述されているか

エラー処理が適切に実装されていれば、予期せぬ入力やリソース不足の状況に対しても安全に対処できます。

サンプルコードの構造と解説

ここでは、サンプルコード全体の構成および各関数の役割について解説します。

コード内には、適宜コメントを記載し、どの部分がどのような役割を果たしているかが分かるようにしています。

全体のプログラム構成

サンプルコードは、以下の各パートに分けられています。

• ヘッダファイルと定数定義
• グラフを表現する構造体や、エッジ情報の定義
• 初期化、ダイクストラ法の計算を行う関数
• 入出力および結果表示のための補助関数
• main() 関数内での各関数呼び出しの流れ

この構成により、コードが拡張される際にも各パート間の依存が最小限となっており、メンテナンスしやすくなっています。

各関数の役割と連携

プログラム内には、以下に示す主要な関数が含まれています。

ダイクストラ法の主要関数

dijkstra()関数は、実際に最短経路を計算する関数です。

この関数では、以下の処理が行われます。

• 頂点の初期化(距離および訪問フラグ)
• メインループによる頂点選択と距離更新
• 最適経路の記録と、最終結果の配列への格納

関数内で使用されるループや条件分岐は、上述したアルゴリズムフローに沿って実装されており、データ構造の状態が一貫して管理されるように工夫されています。

グラフ入力および出力処理

グラフの情報は、ユーザーの入力やファイルから読み取る場合が考えられます。

入力処理用の関数(例：readGraph())は、グラフの頂点数、各辺の接続情報および重み情報を正確に読み込み、内部データ構造に格納します。

また、出力処理の関数は、計算された最短経路とその距離を分かりやすく表示するための処理を実装しています。

以下に、サンプルコードの一部例を示します。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define INF 1000000
#define MAX_VERTICES 100
// グラフ構造体の定義
typedef struct {
    int numVertices;
    int weights[MAX_VERTICES][MAX_VERTICES];
} Graph;
// 初期化処理
void initialize(Graph *graph, int vertices) {
    graph->numVertices = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            if (i == j)
                graph->weights[i][j] = 0;
            else
                graph->weights[i][j] = INF;
        }
    }
    // サンプルとして、一部のエッジを設定
    // 「Edge from vertex 0 to 1 with weight 10」
    graph->weights[0][1] = 10;
    // 「Edge from vertex 0 to 2 with weight 3」
    graph->weights[0][2] = 3;
    // 「Edge from vertex 1 to 2 with weight 1」
    graph->weights[1][2] = 1;
}
// ダイクストラ法の実装
void dijkstra(Graph *graph, int start, int distance[]) {
    int visited[MAX_VERTICES] = {0};
    int n = graph->numVertices;
    // 全頂点の距離を初期化
    for (int i = 0; i < n; i++) {
        distance[i] = INF;
    }
    distance[start] = 0;
    // 各頂点について最短距離を探索
    for (int i = 0; i < n; i++) {
        int u = -1;
        int minDistance = INF;
        // 未訪問頂点の中から最小距離の頂点 u を選択
        for (int j = 0; j < n; j++) {
            if (!visited[j] && distance[j] < minDistance) {
                minDistance = distance[j];
                u = j;
            }
        }
        if (u == -1) break;  // 到達可能な頂点が無い場合
        visited[u] = 1;
        // 頂点 u 経由で各頂点への距離を更新
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph->weights[u][v] != INF &&
                distance[u] + graph->weights[u][v] < distance[v]) {
                distance[v] = distance[u] + graph->weights[u][v];
            }
        }
    }
}
// グラフ情報と最短距離の表示
void printShortestPaths(int distance[], int vertices) {
    printf("Shortest distances from source:\n");
    for (int i = 0; i < vertices; i++) {
        if (distance[i] == INF)
            printf("Vertex %d: INF\n", i);
        else
            printf("Vertex %d: %d\n", i, distance[i]);
    }
}
int main() {
    Graph graph;
    int vertices = 4;  // サンプルとして4頂点のグラフ
    initialize(&graph, vertices);
    int distances[MAX_VERTICES];
    int source = 0;  // 始点は頂点0
    dijkstra(&graph, source, distances);
    printShortestPaths(distances, vertices);
    return 0;
}

Shortest distances from source:
Vertex 0: 0
Vertex 1: 10
Vertex 2: 3
Vertex 3: INF

上記のサンプルコードは、グラフの初期化、ダイクストラ法による最短経路の計算、結果表示までの一連の流れを示しています。

各関数の役割が明確で、コード内のコメントも参照すれば理解しやすい構造となっています。

まとめ

この記事では、ダイクストラ法の基本や非負重みグラフの定義、頂点選択と距離更新の流れ、各種データ構造の役割について解説しています。

また、C言語による実装準備から初期化、メインループ、エラー処理までの詳細な手順と、サンプルコードを用いた実際のプログラム構成について説明しています。

この記事を通して、ダイクストラ法の理論と実装方法の両面が理解できる内容となっています。