ダイクストラ法を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; }
ダイクストラ法の実装は適当。ここではいいかげんな二次元配列で実装してますけど、本当は二分ヒープで実装したプライオリティーキューとかでやると良いらしいですよ。
以下全コード。データの変換にわりと行数つかってる。
#include <stdio.h> #include <limits.h> #define MAX_LINKED 4 #define MAX_ROUTE 100 #define N 5 #define MAX_COL 10 #define MAX_ROW 10 #define EDGECOST 1 struct node{ char key; // 元々の文字 int col, row; // 座標 int linkable; // このノードがリンク可能か否か int linked_count; // このノードからリンクしている数 struct node *link[4]; // リンク int cost; // スタート地点からのコスト int path_count; // スタート地点からの経路点数 struct node *path[MAX_ROUTE]; // スタート地点からの最短経路 }; typedef struct{ int cols, rows; struct node nodes[MAX_COL][MAX_ROW]; struct node *start, *goal; } Route; int node_link(struct node *from, struct node *to){ if(from->linkable && to->linkable){ from->link[from->linked_count] = to; ++from->linked_count; } } int route_link(Route *route){ int i, j; for(i=0;i<route->cols;++i){ for(j=0;j<route->rows;++j){ if(!route->nodes[i][j].linkable) continue; if(0 <= i-1){ node_link(&(route->nodes[i][j]), &(route->nodes[i-1][j])); } if(i+1 <= route->cols){ node_link(&(route->nodes[i][j]), &(route->nodes[i+1][j])); } if(0 <= j-1){ node_link(&(route->nodes[i][j]), &(route->nodes[i][j-1])); } if(j+1 <= route->rows){ node_link(&(route->nodes[i][j]), &(route->nodes[i][j+1])); } } } return 0; } int route_init(Route *route, char *route_dat[]){ int i, j; route->cols = route->rows = N; for(i=0;i<route->cols;++i){ for(j=0;j<route->rows;++j){ route->nodes[i][j].key = route_dat[i][j]; route->nodes[i][j].col = i; route->nodes[i][j].row = j; route->nodes[i][j].cost = INT_MAX; switch(route->nodes[i][j].key){ case 'g': route->nodes[i][j].linkable = 1; route->nodes[i][j].linked_count = 0; route->goal = &(route->nodes[i][j]); break; case 's': route->nodes[i][j].linkable = 1; route->nodes[i][j].linked_count = 0; route->start = &(route->nodes[i][j]); break; case '0': route->nodes[i][j].linkable = 1; route->nodes[i][j].linked_count = 0; break; case '1': route->nodes[i][j].linkable = 0; route->nodes[i][j].linked_count = 0; break; default: return -1; break; } } } route->start->cost = 0; route->start->path_count = 0; return route_link(route); } int dijkstra(struct node *start, struct node *goal){ int i, result = 0; struct node *curnode = start; if(start == goal) return 1; for(i=0;i<curnode->linked_count;++i){ struct node *linknode = curnode->link[i]; if(curnode->cost+EDGECOST < linknode->cost){ int j; linknode->cost = curnode->cost + EDGECOST; linknode->path_count = curnode->path_count+1; for(j=0;j<curnode->path_count;++j){ linknode->path[j] = curnode->path[j]; } linknode->path[j] = curnode; result += dijkstra(linknode, goal); } } return result; } int main(){ int i, j; Route route; char *route_dat[] = { "s0001", "10100", "00000", "01011", "0000g" }; // 元経路データの route_dat から経路データ route を構築 route_init(&route, route_dat); if(dijkstra(route.start, route.goal) == 0){ fputs("coudn't find shortest path\n", stderr); exit(1); } for(i=0;i<route.goal->path_count;++i){ struct node *n = route.goal->path[i]; printf("(%d,%d)\n", n->col, n->row); } printf("(%d,%d)\n", route.goal->col, route.goal->row); return 0; }
まあけっこうあやしいと思う。
