1

重み付き無向グラフを解くためにダイクストラ法を実装したプログラムを書いています。

以下の入力で実行するとエラーが起きてしまうのですが、どのように修正するべきかわからず、質問させていただきました。

ダイクストラ法を実装したコード

def shortest_length(G, start):
    S = {start:0}; D={}
    while len(S)>0:
        x = select_min(S);m=S[x];D[x]=m
        for (y,w) in edge(G, x):
            if y in S:
                if S[y]>m+w:
                    S[y] = m + w
            elif y not in D:
                S[y] = m + w
        print('仮', S, '確定', D)

def select_min(S):
    m = -1
    for a in S:
        if m == -1 or m > S[a]:
            x == a
            m = S[a]
    return x

def edge(G,x):
    return ([(b, G[(a,b)])for (a,b) in G if a == x]
        +[(a, G[(a,b)]) for (a,b) in G if b == x])

入力

>>> from Dijksta import shortest_length
>>> G = {('A','B'):1, ('A', 'D'):3, ('B', 'D'):3, ('B', 'E'):5, ('C', 'E'):3, ('D', 'E'):1}
>>> shortest_length(G, 'A')

エラー

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/username/Desktop/Dijkstra.py", line 4, in shortest_length
    x = select_min(S);m=S[x];D[x]=m
  File "/Users/username/Desktop/Dijkstra.py", line 17, in select_min
    x == a
NameError: name 'x' is not defined

2 件の回答 2

1

探索し終えた要素をリストSから削除してないことが主要な原因だと思います。
pythonではなくc++ですみませんが、以下のように書くとスッキリすると思います。
計算量O(V^2)

/*
Q: キュー
start: 開始地点
dp[i]: 点iに到達するまでにかかる最小コスト。最初は全て+INFに初期化しておく。
v[i]: 点iにj番目に隣接している要素のリスト
c[i][j]: 点iから、点iにj番目に隣接している要素のまでのコスト
*/

dp[start]=0;
Q.push(start)
while(!Q.empty()){
    int p = Q.front();Q.pop();
    for(int i=0;i<v[p].size();i++){
        int q = v[p][i];
        if(dp[q]>dp[p]+c[p][i]){
            dp[q]=dp[p]+c[p][i];
            Q.push(q);
        }
    }
}

追伸
ご質問者のコードは最小コストの要素を選んでいることから、計算量 O((E+V)\log{V})の修正dijkstra法を実装したかったのかと推測しましたが、最小値の探索にO(V)かけているので、むしろ標準のdijkstra法よりも計算量が増えてるように思われます。
質問事項ではないですが、念の為。

1

エラーメッセージで、関数select_minの中の式x == aでエラーが起きていると書いてあるので、まずはそこを見てみましょう。これはxaを比較していますが、この時点では、関数の中でxを定義していないのでエラーになっています。値の代入x = aがしたかったことでしょうか。

def select_min(S):
    m = -1
    for a in S:
        if m == -1 or m > S[a]:
            x == a # ここがエラー
            m = S[a]
    return x
3
  • ご指摘いただきましてありがとうございます。修正したところ、出力はされるようになりました。しかしながら繰り返し処理が止まらなくなり、永遠とprint()が実行されるというバグが見つかりました。
    – user32568
    Commented 2019年3月21日 13:00
  • > 永遠とprint()が実行されるというバグ は、 shortest_length の中でループの条件に指定している len(S) が増えることはあっても減ることがないのが原因でしょう。
    – PicoSushi
    Commented 2019年3月21日 13:14
  • 1
    @Nao PicoSushiさんがおっしゃるように、Sの要素が減ることがないため無限ループになっているいますが、全体的にうまくダイクストラ法が実装できてないようです。
    – Hideki
    Commented 2019年3月21日 16:26

この質問に回答するには、ログインする必要があります。