質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

592閲覧

ダイクストラ法の経路の出力の改善

P_036

総合スコア3

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

1クリップ

投稿2023/01/18 12:46

前提

現在、Pythonでダイクストラ法を解くコードを作成しています。(最短経路の重みが何であるのかは既に作成できております。)

どんな経路を通るかを出力できるようにしたいのですが、私が作ったコードではスタートが特定の値のみでしか正常に動作しません。
通る頂点が多いと、何かしらの頂点を飛ばしてしまいます。

正常な経路を表示するには、どう改善したらよいのでしょうか?
良い発想が思い浮かばず一人では限界なので、お力添えをお願いいたします。

なお、今回扱うグラフは頂点数8です。
ノードの重みは下記のソースコードのリストAに記載しております。

該当のソースコード

def main(): A=[] X=[] L=[] for i in range(0,100): X.insert(i,0) L.insert(i,999) A=[[0,1,4,5,0,0,0,0], [1,0,0,3,6,0,0,0], [4,0,0,2,0,0,0,0], [5,3,2,0,2,0,5,0], [0,6,0,2,0,2,1,3], [0,0,0,0,2,0,0,4], [0,0,0,5,1,0,0,6], [0,0,0,0,3,4,6,0]] #ノードの数を取得 N=8 #スタートポイントを任意に指定 u=3 #初期化 X[u]=1 size=1 L[u]=0 #最短ルート登録辞書 root={} #近接しているノードの重みを取得 for i in range(0,N): root[i]=[str(u),str(i)] if(A[u][i]>0): L[i]=A[u][i] root[i]=[str(u),str(i)] #print(root) while(size<N): min=999 #未確定の地点の中から重みが小さい頂点を選び、 #その地点までの最短距離として確定 for i in range(0,N): if (X[i]==0 and L[i]<=min): #Xが0でないかつ候補のノード min=L[i] #最小値更新 v=i #ノード取得 X.insert(v,1) size=size+1 #確定した頂点と繋がっていて、未確定である地点に対して #今確定した場所を経由した場合の距離を計算 for x in range(0,N): if(X[x]!=1 and A[v][x]!=0): if(L[x]>(L[v]+A[v][x])):#今までよりの距離より小さければ更新 L[x]=L[v]+A[v][x] if(len(root[x])==2): root[x]=[str(u),str(v),str(x)] else: root[x]=root[x][:-1].append(v) root[x]=root[x].append(x) #結果表示 for i in range(0,N): print("頂点",i, " : 重さ",L[i], " : ",end="") root_list=root[i] count=0 root_len=len(root_list) for j in root_list: #経路を表示 count=count+1 print(j, end="") if(root_len!=count): print("->",end="") print() #実行結果 #頂点 0 : 重さ 4 : 3->1->0 #頂点 1 : 重さ 3 : 3->1 #頂点 2 : 重さ 2 : 3->2 #頂点 3 : 重さ 0 : 3->3 #頂点 4 : 重さ 2 : 3->4 #頂点 5 : 重さ 4 : 3->4->5 #頂点 6 : 重さ 3 : 3->4->6 #頂点 7 : 重さ 5 : 3->4->7 main()

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

元のソースがよく理解できなかったので、修正したソースを示すのみとします。

python

1 # X.insert(v,1) 2 X[v]=1 3 size=size+1 4 5 #確定した頂点と繋がっていて、未確定である地点に対して 6 #今確定した場所を経由した場合の距離を計算 7 for x in range(0,N): 8 if(X[x]!=1 and A[v][x]!=0): 9 if(L[x]>(L[v]+A[v][x])):#今までよりの距離より小さければ更新 10 L[x]=L[v]+A[v][x] 11 # if(len(root[x])==2): 12 # root[x]=[str(u),str(v),str(x)] 13 # else: 14 # root[x]=root[x][:-1].append(v) 15 # root[x]=root[x].append(x) 16 root[x]=root[v]+[x]

root[x]については、特に条件分岐は必要なくて、単にroot[v]までのルートの後ろにxをつなぐだけです。

投稿2023/01/18 21:29

actorbug

総合スコア2212

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

P_036

2023/01/19 00:58

ありがとうございます!! 今まで悩んでいたのが嘘みたいにあっさりできました…… 念の為スタートポイントuの値を変更して試してみたところ、しっかりとした経路が出ました。 説明不足の質問にもかかわらず回答して下さって、心から感謝します! 本当にありがとうございました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問