[C言語] ダイクストラ法を実装して経路探索を行う方法

Q: ダイクストラ法とベルマンフォード法の違いは？

ダイクストラ法とベルマンフォード法の主な違いは以下の通りです。 適用条件 : ダイクストラ法は非負の重みを持つグラフに適用可能ですが、ベルマンフォード法は負の重みを持つ辺を含むグラフにも対応できます。 計算量 : ダイクストラ法は、優先度付きキューを使用することで、計算量が \(O((V + E) \log V)\) となります。 一方、ベルマンフォード法は、計算量が \(O(V \cdot E)\) であり、特に辺の数が多い場合には効率が悪くなります。 経路の復元 : 両者とも経路の復元が可能ですが、ダイクストラ法は最短距離を確定させる過程で親情報を保持することが一般的です。 ベルマンフォード法も同様に親情報を保持しますが、負の重みの影響を受けるため、経路の復元が複雑になることがあります。

Q: ダイクストラ法の計算量はどれくらいですか？

ダイクストラ法の計算量は、使用するデータ構造によって異なります。 一般的には以下のようになります。 隣接行列を使用する場合 : 計算量は \(O(V^2)\) です。 これは、全ての頂点に対して隣接行列を参照する必要があるためです。 隣接リストと優先度付きキューを使用する場合 : 計算量は \(O((V + E) \log V)\) です。 ここで、Vは頂点の数、Eは辺の数です。 優先度付きキューを使用することで、未訪問頂点の選択が効率的に行えるため、全体の計算量が改善されます。 このように、ダイクストラ法の計算量は、グラフの構造や使用するデータ構造によって大きく変わるため、適切な選択が重要です。

ダイクストラ法は、グラフ上の最短経路を求めるアルゴリズムです。

C言語で実装する際には、まずグラフを隣接行列や隣接リストで表現します。

次に、各頂点の最短距離を格納する配列と、訪問済みかどうかを管理する配列を用意します。

初期状態では、始点の距離を0、他の頂点の距離を無限大に設定します。

未訪問の頂点の中から最短距離の頂点を選び、その頂点を経由して他の頂点への距離を更新します。

これを全頂点が訪問されるまで繰り返します。

この記事でわかること

ダイクストラ法の基本的な概念
アルゴリズムの流れと実装方法
最適化手法の具体例
ダイクストラ法の応用分野
他のアルゴリズムとの比較ポイント

目次から探す

ダイクストラ法とは

ダイクストラ法の概要

ダイクストラ法は、グラフ理論における最短経路探索アルゴリズムの一つです。

特に、非負の重みを持つ辺を持つグラフにおいて、指定した始点から他の全ての頂点への最短経路を求めることができます。

このアルゴリズムは、1956年にエドガー・ダイクストラによって提案されました。

ダイクストラ法の特徴

非負の重み: ダイクストラ法は、辺の重みが全て非負であることが前提です。
効率性: 計算量は、隣接リストを使用した場合、\(O((V + E) \log V)\) であり、Vは頂点数、Eは辺の数です。
単一始点: 一度に一つの始点からの最短経路を求めることができます。
経路の復元: 最短経路を求めるだけでなく、経路を復元することも可能です。

ダイクストラ法が適用できる問題

ダイクストラ法は以下のような問題に適用できます。

スクロールできます

問題の種類	説明
地図上の経路探索	交通網や地図アプリでの最短経路探索に利用されます。
ネットワークの最適化	データパケットの最適なルートを決定する際に使用されます。
ロボットの経路計画	ロボットが障害物を避けながら目的地に到達するための経路を計算します。
ゲームAIの経路探索	ゲーム内キャラクターの移動経路を決定するために使用されます。

ダイクストラ法と他のアルゴリズムの比較

ダイクストラ法は他の最短経路アルゴリズムと比較して、特定の条件下での利点と欠点があります。

以下の表に示します。

スクロールできます

