Algorithm Database無向グラフ スケジューリング 量子計算（グローバーのアルゴリズム） 最小カット 投票力指数 (CGI) チャネル割当問題 共有区間列挙問題(CGI) ２次元ボロノイ図構成 グラフエディタの作成（群馬大学 中野研究室） 辺連結度増大アルゴリズム ３次元凸包 グラフ分割問題 最大クリーク問題 巡回セールスマン問題 最短路問題 ハイパーグラフの極小横断 new!!誤差拡散法 （ブラウザの設定で "Javaを有効" にして下さい。）
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://mikilab.doshisha.ac.jp/dia/research/report/2004/0716/002/report20040716002.html
