質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.81%

  • アルゴリズム

    358questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

プリムのアルゴリズムとダイクストラ法の違いについて

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 191

maskey

score 1

 前提・実現したいこと

プリムのアルゴリズムとダイクストラ法の違いが分からずに困っています。

プリム法は最小全域木、ダイクストラ法は2点間の最短経路を求めるアルゴリズムだという事は理解しているのですが、結局最小全域木で2点間を辿れば最短経路になる様に思えるので、ダイクストラ法の必要性がよく分からずにいます。

どなたか詳しくご説明していただけませんでしょうか。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+3

最大の違いは、ダイクストラ法には「スタート地点・ゴール地点」という概念があることです。プリム法では最小スパニング木ができますが、ダイクストラ法でできるのは、スタート地点を根とした最短経路スパニング木です。
そのため、外部の点を木に入れるときの計算方法が異なります。プリム法では、新しい辺を加えるときに、木の内部と外部を結ぶ辺の重みしか考慮しません。これに対してダイクストラ法では、木の内部と外部を結ぶ辺の重みに加え、その辺のうち木の内部にある方の頂点とスタート地点との距離も考慮します。

わかりやすい例として、正三角形ABCとその重心Dを考えてみてください。AからDの4点をつなぐ最小スパニング木はD-A, D-B, D-Cの3本の直線で構成されるものになりますが、AからBへの最短経路は明らかにA-Bです。
点Aを根とした最短経路スパニング木は、A-B, A-C, A-Dの3本の直線で構成されるものになります。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/16 20:41

    ご丁寧な解説をありがとうございます!
    なるほど、最小全域木上の経路が必ずしも2点間の最短経路とはならないのですね。正三角形の具体例のおかげで、スムーズに理解出来ました。
    ご回答頂きありがとうございました。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.81%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    PHPやJAVAを使ってアルゴリズムを学びたい

    PHPやJAVAを使ってアルゴリズムに関するスキルを身につけようと思っています。 PHPやJAVAでアルゴリズムが学べるオススメ参考書やURLなにかありましたら教えてください。

  • 解決済

    漸化式について

    漸化式の問題について質問です. P_(n+1) = ((n+2)/(n+1))*P_(n) + (2n)/(n+1) という漸化式なのですが特性方程式を使って解くのかと考え,何

  • 受付中

    アルゴリズムの入門書

    アルゴリズム入門の勉強におすすめの書籍、サイトなど教えてもらえないでしょうか? CheckiOというpython学習サイトを進めているのですが、難しくてなかなか進まないのでアルゴ

  • 解決済

    PHPを通してアルゴリズムを勉強したいのですが

    現在PHPを勉強中なのですが、アルゴリズムなるものに興味が出てきました。 そこで、PHPでアルゴリズムを学ぶ際におすすめの書籍を教えて下さい(´・ω・`) ちなみに勉強を始

  • 解決済

    c言語についての質問です

    あるテキストを辞書順にソートし、別のテキストに出力するプログラムを作成したいです。 include<stdio.h> include<stdlib.h> include<

  • 解決済

    疑似コードの記号について

    疑似コードで記されている、両端に矢印が付いた記号や、両端が四角の記号。 それと、処理の合間に入っている棒。 これらの作用を教えてください。

  • 受付中

    二分木探索のsearchの中身

    目的 二分木探索の実装 問題点 下記コードのBTNode searchの部分がどう書けばいいのか分かりません。 調べてみましたが、明確な解決策が見つかりませんでした。 ソー

  • 解決済

    入力された長文から登録されている単語をあいまい検索する方法は?

    単語から長文を検索するのは一般的な検索エンジンの動作ですが、 入力された長文から、事前に登録された単語を現実的な早さで「あいまい検索」することは可能でしょうか? また、それを作るた

同じタグがついた質問を見る

  • アルゴリズム

    358questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。