アルゴリズム名	特徴	適用条件
ダイクストラ法	非負の重みのグラフに適用可能。最短経路を効率的に求める。	辺の重みが全て非負であること。
ベルマンフォード法	負の重みを持つ辺にも対応可能。全ての頂点に対して最短経路を求める。	負の重みの辺が存在する場合。
A*アルゴリズム	ヒューリスティックを用いて探索を効率化。特定の条件下で最適。	目的地が明確で、ヒューリスティックが有効な場合。

ダイクストラ法のアルゴリズムの流れ

グラフの表現方法

ダイクストラ法を実装するためには、グラフを適切に表現する必要があります。

主に以下の2つの方法があります。

スクロールできます

表現方法	説明
隣接行列	グラフの頂点数に対して2次元配列を用意し、辺の重みを格納します。
隣接リスト	各頂点に対して、その頂点に接続されている頂点と重みをリスト形式で格納します。

隣接行列は簡単に実装できますが、メモリ効率が悪く、辺が少ないグラフには不向きです。

一方、隣接リストはメモリ効率が良く、辺の数が少ないグラフに適しています。

初期化の手順

ダイクストラ法の初期化では、以下の手順を行います。

最短距離配列の初期化: 始点の距離を0、他の頂点の距離を無限大に設定します。
訪問済み配列の初期化: 全ての頂点を未訪問として設定します。
優先度付きキューの初期化: 始点をキューに追加します。

この初期化により、アルゴリズムが正しく動作するための準備が整います。

最短距離の更新方法

最短距離の更新は、現在の頂点から隣接する頂点への距離を計算し、必要に応じて最短距離配列を更新します。

具体的には以下の手順です。

現在の頂点から隣接する頂点への距離を計算します。
計算した距離が、隣接する頂点の現在の距離よりも小さい場合、最短距離配列を更新します。
更新した頂点を優先度付きキューに追加します。

このプロセスを繰り返すことで、最短距離が徐々に確定していきます。

未訪問頂点の選択方法

未訪問頂点の選択は、優先度付きキューを使用して行います。

具体的な手順は以下の通りです。

キューから最小の距離を持つ頂点を取り出します。
取り出した頂点を訪問済みとしてマークします。
その頂点から隣接する未訪問頂点に対して、最短距離の更新を行います。

この方法により、常に最も近い頂点を選択することができます。

アルゴリズムの終了条件

ダイクストラ法のアルゴリズムは、以下の条件で終了します。

全ての頂点が訪問済みになる: すべての頂点が訪問され、最短距離が確定した時点で終了します。
優先度付きキューが空になる: キューに未訪問の頂点がなくなった場合も終了します。

この終了条件により、アルゴリズムは効率的に最短経路を求めることができます。

C言語でのダイクストラ法の実装準備

必要なデータ構造

ダイクストラ法をC言語で実装するためには、以下のデータ構造が必要です。

スクロールできます

データ構造	説明
配列	最短距離を格納するための配列。
配列	各頂点の訪問状態を管理するための配列。
構造体	グラフの頂点や辺を表現するための構造体。
優先度付きキュー	未訪問の頂点を効率的に管理するためのデータ構造。

これらのデータ構造を適切に組み合わせることで、ダイクストラ法を効率的に実装できます。

隣接行列と隣接リストの選択

グラフの表現方法として、隣接行列と隣接リストのどちらかを選択する必要があります。

隣接行列:
メリット: 実装が簡単で、辺の存在確認がO(1)で行える。
デメリット: メモリ消費が大きく、辺が少ないグラフには不向き。
隣接リスト:
メリット: メモリ効率が良く、辺の数が少ないグラフに適している。
デメリット: 実装がやや複雑で、辺の存在確認がO(V)かかる。

グラフの特性に応じて、適切な表現方法を選択します。

無限大の表現方法

ダイクストラ法では、最短距離が未確定の頂点を「無限大」として扱います。

C言語では、以下のように定数を定義することが一般的です。

#define INF 99999999  // 無限大を表す定数

この定数を使用することで、最短距離の初期化や更新処理が容易になります。

頂点と辺の管理方法

グラフの頂点と辺を管理するためには、構造体を使用することが一般的です。

以下は、頂点と辺を表現するための構造体の例です。

