OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

最短路問題について

  • すぐに回答を!
  • 質問No.119271
  • 閲覧数270
  • ありがとう数1
  • 気になる数1
  • 回答数1
  • コメント数0

お礼率 100% (1/1)

はじめまして。
「データ構造とアルゴリズム」を独学で勉強中の学生です。
当方、周りより指導していただける環境が無く
どうにも行き詰まってしまったのでここに書き込みをさせていただきました。
お聞きしたい問題なのですが
「最短路問題について問題の定義と解法(アルゴリズム)を説明せよ。次に図1においてpから全ての頂点への最短路を求めよ。」
というものです。
* 図1はhttp://www.geocities.co.jp/Hollywood-Stage/3151/g/g.gifにupしてあります。
最短路問題を解く方法としてダイクストラのアルゴリズムやFloydのアルゴリズムがありますが、これらは書籍などを参考にして理解しているつもりです。
しかし実際、問題を解く手順といいますか、解答を書くことができないのでどなたかおわかりになる方がいらっしゃいましたらご指導をいただきたいと思い書き込みをさせていただきました。
学習不足で怠慢な学生の質問で大変申し訳ありませんが
ご指導のほどよろしくお願いいたします。
通報する
  • 回答数1
  • 気になる1
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.1
レベル9

ベストアンサー率 71% (59/82)

「アルゴリズムを説明せよ」って
言われたら、私なら、参考書に良く
出ている、「ステップ1 …を…する」
とかいう、あれを書きます。

ダイクストラのアルゴリズムの場合、
例えば、こんな風に書けるんじゃない
でしょうか?

[定義]
・ノードiからノードjの仮の最短距離を
 d_ijとし、その初期値は全て∞とする
・ノードiと直接つながっているノード(隣接ノード)
 番号の集合を
  N_i = {n_i1, n_i2, … }
 とする
・ノードiと、その隣接ノードjの間の距離をl_ijとする
・他のノードへの最短距離を求めるべき初期ノード
 (出発点)の番号をpとする
・最短経路を構成するアーク(ノードiとノードjを
 結ぶアークを(i,j)と表す)を要素とする集合をRとし、
 その初期値は空集合とする
・全てのノードの番号を要素に持つ集合をMとする

[アルゴリズム]
ステップ1.
 初期化:
 ・初期ノードpの仮の最短距離を0にする
   d_pp := 0
 ・変数aを初期ノードの番号pで初期化
   a := p
 ・集合Mからpを取り除く

 ステップ4へ

ステップ2.
 集合Mの要素であるノードのうち、初期ノードpからの
 仮の最短距離が最小のノードを求め、
 その番号をaに代入する
  a = argmin_(i∈M) d_pi

ステップ3.
 Mに含まれないaの全ての隣接ノードについて、
 各ノードの仮の最短距離とノードaまでの距離の和が
 最小のアークを選び、最短経路として登録する
  b = argmin_(i not∈M) (d_pb + l_ab)
  R := {{R}, (b, a)}

ステップ4.
 Mに含まれるaの全ての隣接ノードについて、
 各ノードの仮の最短距離が、ノードaまでの仮の
 最短距離とノード間距離の和より大きい場合、
 その値を更新する
  for all i (∈ N_a)
   if d_pi > d_pa + l_ai
    d_pi := d_pa + l_ai

ステップ5.
 Mが空集合であれば終了。Rの要素が最短経路を
 構成する全てのアークである。また、pから
 ノードiへの最短距離はd_piである。
 Mが空集合でなければステップ2へ。
  if M = φ
   end
  otherwise
   go to step 2

このように、自分で必要な変数を定義し、それを
使って曖昧性が少なくなるよう、集合論の記号や
数式を駆使して、各ステップのオペレーションを
表現します。

補足ですが、グラフ理論を勉強されている方には
失礼かと思いますが、上で「ノード」とは各頂点
(葉)を表し、「アーク」とは隣接する地点間を
結ぶ線分(枝)を表す抽象的な用語です。
お礼コメント
jonathan_davis

お礼率 100% (1/1)

お礼が遅くなってしまって申し訳ありませんでした。
ご回答ありがとうございました。
参考にさせていただきます。
投稿日時 - 2001-08-31 02:02:34
-PR-
-PR-
このQ&Aのテーマ
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