【C言語】第8章第13回：最短経路アルゴリズムの実装
最短経路アルゴリズムは、グラフ上の2つの頂点間で最小のコストで到達できる経路を見つけるための手法です。本記事では、代表的なアルゴリズムであるダイクストラ法とベルマンフォード法について学びます。
0. 記事の概要
この記事を読むメリット
- 最短経路問題の理解：実用的なグラフアルゴリズムを学び、効率的な問題解決スキルを向上させます。
- アルゴリズム設計の基本理解：ダイクストラ法やベルマンフォード法の動作原理を習得します。
- 実践的なスキルの習得：C言語での最短経路アルゴリズムの実装方法を学べます。
この記事で学べること
- 最短経路アルゴリズムの基本概念
- ダイクストラ法とベルマンフォード法の実装方法
- アルゴリズムの応用例
1. 最短経路アルゴリズムの基本
1.1 最短経路問題とは？
最短経路問題は、グラフの2つの頂点間で最小のコストまたは距離で到達できる経路を見つけることを目的としています。
- 応用例：交通ルートの最適化、ネットワークトラフィック解析
- 種類：単一始点最短経路、全点対最短経路
1.2 ダイクストラ法とベルマンフォード法
- ダイクストラ法：非負重みのグラフで効率的な最短経路探索が可能
- ベルマンフォード法：負の重みを持つグラフにも対応可能
2. ダイクストラ法の実装
2.1 アルゴリズムの概要
ダイクストラ法は、各ステップで未訪問頂点の中から最小の距離を持つ頂点を選び、そこから隣接する頂点への距離を更新することで最短経路を探索します。
2.2 実装例
#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF INT_MAX
// 最小距離を持つ頂点を選ぶ
int selectMinVertex(int* distance, int* visited, int vertices) {
int min = INF, index = -1;
for (int i = 0; i < vertices; i++) {
if (!visited[i] && distance[i] < min) {
min = distance[i];
index = i;
}
}
return index;
}
// ダイクストラ法
void dijkstra(int graph[MAX][MAX], int vertices, int start) {
int distance[MAX], visited[MAX] = {0};
for (int i = 0; i < vertices; i++) {
distance[i] = INF;
}
distance[start] = 0;
for (int i = 0; i < vertices - 1; i++) {
int u = selectMinVertex(distance, visited, vertices);
visited[u] = 1;
for (int v = 0; v < vertices; v++) {
if (graph[u][v] && !visited[v] && distance[u] != INF &&
distance[u] + graph[u][v] < distance[v]) {
distance[v] = distance[u] + graph[u][v];
}
}
}
printf("Vertex\tDistance from Source\n");
for (int i = 0; i < vertices; i++) {
printf("%d\t%d\n", i, distance[i]);
}
}
int main() {
int graph[MAX][MAX] = {{0, 2, 4, 0, 0},
{2, 0, 1, 7, 0},
{4, 1, 0, 0, 3},
{0, 7, 0, 0, 1},
{0, 0, 3, 1, 0}};
int vertices = 5, start = 0;
dijkstra(graph, vertices, start);
return 0;
}
動作解説
- 初期化：距離配列をINFで初期化し、出発点の距離を0に設定します。
- 未訪問頂点の探索：最小距離を持つ未訪問頂点を選択します。
- 距離の更新：選択した頂点に隣接する頂点の距離を更新します。
- 結果の出力：各頂点への最短距離を出力します。
3. ベルマンフォード法の実装
3.1 アルゴリズムの概要
ベルマンフォード法は、グラフ中のすべてのエッジを繰り返し緩和（relax）することで最短経路を探索します。負の重みを持つグラフにも対応可能です。
3.2 実装例
#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF INT_MAX
typedef struct Edge {
int src, dest, weight;
} Edge;
// ベルマンフォード法
void bellmanFord(Edge edges[], int edgeCount, int vertices, int start) {
int distance[MAX];
for (int i = 0; i < vertices; i++) {
distance[i] = INF;
}
distance[start] = 0;
for (int i = 1; i < vertices; i++) {
for (int j = 0; j < edgeCount; j++) {
int u = edges[j].src;
int v = edges[j].dest;
int weight = edges[j].weight;
if (distance[u] != INF && distance[u] + weight < distance[v]) {
distance[v] = distance[u] + weight;
}
}
}
printf("Vertex\tDistance from Source\n");
for (int i = 0; i < vertices; i++) {
printf("%d\t%d\n", i, distance[i]);
}
}
int main() {
Edge edges[] = {{0, 1, 2}, {1, 2, 3}, {2, 3, -1}, {3, 4, 2}, {4, 0, -4}};
int edgeCount = 5, vertices = 5, start = 0;
bellmanFord(edges, edgeCount, vertices, start);
return 0;
}
動作解説
- 初期化：距離配列をINFで初期化し、出発点の距離を0に設定します。
- エッジの緩和：すべてのエッジを反復して緩和します。
- 結果の出力：各頂点への最短距離を出力します。
4. 練習問題
以下の課題に挑戦して、最短経路アルゴリズムの理解を深めましょう。
- ダイクストラ法を使用して単一始点最短経路を求めるプログラムを実装してください。
- ベルマンフォード法を使用して負の重みがあるグラフを解決するプログラムを作成してください。
- フロイドワーシャル法で全点対最短経路を求めるプログラムを実装してください。
5. まとめ
本記事では、ダイクストラ法とベルマンフォード法を用いて最短経路問題を解決する方法を学びました。次回は、さらに高度なグラフアルゴリズムについて学びます。