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

前提

現在、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()

行動規範の内容に同意します

回答1件

ベストアンサー

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

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]