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