ダイクストラ法をC言語で。
なんか最近微妙にまわりでダイクストラ法がブームらしいので、C言語で書いてみる。つっても、汎用的な書き方ってのをどうやるかは知らないんだけど。大学の同級生とか後輩とかがプログラムで迷路を解く課題に苦しめられたらしいので、俺的理解のダイクストラ法で迷路を解いてみる。
コードが長くなっちゃうんで、問題となる迷路はコードに埋め込みでこんな5×5のcharで与える。sがスタート地点、gがゴール地点、0が通路で1が壁を意味する。斜め移動は無し、地点間のコストは全て1。
（文字列末尾の '\0' 入れると長さ6の char だけど気にしない）
char *route_dat[] = { "s0001", "10100", "00000", "01011", "0000g" };
ほんでまあ、この元となる経路データ route_dat から、最短経路を求めるのに適した経路データ構造に変換してからダイクストラ法で解いた。
実行結果はこんな。
% ./dijkstra (0,0) (0,1) (1,1) (2,1) (2,2) (3,2) (4,2) (4,3) (4,4)
うんまあとりあえずこの問題では合ってるらしいよ。
肝心のデータ構造とダイクストラ法を用いた関数はこんな。
struct node{ char key; // 元々の文字 int col, row; // 座標 struct node *link[4]; // リンク int linked_count; // このノードからリンクしている数 int is_shortest; // 既に最短経路か否か int cost; // スタート地点からのコスト struct node *parent; // このノードの親ノード }; typedef struct{ int cols, rows; struct node nodes[MAX_COL][MAX_ROW]; struct node *start, *goal; } Route; int relax(Route *route, struct node *curnode){ int i; for(i=0;i<curnode->linked_count;++i){ struct node *linked = curnode->link[i]; int newcost = curnode->cost + EDGECOST; if(linked->cost > newcost){ linked->cost = newcost; linked->parent = curnode; } } return 1; } struct node *nextnode(Route *route){ struct node *minnode = NULL; int i, j; for(i=0;i<route->cols;++i){ for(j=0;j<route->rows;++j){ struct node *n = &route->nodes[i][j]; if(!n->is_shortest && (minnode==NULL || minnode->cost > n->cost)){ minnode = n; } } } minnode->is_shortest = 1; return minnode; } int dijkstra(Route *route, struct node *start, struct node *goal){ struct node *curnode = start; while(curnode != goal){ relax(route, curnode); // 最短経路がわかった点からパスがある点の更新 curnode = nextnode(route); // コストが一番小さい点を次の点に if(curnode == NULL){ return 0; } } return 1; }
ダイクストラ法の実装は適当。ここではいいかげんな二次元配列で実装してますけど、本当は二分ヒープで実装したプライオリティーキューとかでやると良いらしいですよ。
以下全コード。データの変換にわりと行数つかってる。
続きを読むマウス脳とキーボード脳
なんかこう、マウスでかちかちぐいーんかち、とやってるときと、キーボードでぺちぺちぺちとやってる時では、脳味噌のモードが違う気がする。
