読者です 読者をやめる 読者になる 読者になる

FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

もっとアルゴリズみ!

上のページの解説を参考に、擬似コードC言語に翻訳してみた。こういうアルゴリズムの理解がすらすらとできるくらいには、オレは少しは成長したのかなあ。

#include <stdio.h>

typedef struct {
	int edges_to[10];
	int edges_cost[10];
	int n_edges, done, cost, from;
} node;

// ダイクストラ法
void get_path(node *nodes, int size, int dep)
{
	int i, to, cost, from;
	node *done_node;
	
	// ノードを初期化
	for (i = 0; i < size; i++) {
		nodes[i].done = 0;
		nodes[i].cost = -1;
	}
	
	// 始点のコストはゼロ
	nodes[dep].cost = 0;
	
	while (1) {
		// 確定するノードを設定
		done_node = NULL;
		for (i = 0; i < size; i++) {
			if (nodes[i].done || nodes[i].cost < 0) {
				continue;
			} else if (done_node == NULL || nodes[i].cost < done_node->cost) {
				done_node = &nodes[i];
				from = i;
			}
		}
		// 確定するノードがなくなったら終了
		if (done_node == NULL) break;
		
		// ノードを確定
		done_node->done = 1;
		
		// 接続先の情報を更新
		for (i = 0; i < done_node->n_edges; i++) {
			to = done_node->edges_to[i];
			cost = done_node->cost + done_node->edges_cost[i];
			if (nodes[to].cost < 0 || cost < nodes[to].cost) {
				nodes[to].cost = cost;
				nodes[to].from = from;
			}
		}
	}
}

int main(void)
{
	int i, j, size, dep, dest;
	int path[100];
	node nodes[100];
	
	printf("グラフの最短経路を求める☆\n");
	
	// ノード数の入力
	scanf("%d", &size);
	for (i = 0; i < size; i++) {
		// 接続するノード数の入力
		scanf("%d", &nodes[i].n_edges);
		for (j = 0; j < nodes[i].n_edges; j++) {
			// 接続先の番号とコストの入力
			scanf("%d", &nodes[i].edges_to[j]);
			scanf("%d", &nodes[i].edges_cost[j]);
		}
	}
	// 始点と終点の入力
	scanf("%d%d", &dep, &dest);
	
	// ダイクストラ法を実行
	get_path(nodes, size, dep);
	
	// コストを出力
	printf("%d\n", nodes[dest].cost);
	
	// 終点までの道程を配列に保存
	for (i = 0; dest != dep; i++) {
		path[i] = dest = nodes[dest].from;
	}
	// 道程を始点から順に出力
	for (j = i - 1; j >=  0; j--) {
		printf("%d ", path[j]);
	}
	printf("\n");
	
	return 0;
}

全体のノード数、それぞれのノードに接続されたエッジの情報、始点と終点を入力すると、ダイクストラ法で求めた始点-終点間の最短経路とコストを表示する。入力しだいで有向グラフ・無向グラフの両方に対応できそう。今までダイクストラ法って名前だけで敬遠してたけど、じっくり読みほどいてみれば案外シンプルなアルゴリズムなのねー。

ブラックボックス的に使うのは気持ち悪いけど、その中身を理解して使うのならば、アルゴリズムはとっても便利なツール。先人の辿った道筋をなぞるだけで、プログラミングの夢が広がりんぐ。もちろん、基礎となるプログラミング言語をよりよく理解するのも重要だけど、レベルを上げる近道はアルゴリズムを知ることにあるのかも。