ダイクストラ法の処理過程表なんですが・・・

質問

ダイクストラの処理過程表を書けという問題があるのですが
参考書にも表が書かれたものがないので書き方が分かりません。
ダイクストラ法自体は分かるのですが・・・・
例えば以下のようなネットワークの場合
（数値は点までの距離です）
　 ｂ
4／　＼2
a　　　ｄ---------e
1＼　／2 3
　 ｃ
ダイクストラ法を使って点aから各点までの最短距離を
求まる順に書き出すと
c(1,a)
d(3,c)
b(4,a)
e(6,d)
となりますが、この場合問題の表は

...点...|...a.|...b..|...c..|...d..|...e..|.........U.......|
初期|0/a|∞/ф|∞/ф|∞/ф|∞/ф.|.{a,b,c,d,e}|
操....|.....a..|.....|......|......|......|.......|...................|
作....|.....b..|.....|......|......|......|.......|...................|
点....|.....c..|.....|......|......|......|.......|...................|
........|.....d..|.....|......|......|......|.......|...............|
........|.....e..|.....|......|......|......|.......|...............|

と与えられていました。どのように書き込んでいけば
いいのか分からないのでどなたかアドバイスお願いします。
（表がわかりにくいかもしれませんがお願いします。）

回答No.1

Tacosan · ベストアンサー

最後の「U」の欄は, 何を意味しているんでしょうかねぇ. 普通の Dijkstra法だと, 最初は { b, c, d, e } にするような気がする (その方が 1ステップ分だけ処理が短かくてすむから) けど....
その欄を除けば簡単で, 各ステップごとの「その点までの (わかっている範囲内での) 最短距離」と「その最短距離が得られるような経路での, その点の直前に来る点の名前」を書けばいいんでしょう, きっと.

お礼

ありがとうございます。
>「その点までの (わかっている範囲内での) 最短距離」と
>「その最短距離が得られるような経路での, その点の直前に来る点の名前」

えと・・
つまり
___a____b_____c_____d_____e
a
b
c
d
e
と表があり
質問のネットワークを考えると
各ステップは
(1)aから隣接点ｂ、ｃまでの距離を求める。bは（4.a）と仮定　cは（1.c）で決定

(2)ｃを通ったｄまでの最短距離(3,c)決定

(3)dを通ったb,eまでの距離(5,d)(6,d)を仮定

(4)(1)で仮定したbまでの距離と(3)で仮定したｂまでの距離を比べ
ｂまでの最短距離は(4.a)に決定

(5)eまでの最短距離を(6,d)に決定
____a____b_____ｃ____d_____e___U__
a__0/a__4/a___1/a___???___???_____
b_______0/b_________6/b___________
c_______???___0/c___3/c___???_____
d___________________0/e___6/d_____
e_________________________0/e_____
とすればよろしいのでしょうか？
空欄のところは最短距離が求まっているので空欄
???のところは初期設定の(∞/ф）です

回答No.2

Tacosan

Dijkstra 法の処理はそれで OK. でも, 「操作点」の意味が全くわからないですね....
必ずしも「与えられた順番」に従って処理するわけじゃないから....
普通, このような表を書くなら縦方向は時系列 (アルゴリズムの各ステップ) で, その場合にはいいんですけどねぇ. 「操作点」って何だ?

お礼

度々ありがとうございます。
何なんでしょうねぇ・・操作点って・・・・

問題に表の説明か例でも示してくれてれば分かったんですが・・・

質問はこれにて〆切にさせて頂きます。
ありがとうございましたm(__)m