typedef struct {
    int vertex;  // 頂点の番号
    int weight;  // 辺の重み
} Edge;
typedef struct {
    int numVertices;  // 頂点の数
    Edge** adjList;   // 隣接リスト
} Graph;

このように構造体を定義することで、グラフの情報を効率的に管理できます。

隣接リストを使用する場合、各頂点に対してその頂点に接続されている辺の情報を格納します。

ダイクストラ法のC言語実装

初期化処理の実装

ダイクストラ法の初期化処理では、最短距離配列と訪問済み配列を設定します。

以下はその実装例です。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>  // INT_MAXを使用するため
#define INF INT_MAX  // 無限大を表す定数
void initialize(int numVertices, int* distance, int* visited, int start) {
    for (int i = 0; i < numVertices; i++) {
        distance[i] = INF;  // 最短距離を無限大で初期化
        visited[i] = 0;      // 未訪問として初期化
    }
    distance[start] = 0;  // 始点の距離を0に設定
}

この関数では、最短距離配列distanceを無限大で初期化し、訪問済み配列visitedを未訪問として設定します。

始点の距離は0に設定します。

最短距離配列の更新処理

最短距離配列の更新処理では、現在の頂点から隣接する頂点への距離を計算し、必要に応じて最短距離を更新します。

以下はその実装例です。

void updateDistances(int numVertices, int* distance, int* visited, int** adjMatrix, int current) {
    for (int i = 0; i < numVertices; i++) {
        if (adjMatrix[current][i] != 0 && !visited[i]) {  // 隣接かつ未訪問の場合
            int newDistance = distance[current] + adjMatrix[current][i];  // 新しい距離を計算
            if (newDistance < distance[i]) {
                distance[i] = newDistance;  // 最短距離を更新
            }
        }
    }
}

この関数では、隣接行列adjMatrixを使用して、現在の頂点から隣接する頂点への距離を計算し、最短距離を更新します。

未訪問頂点の選択処理

未訪問頂点の選択処理では、最短距離が最小の未訪問頂点を選択します。

以下はその実装例です。

int selectMinVertex(int numVertices, int* distance, int* visited) {
    int minVertex = -1;
    for (int i = 0; i < numVertices; i++) {
        if (!visited[i] && (minVertex == -1 || distance[i] < distance[minVertex])) {
            minVertex = i;  // 最小の距離を持つ未訪問頂点を選択
        }
    }
    return minVertex;
}

この関数では、最短距離配列distanceを参照し、最小の距離を持つ未訪問頂点を選択します。

経路の復元方法

経路の復元は、最短経路を求めるために、親情報を保持することで実現できます。

以下はその実装例です。

void printPath(int* parent, int vertex) {
    if (vertex == -1) return;  // 親がいない場合は終了
    printPath(parent, parent[vertex]);  // 再帰的に親を辿る
    printf("%d ", vertex);  // 現在の頂点を出力
}

この関数では、親配列parentを使用して、最短経路を再帰的に出力します。

親情報は、最短距離を更新する際に記録しておく必要があります。

実装の全体像

ダイクストラ法の全体的な実装は以下のようになります。

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define INF INT_MAX
void initialize(int numVertices, int* distance, int* visited, int start);
void updateDistances(int numVertices, int* distance, int* visited,
                     int** adjMatrix, int current);
int selectMinVertex(int numVertices, int* distance, int* visited);
void printPath(int* parent, int vertex);

void initialize(int numVertices, int* distance, int* visited, int start) {
    for (int i = 0; i < numVertices; i++) {
        distance[i] = INF; // 最短距離を無限大で初期化
        visited[i] = 0;    // 未訪問として初期化
    }
    distance[start] = 0; // 始点の距離を0に設定
}

void updateDistances(int numVertices, int* distance, int* visited,
                     int** adjMatrix, int current) {
    for (int i = 0; i < numVertices; i++) {
        if (adjMatrix[current][i] != 0 && !visited[i]) { // 隣接かつ未訪問の場合
            int newDistance =
                distance[current] + adjMatrix[current][i]; // 新しい距離を計算
            if (newDistance < distance[i]) {
                distance[i] = newDistance; // 最短距離を更新
            }
        }
    }
}

