前回が、Dijkstra 法の最も内側のループである「探索点の隣接枝を見ていく」部分についてだったが、今回は Dijkstra 法そのものについてみていく。
プリプロセッサ等が多く、元のソースは読みづらくなってしまっているため、以下のように必要なもののみに絞ってみた。するとずいぶん読みやすくなり、全体が把握しやすい。変数名の付け方など、自分以外の人が書いたソースを読む事はとても勉強になることである。
次回以降は、Insert()、Delete()、RemoveMin() という予定である。
回を重ねるごとに複雑になっていきそうだ。
/* 始点をバケットに格納する */
bckNew = DistToBucket(&(source->dist), DistToLevel(&(source->dist)));
Insert(source, bckNew);
do {
/* バケットから最小ポテンシャル点を取り出す */
currentNode = RemoveMin();
/* 終了条件 */
if (currentNode == NULL) break;
if (currentNode == sink) {
reached = true;
break;
}
sp->cScans++;
currentNode->where = IN_SCANNED;
lastArc = (currentNode+1)->first - 1;
/* 隣接枝をスキャンしていく */
for (arc = currentNode->first; arc <= lastArc; arc++) {
/* 前回ブログ参照 */
}
} while (1);
プリプロセッサ等が多く、元のソースは読みづらくなってしまっているため、以下のように必要なもののみに絞ってみた。するとずいぶん読みやすくなり、全体が把握しやすい。変数名の付け方など、自分以外の人が書いたソースを読む事はとても勉強になることである。
次回以降は、Insert()、Delete()、RemoveMin() という予定である。
回を重ねるごとに複雑になっていきそうだ。
/* 始点をバケットに格納する */
bckNew = DistToBucket(&(source->dist), DistToLevel(&(source->dist)));
Insert(source, bckNew);
do {
/* バケットから最小ポテンシャル点を取り出す */
currentNode = RemoveMin();
/* 終了条件 */
if (currentNode == NULL) break;
if (currentNode == sink) {
reached = true;
break;
}
sp->cScans++;
currentNode->where = IN_SCANNED;
lastArc = (currentNode+1)->first - 1;
/* 隣接枝をスキャンしていく */
for (arc = currentNode->first; arc <= lastArc; arc++) {
/* 前回ブログ参照 */
}
} while (1);