さくら電算ホームページ
さくら電算製品情報 さくら電算について サポート・お問い合わせ ご注文・価格 ソフトウェアサポートについて 製品カスタマイズ よくある質問と回答(FAQ) ダウンロード
最短経路問題を解くためのアルゴリズム(ダイクストラ法)とは?
ダイクストラ法はグラフ上の2頂点間の最短経路を効率的に求めるアルゴリズムで、1959年エドガー・ダイクストラによって考案されました。当方で公開している最短経路検索システムでもダイクストラ法を基本として最短経路を求める方法を使用しています。

ダイクストラ法と最短経路検索システムの概要

各頂点とそれを結ぶ長さが定義されているとき(最短経路検索システムではマップファイルで定義される)、任意の2頂点間(最短経路検索システムでは検索指示ファイルで定義される)が最短になる経路を求めます。その方法として各頂点にそれまでたどってきた合計の距離を記録して行き、たどってきた経路の距離が記録している距離より短ければ、それをその頂点の距離として記録して検索を続行します。逆にたどってきた経路の距離が記録している距離より長ければ、それ以上の検索は無意味なのでそこで検索を打ち切り、残りの経路の検索を行います。また、一番最初は各頂点の距離論理的に無限大(各自の実装方法による)にしておき、一回目は必ずその距離を記録させる様にします。各頂点から複数の枝分かれがある場合は、その一個を検索を開始したとき、残りはスタックの形で待機させておくと、効率的に最短経路検索が動作します。

最短経路検索システムの紹介ページ

スポンサード リンク
Information
ホーム
公開ソフトについて
ご注文
製品カスタマイズ
CD配達サービス
よくある質問と回答
サポートについて
代表者プロフィール
リンク
お問合せ

スポンサード リンク
Copyright(C) 2007-2018 さくら電算 All Rights Reserved.
特定商取引法表示 個人情報の取り扱い お問合せ サイトマップ