C言語とダイクストラ法でグラフの最短経路を求める
- 作成日: 2023-04-09
- 更新日: 2023-12-25
- カテゴリ: C言語
C言語とダイクストラ法でグラフの最短経路を求める
ゲームやシステム開発などである経路の最短経路を求めたい。
というケースはけっこうあるかと思われます。
こういう時に必要になるのがデータ構造とアルゴリズムです。
今回はデータ構造の一種であるグラフにダイクストラ法というアルゴリズムを適用し、最短経路を求めてみたいと思います。
C言語によるサンプルコードとサンプルコードの解説を行います。
この記事を見ればダイクストラ法のとっかかりがわかるようになるでしょう。
あなたがわかるようになるように私も頑張って書きたいと思います。
関連記事
C言語でcharをintに変換する方法
C言語でenumをtypedefして使う【列挙型】
C言語でforeachマクロを実装する方法
C言語でnull判定する方法【NULL, 比較】
C言語でできることを解説！C言語歴16年の開発者が語る
C言語でオブジェクト指向する【単一継承の方法】
C言語でグローバルに関数を使う方法
C言語でシャローコピーとディープコピーを実装する
C言語によるコード全文
まずC言語によるグラフの最短経路を求めるコードを全文示します。
いきなり長いコードが出てびっくりするかと思いますが、今後の解説ではこのコードの詳細を解説していくという感じになります。
/* ダイクストラ法を使ってグラフの最短経路を求めるサンプルプログラム。
*
* このプログラムでは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;
}
ソースコードの解説
ではソースコードの解説を行っていきます。
まずこのコードで構築するグラフの構造について画像で説明します。
構築するグラフ構造は？
今回構築しているグラフの構造は上になります。
ピンク色の丸い図形がノード、そこから伸びている黒い棒が辺（エッジ）になります。
ノードの左下に書かれているアルファベットがノードの名前です。
ノードに書き込まれている数字がノードの持つコストで、「?」は無限大を表しています。
辺の近くに書かれている数字は辺の重さです。
このグラフはAからGまで合わせて7つのノードを持つグラフです。
辺は各ノードから無数に伸びており、複雑な経路をしています。
始点のノードは0が書き込まれているAノードがそうです。
ここから終点のGノードまで経路を求めるのが先ほどのコードの内容になります。
あるノードからあるノードまでの経路
グラフで関心ごとになるのがあるノードから別のあるノードまでの経路です。
どのような経路をたどればコストが最短になるのか？ という問題があります。
コストというのはノードから伸びている辺です。
ノードを建物、辺を道路だと思ってください。
そうすると辺の重さは道路を進むのにかかる時間になります。
道路を通れば通るほど、時間はかかります。
ですのでできるだけ時間がかからない道路を進んでいく必要があります。
これを求めるのがダイクストラ法です。
ソースコードの概要の解説
ソースコードの詳細についてはコードのコメントを読んでいただくとして、コードの概要について解説します。
まず今回やる仕事は3つです。
それは
- グラフの構築
- 最短経路の算出
- 最短経路の取得と表示
の3つです。
最初に構造体変数の初期化を行ってグラフのノード群でグラフ構造を構築していきます。
これは単純に辺の重さを指定したり、辺の先に繋がっているノードへのポインタを設定したりといった作業です。
やってみるとわかりますが、この構築はかなり退屈な作業かもしれません。
グラフ構造を構築したら次はダイクストラ法で最短経路を求めます。
これのアルゴリズムの詳細についてもコメントを参照してください。
基本的なアルゴリズムとしては
- 始点ノードを決定しノードのコストを0にする
- 未確定ノードの中から最小のコストを持つノードを見つけてそのノードを確定する
- 最小のコストを持つノードから伸びている辺の先の未確定ノードに、辺の重さと1つ前のノードのコストを合計した値を、その値がノードのコストより小さければ書き込む
- 未確定ノードが無くなるまで2と3を繰り返す
というシンプルなアルゴリズムになります。
辺の先のノードにコストを書き込むんですがこの時に辺の先のノードに1つ前のノードのポインタをメンバ変数prevに持たせます。
こうすることでノード群が片方向リンクリストで繋がり、このリストがそのまま最短経路になります。
つまり終点のノードから始点のノードに向かってprevを辿っていくと、その逆順がそのまま始点から終点までの最短経路になります。
最短経路の取得と表示はこのリストを利用して行います。
ソースコードを理解するための知識
このソースコードを理解するための知識としては
- for文の書き方
- 構造体の使い方
- 構造体の前方参照の書き方
- 配列の使い方
- 構造体のポインタの使い方
などが必要になります。
参考記事としては以下をあげておきます。
おわりに
今回はC言語でダイクストラ法を使ってグラフの最短経路を求めてみました。
ダイクストラ法はシンプルなアルゴリズムですが理解するのはけっこう大変かもしれません。
しかしコードを何度も書いて暗記するようにすると理解が進みます。
なにか参考になれば幸いです。