Dijkstra's Algorithm
ダイクストラのアルゴリズム, ダイクストラ法
最短経路問題において使用.あるノードから他のノードへの最短経路を求める.重み付きグラフにおいて、負の重みがあった場合は挙動がおかしくなるので、その時はFloyd-Warshall?を使う.
Program
int graph[MAX][MAX];
int len[MAX], v[MAX];
int start; // 始点
int min, p;
void dijkstra() {
for(int i = 0 ; i < MAX ; i++) {
len[i] = INT_MAX;
v[i] = 0;
}
len[start] = 0;
for(int i = 0 ; i < MAX ; i++) {
min = INT_MAX;
for(int j = 0; i < MAX ; j++) {
if(v[j] == 0 && len[j] < min) {
p = j;
min = len[j];
}
}
v[p] = 1;
for(int j = 0 ; j < MAX ; j++) {
if((len[p] + graph[p][j]) < len[j]) {
len[j] = len[p] + graph[p][j];
}
}
}
for(int i = 0 ; i < MAX ; i++) {
cout << start << " -> " << i << " : " << len[i] << endl;
}
}