ダイクストラの処理過程表を書けという問題があるのですが
参考書にも表が書かれたものがないので書き方が分かりません。
ダイクストラ法自体は分かるのですが・・・・
例えば以下のようなネットワークの場合
(数値は点までの距離です)
b
4/ \2
a d---------e
1\ /2 3
c
ダイクストラ法を使って点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ベストアンサー
- 回答日時:
最後の「U」の欄は, 何を意味しているんでしょうかねぇ. 普通の Dijkstra法だと, 最初は { b, c, d, e } にするような気がする (その方が 1ステップ分だけ処理が短かくてすむから) けど....
その欄を除けば簡単で, 各ステップごとの「その点までの (わかっている範囲内での) 最短距離」と「その最短距離が得られるような経路での, その点の直前に来る点の名前」を書けばいいんでしょう, きっと.
ありがとうございます。
>「その点までの (わかっている範囲内での) 最短距離」と
>「その最短距離が得られるような経路での, その点の直前に来る点の名前」
えと・・
つまり
___a____b_____c_____d_____e
a
b
c
d
e
と表があり
質問のネットワークを考えると
各ステップは
(1)aから隣接点b、cまでの距離を求める。bは(4.a)と仮定 cは(1.c)で決定
(2)cを通ったdまでの最短距離(3,c)決定
(3)dを通ったb,eまでの距離(5,d)(6,d)を仮定
(4)(1)で仮定したbまでの距離と(3)で仮定したbまでの距離を比べ
bまでの最短距離は(4.a)に決定
(5)eまでの最短距離を(6,d)に決定
____a____b_____c____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
- 回答日時:
Dijkstra 法の処理はそれで OK. でも, 「操作点」の意味が全くわからないですね....
必ずしも「与えられた順番」に従って処理するわけじゃないから....
普通, このような表を書くなら縦方向は時系列 (アルゴリズムの各ステップ) で, その場合にはいいんですけどねぇ. 「操作点」って何だ?
度々ありがとうございます。
何なんでしょうねぇ・・操作点って・・・・
問題に表の説明か例でも示してくれてれば分かったんですが・・・
質問はこれにて〆切にさせて頂きます。
ありがとうございましたm(__)m
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(コンピューター・テクノロジー) ダイクストラ法の証明を教えてください。特に、最短路確定済みの点に隣接する点で、暫定の距離が最短のもの 2 2022/08/09 00:56
- 高校 数Ⅱの軌跡という単元について質問です。 問題の最後に、逆に、この~上の全ての点は条件を満たすとかく場 3 2023/03/21 16:38
- 数学 ベクトル方程式(ヘッセの標準形)についての質問 2 2022/04/23 18:00
- 高校受験 高校受験まで2週間/未だに理社が平均点以下 理社の点数が未だに平均点以下から上がらず困っています… 1 2023/01/29 18:24
- 数学 数学 軌跡の問題で2点から等しい距離にある点の軌跡を求めるので三平方の定理を使うのですが、求める点の 4 2023/02/10 21:26
- その他(プログラミング・Web制作) python コードについて(初学者です) 3 2023/07/20 14:44
- 数学 私大入試の証明問題について質問です。 範囲を求めよという証明問題なのですが、場合分けするのに必要な式 3 2023/02/10 16:45
- その他(データベース) Accessフォームにて指定のフィールドの平均値を小数点第一位で表示できない 2 2022/08/30 17:19
- 物理学 写真の問題についての、 写真の赤枠で囲ってある部分の「衝突の時間間隔は公比eの等比数列をなす」と書い 2 2022/08/01 23:23
- 高校 三次関数のグラフにつきまして 3 2022/05/15 11:14
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
医薬品製造のPV PQの意味について
-
GQPとGMPは何が違うのですか?...
-
2液性エポキシ接着剤の保管期間...
-
SIP洗浄とCIP洗浄の違いは?
-
吸血鬼が嫌うもの
-
アセトンの有害について
-
統計の質問です。フィッシャー...
-
谷の定義を教えて下さい
-
venomとpoisonとtoxinの違いっ...
-
鉛の毒性について
-
活性炭の粒度
-
【海外/輸入/医薬品/表記/賦形...
-
「査収」
-
"REC DATE"ってどういう意味?
-
分析法バリデーションや分析方...
-
ほう砂の使い道について
-
マックスウェルの相反定理
-
フロリナートの構造式を教えて...
-
エアダスターの成分"HFC-152a"...
-
「1時間不足する」と「1時間下...
おすすめ情報