ベルマンフォード法

 投稿者：永野護  投稿日：2021年11月24日(水)10時40分51秒
  REM   ベルマンフォード法で最短経路を求めています。最短距離は何とか出てるみたいですが、途中経路の
REM   示し方がわかりません。ご多忙の折誠に恐縮ですが、よろしければ経路の示し方をご教授願えないでしょうか。
REM   コードは下記の通りです。7つの頂点を含むグラフです。

DIM  dist(7)

DIM  c(7,7)
FOR  y=1  TO  7
   FOR  z=1  TO  7
      LET c(y,z)=1000
   NEXT Z
NEXT Y

LET dist(1)=0
LET dist(2)=1000
LET dist(3)=1000
LET dist(4)=1000
LET dist(5)=1000
LET dist(6)=1000
LET dist(7)=1000
LET c(1,1)=0
LET c(2,2)=0
LET c(3,3)=0
LET c(4,4)=0
LET c(5,5)=0
LET c(6,6)=0
LET c(7,7)=0
LET c(1,2)=20
LET c(2,1)=20
LET c(1,3)=50
LET c(3,1)=50
LET c(2,3)=1
LET c(3,2)=1
LET c(2,4)=6
LET c(4,2)=6
LET c(3,4)=100
LET c(4,3)=100
LET c(3,5)=50
LET c(5,3)=50
LET c(4,5)=8
LET c(5,4)=8
LET c(4,7)=20
LET c(7,4)=20
LET c(5,7)=30
LET c(7,5)=30
LET c(5,6)=40
LET c(6,5)=40
LET c(6,7)=80
LET c(7,6)=80
REM-----------------------------------------------------------------
FOR  t=1  TO 6
   FOR i=1  TO  7
    IF     dist(i)>dist(t)+c(t,i)  THEN  LET dist(i)=dist(t)+c(t,i)
  NEXT  i
NEXT  t

REM   ------------------------------


FOR   x=1  TO  7
   PRINT  "最短距離="; dist(x);
NEXT x

END










 		 

Re: ベルマンフォード法

 投稿者：nagram  投稿日：2021年11月25日(木)10時18分33秒
  > No.4981[元記事へ]

永野護さんへのお返事です。

各頂点をA～Gとし、有向グラフの重みを次のようにし、Aを始点として各頂点への最短経路を求める問題ですね。

A→B=20, A→C=50
B→C=1, B→D=6
C→D=100, C→E=50
D→E=8, D→G=20
E→F=40, E→G=30
F→G=80


DIM  dist(7), node$(7),path$(7)
MAT READ node$
DATA  A,B,C,D,E,F,G
MAT path$=node$(1)&NUL$

DIM  c(7,7)
MAT c=1000*CON

LET dist(1)=0
LET dist(2)=1000
LET dist(3)=1000
LET dist(4)=1000
LET dist(5)=1000
LET dist(6)=1000
LET dist(7)=1000
LET c(1,1)=0
LET c(2,2)=0
LET c(3,3)=0
LET c(4,4)=0
LET c(5,5)=0
LET c(6,6)=0
LET c(7,7)=0
LET c(1,2)=20
LET c(2,1)=20
LET c(1,3)=50
LET c(3,1)=50
LET c(2,3)=1
LET c(3,2)=1
LET c(2,4)=6
LET c(4,2)=6
LET c(3,4)=100
LET c(4,3)=100
LET c(3,5)=50
LET c(5,3)=50
LET c(4,5)=8
LET c(5,4)=8
LET c(4,7)=20
LET c(7,4)=20
LET c(5,7)=30
LET c(7,5)=30
LET c(5,6)=40
LET c(6,5)=40
LET c(6,7)=80
LET c(7,6)=80
REM-----------------------------------------------------------------
FOR  t=1  TO 6
   FOR i=1  TO  7
      IF     dist(i)>dist(t)+c(t,i)  THEN
         LET dist(i)=dist(t)+c(t,i)
         LET path$(i)=path$(t)&node$(MAX(t,i))
      END IF
   NEXT  i
NEXT  t
REM   ------------------------------

FOR   x=1  TO  7
   PRINT  "最短距離="; dist(x); ", 経路=";path$(x)
NEXT x

END
 

ベルマンフォード法

 投稿者：永野護  投稿日：2021年11月27日(土)18時31分44秒
  ベルマンフォード法は無向グラフにも適用できるのでしょうか。先ごろ作っていただきました
プログラムで対応可能でしょうか。度々質問してすみませんがご迷惑でなかったらご教授
お願いしたいのですが。何卒よろしくお願いします。本当に身勝手なお願いで申し訳ないです。
 		 

Re: ベルマンフォード法

 投稿者：nagram  投稿日：2021年11月29日(月)11時09分35秒
  永野護さんへのお返事です。

> ベルマンフォード法は無向グラフにも適用できるのでしょうか。先ごろ作っていただきました
> プログラムで対応可能でしょうか。度々質問してすみませんがご迷惑でなかったらご教授
> お願いしたいのですが。何卒よろしくお願いします。本当に身勝手なお願いで申し訳ないです。
>

私もグラフ理論に詳しいわけではないですが、ベルマンフォード法は有向グラフにしか使えないようですね。
無向グラフの解法も調べましたが、いい方法は見つけられませんでした。

