スタートページWeb教材一覧オペレーションズリサーチ

動的計画法による最短経路問題


最短経路問題の説明

図のような道路があります。①から⑥までの最短経路を求めます。

終点から始点まで戻るように考えます。
  地点iから直接に行ける地点jまでの距離を C(i,j) とします。
  地点iから終点までの最短距離を D(i) とします。
  最短にするためには、地点iから地点Kに行けばよいとき、Pnext(i) =Kとします。
 i=6のとき、
   ⑥は終点なので、
     D(6) =0
     Pnext(i) は定義する必要はない。
 i=5のとき、
   ⑤から出ていく道は「⑤→⑥」だけです。そして、⑥は終点ですから、
     D(5) = C(5,6) =5
     Pnext(5) =6
 i=4のとき、
   ④から出ていく道は「④→⑥」と「④→⑤」の2本があります。
     「④→⑥」のとき、A = C(4,6) = 9
     「④→⑤」のとき、B = C(4,5)+D(5) = 6+5=11
   A<Bなので、
     D(4) = 5
     Pnext(5) =6

 このようにして、i=1まで行うと、次の表ができます。
    i  D(i)  Pnext(i)
    6    0   -
    5    5   6
    4    9   6
    3   19   4
    2   13   5
    1   17   2

これから、最短距離は17になります。
 最短経路は、次の手順で求めます。始点①から始めます。
   Pnext(1) =2 ②へ行く。
   Pnext(2) =5 ⑤へ行く。
   Pnext(5) =6 ⑥へ行く。
  ⑥が終点なので、最短経路は
   1→2→5→6

定式化
  地点の個数をNとし、地点番号をi、終点の地点番号を Nlast(=N)とします。
 i=Nlast のとき、
   D(Nlast) =0
 i<Nlast のとき、
    iを一つずつ減らして1になるまで行う。
   D(i) =min{ D(k) + C(i,k)}
      k=i+1,i+2,・・・,N で C(i,k)が存在するもの
   Pnext(i) = minとなるkの値


計算プログラム

地点数=  経路数=
地点番号は1、2、・・・として抜けた番号がないように設定してください。
地点番号は、出発<到着となるように設定してください。
経路番号出発地点到着地点経路距離
経路1
経路2
経路3
経路4
経路5
経路6
経路7
経路8
経路9
経路10