Dijkstra法によるグラフ最短路問題

内容

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