永野護さんが提示したプログラムも有向グラフにしか適用できず、「辺の方向は頂点の順序により決定する」という条件が付きます。
c(p,q) を p<q のときのみ調査しています。(A→B,D→G は調査するが、E→C はスルー)
提示されたグラフのデータがその条件を満たしていたので解けましたが、c(5,2)=6 といったデータがあると上手く求めることができません。

ネットでベルマンフォード法のサンプルプログラムを見ましたが、[FOR i=1 TO 7] の部分を foreach文を利用しているものが多いですね。
foreach文は十進BASICにはない構文なので代替する方法を考えましたが、私の実力不足でうまくできませんでした。
下記のプログラムは、永野護さんが提示したプログラムを探査する向きを変えて２回実行しています。当然、計算量も２倍になります。
(データの一部を変えて、頂点の順序とは逆方向の辺を作っています。)
この方法が、(非負の重みの)すべての有向グラフに対して有効かは分かりません。


各頂点をA～Gとし、有向グラフの重みを次のようにし、Aを始点として各頂点への最短経路を求める。

A→B=20, A→C=50
B→C=150, B→D=6
C→E=4
D→C=3, D→E=8, D→G=20
E→F=40, E→G=30
F→G=80

LET n=7
DIM  dist(n), node$(n),path$(n)
MAT READ node$
DATA  A,B,C,D,E,F,G
MAT path$=node$(1)&NUL$

DIM  c(n,n)
MAT c=1000*CON

MAT dist=1000*CON
LET dist(1)=0

LET c(1,2)=20
LET c(1,3)=50
LET c(2,3)=150  ! c(2,3)=1
LET c(2,4)=6
LET c(4,3)=3  ! c(3,4)=100
LET c(3,5)=4  ! c(3,5)=50
LET c(4,5)=8
LET c(4,7)=20
LET c(5,7)=30
LET c(5,6)=40
LET c(6,7)=80
REM-----------------------------------------------------------------
FOR  t=1  TO n-1
   FOR i=1  TO  n
      IF     dist(i)>dist(t)+c(t,i)  THEN
         LET dist(i)=dist(t)+c(t,i)
         LET path$(i)=path$(t)&node$(i)
      END IF
   NEXT  i
NEXT  t
FOR  t=1  TO n-1
   FOR i=n  TO  1 STEP -1
      IF     dist(i)>dist(t)+c(t,i)  THEN
         LET dist(i)=dist(t)+c(t,i)
         LET path$(i)=path$(t)&node$(i)
      END IF
   NEXT  i
NEXT  t

REM   ------------------------------

FOR   x=1  TO  n
   PRINT  "最短距離="; dist(x); ", 経路=";path$(x)
NEXT x

END
 

ベルマンフォード法

 投稿者：永野護  投稿日：2021年11月29日(月)12時31分35秒
  nagram様、お忙しいところ貴重なプログラムを作っていただきましたことに心より感謝
します。ご多忙中にもかかわらず丁寧なご指導をいただき、ありがとうございました。
貴重な体験を糧とし、日々精進してまいりたいと存じます。
末筆ではございますが、nagram様の一層のご活躍を心よりお祈り申し上げます。
敬具 		 

ベルマンフォード法

 投稿者：永野護  投稿日：2021年11月30日(火)12時24分19秒
  nagram様よりご提示いただきましたプログラムをヒントにdo  while   loopを加えてみました。
隣接行列の値も変えています。これでちゃんとできているみたいですが。

DIM  dist(7), node$(7),path$(7)
MAT READ node$
DATA  A,B,C,D,E,F,G
MAT path$=node$(1)&NUL$

DIM  c(7,7)
MAT c=1000*CON
LET inf=1000
LET dist(1)=0
LET dist(2)=inf
LET dist(3)=inf
LET dist(4)=inf
LET dist(5)=inf
LET dist(6)=inf
LET dist(7)=inf
LET c(1,1)=0
LET c(2,2)=0
LET c(3,3)=0
LET c(4,4)=0
LET c(5,5)=0
LET c(6,6)=0
LET c(7,7)=0
LET c(1,2)=30
LET c(2,1)=30
LET c(1,3)=20
LET c(3,1)=20
LET c(1,7)=1
LET c(7,1)=1
LET c(2,3)=2
LET c(3,2)=2
LET c(2,4)=6
LET c(4,2)=6
LET c(2,5)=1
LET c(5,2)=1
LET c(2,7)=6
LET c(7,2)=6
LET c(3,4)=2
LET c(4,3)=2
LET c(3,5)=3
LET c(5,3)=3
LET c(3,6)=1
LET c(6,3)=1
LET c(4,5)=20
LET c(5,4)=20
LET c(4,6)=30
LET c(6,4)=30
LET c(4,7)=100
LET c(7,4)=100
LET c(5,7)=2
LET c(7,5)=2
LET c(5,6)=5
LET c(6,5)=5
LET c(6,7)=10
LET c(7,6)=10

REM-----------------------------------------------------------------
LET w=0
DO  WHILE  w<=7
   FOR  t=1  TO 7
      FOR i=1  TO 7

         IF  dist(i)>dist(t)+c(t,i)  THEN
            LET dist(i)=dist(t)+c(t,i)
            LET path$(i)=path$(t)&node$(i)


         END IF

      NEXT  i

   NEXT  t
   LET w=w+1
LOOP
REM-----------------------------------
PRINT  "-------------------------------------------------------"

FOR   x=1  TO 7
   PRINT  "最短距離="; dist(x); ", 経路=";path$(x)
NEXT x

END





 		 

戻る