53768


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

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

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

[code]

    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])
    
[/code]

入力

[code]

    >>> 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')
    
[/code]

エラー

[code]

    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
    
[/code]


CC BY-SA 4.0
2019-03-21T12:37:48.893
53627
2019-03-27T18:25:39.793
2019-03-21T13:00:20.017
29826
question
python python3 アルゴリズム
重み付き無向グラフを解くためのダイクストラ法に関するコードのエラー


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

[code]

    def select_min(S):
        m = -1
        for a in S:
            if m == -1 or m > S[a]:
                x == a　# ここがエラー
                m = S[a]
        return x
    
[/code]


CC BY-SA 4.0
2019-03-21T12:50:35.343
53628
2019-03-21T12:50:35.343
3605
53627
answer


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

[code]

    /*
    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);
            }
        }
    }
    
[/code]

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


CC BY-SA 4.0
2019-03-27T13:54:16.437
53768
2019-03-27T18:25:39.793
2019-03-27T18:25:39.793
30800
30800
53627
answer