Dijkstra法によるグラフ最短路問題
内容
- スライド 1 Dijkstra法によるグラフ最短路問題
- スライド 2 グラフとは
- スライド 3 グラフには、それぞれの枝に向きのある有向グラフ(directed graph)、...
- スライド 4 最短経路問題
- スライド 5 最短経路問題のクラス
- スライド 6 Dijkstra法
- スライド 7 Dijkstra法による最短経路検索
- スライド 8 まず、このグラフについてのデータを与える
(始点・・・Ns=13,終点・・・N...
- スライド 9 以下の3つのリストを用意する
・リストA (未調査リスト)
・リスト...
- スライド 10 2.始点Nsに関するノードデータを未調査リストから調査済リストへ移動、その際ノー...
- スライド 11 3.区間データを元に、始点Nsから直接到達可能なノードを調べ、そのノードに関する...
- スライド 12 4.以下の項目をリストBが空になるまで繰り返す。
(a)リストBから...
- スライド 13 (c)NiがBにあれば、NsからNmの最短距離に区間 距離Nm,Niを加...
- スライド 14 5.リストBが空に成った時点でA,B,Cについて以下のような リストが得られる...
- スライド 15 ここでリストCに、始点Nsから各ノードへの最短距離が入っていることになり、ノード...
Converted from Powerpoint Presentation to HTML by PPT2HTML AddIn.
PPT2HTML : by AGATASHI