MLB - その５。

前回が、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);