int selectMinVertex(int numVertices, int* distance, int* visited) {
    int minVertex = -1;
    for (int i = 0; i < numVertices; i++) {
        if (!visited[i] &&
            (minVertex == -1 || distance[i] < distance[minVertex])) {
            minVertex = i; // 最小の距離を持つ未訪問頂点を選択
        }
    }
    return minVertex;
}

void printPath(int* parent, int vertex) {
    if (vertex == -1) return;          // 親がいない場合は終了
    printPath(parent, parent[vertex]); // 再帰的に親を辿る
    printf("%d ", vertex);             // 現在の頂点を出力
}

void dijkstra(int numVertices, int** adjMatrix, int start) {
    int* distance = (int*)malloc(numVertices * sizeof(int));
    int* visited = (int*)malloc(numVertices * sizeof(int));
    int* parent = (int*)malloc(numVertices * sizeof(int)); // 親配列
    initialize(numVertices, distance, visited, start);
    for (int i = 0; i < numVertices - 1; i++) {
        int current = selectMinVertex(numVertices, distance, visited);
        visited[current] = 1; // 現在の頂点を訪問済みにする
        updateDistances(numVertices, distance, visited, adjMatrix, current);
    }
    // 結果の出力
    for (int i = 0; i < numVertices; i++) {
        printf("頂点 %d までの最短距離: %d\n", i, distance[i]);
    }
    free(distance);
    free(visited);
    free(parent);
}
int main() {
    int numVertices = 5; // 頂点の数
    int** adjMatrix = (int**)malloc(numVertices * sizeof(int*));
    for (int i = 0; i < numVertices; i++) {
        adjMatrix[i] = (int*)malloc(numVertices * sizeof(int));
    }
    // 隣接行列の初期化(例)
    // 0は辺がないことを示す
    int exampleMatrix[5][5] = {
        {0,   10, 0,  30, 100},
        {10,  0,  50, 0,  0  },
        {0,   50, 0,  20, 10 },
        {30,  0,  20, 0,  60 },
        {100, 0,  10, 60, 0  }
    };
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            adjMatrix[i][j] = exampleMatrix[i][j];
        }
    }
    dijkstra(numVertices, adjMatrix, 0); // 始点は0
    for (int i = 0; i < numVertices; i++) {
        free(adjMatrix[i]);
    }
    free(adjMatrix);
    return 0;
}

このコードは、ダイクストラ法を用いて最短経路を求める全体の流れを示しています。

隣接行列を用いてグラフを表現し、最短距離を計算して結果を出力します。

実装の最適化

優先度付きキューを使った高速化

ダイクストラ法の実装において、未訪問頂点の選択処理を効率化するために、優先度付きキューを使用することが重要です。

優先度付きキューを用いることで、最小の距離を持つ頂点をO(log V)の時間で選択できるため、全体の計算時間を大幅に短縮できます。

C言語では、ヒープを利用した優先度付きキューの実装が一般的です。

以下は、優先度付きキューの基本的な操作を示す例です。

typedef struct {
    int vertex;
    int distance;
} Node;
typedef struct {
    Node* nodes;
    int size;
} PriorityQueue;
void insert(PriorityQueue* pq, Node node) {
    // ノードを挿入する処理
}
Node extractMin(PriorityQueue* pq) {
    // 最小のノードを取り出す処理
}

このように、優先度付きキューを使用することで、未訪問頂点の選択が効率的に行えます。

ヒープを用いた実装

優先度付きキューの実装には、ヒープデータ構造を使用することが一般的です。

ヒープを用いることで、挿入や削除の操作がO(log V)で行えるため、ダイクストラ法の全体の計算量を改善できます。

以下は、最小ヒープの基本的な操作を示す例です。

void minHeapify(PriorityQueue* pq, int index) {
    // ヒープの整合性を保つための処理
}
void decreaseKey(PriorityQueue* pq, int vertex, int newDistance) {
    // キーの値を減少させる処理
}

このように、ヒープを用いることで、優先度付きキューの操作が効率的に行えます。