2

私はPythonにかなり慣れていないので、ここでダイクストラのアルゴリズムを実装しようとしています: http://thomas.pelletier.im/2010/02/dijkstras-algorithm-python-implementation/。問題は、私のマトリックスが次のようになっていることです。

    {
      2845: {27026: {'weight': 0.05950338}, 83860: {'weight': 0.013386887}},
     12422: {27023: {'weight': 0.0787193}, 27026: {'weight': 0.041424256}, 59721: {'weight': 0.11553069}},
     27022: {27025: {'weight': 0.1283993}, 83860: {'weight': 0.11746721}},
     27023: {12422: {'weight': 0.0787193}, 27025: {'weight': 0.22683257}},
     27025: {27022: {'weight': 0.1283993}, 27023: {'weight': 0.22683257}, 27026: {'weight': 0.20290035}},
     27026: {2845: {'weight': 0.05950338}, 12422: {'weight': 0.041424256}, 27025: {'weight': 0.20290035}},
     59721: {12422: {'weight': 0.11553069}},
     83860: {2845: {'weight': 0.013386887}, 27022: {'weight': 0.11746721}}
}

これは上記のアルゴリズムで引き続き機能しますか、それとも少し調整する必要がありますか?

ありがとう

編集：

ここで私が実装したアルゴリズム:

def dijkstra(self, graph, start, end):
        D = {} # Final distances dict
        P = {} # Predecessor dict

        for node in graph.keys():
            D[node] = -1 # Vertices are unreachable
            P[node] = ""
        D[start] = 0 # The start vertex needs no move
        unseen_nodes = graph.keys() # All nodes are unseen

        while len(unseen_nodes) > 0:
            shortest = None
            node = ''
            for temp_node in unseen_nodes:
                if shortest == None:
                    shortest = D[temp_node]
                    node = temp_node
                elif (D[temp_node] < shortest):
                    shortest = D[temp_node]
                    node = temp_node
            unseen_nodes.remove(node)
            for child_node, child_value in graph[node].items():
                if D[child_node] < D[node] + child_value:
                    D[child_node] = D[node] + child_value
                    P[child_node] = node
        path = []
        node = end
        while not (node == start):
            if path.count(node) == 0:
                path.insert(0, node) # Insert the predecessor of the current node
                node = P[node] # The current node becomes its predecessor
            else:
                break
        path.insert(0, start) # Finally, insert the start vertex
        return path

私が使用している行列は上記のとおりです。アルゴリズムが必要とする行列は次のとおりです。

... graph = {
...     'A': {'B': 10, 'D': 4, 'F': 10},
...     'B': {'E': 5, 'J': 10, 'I': 17},
...     'C': {'A': 4, 'D': 10, 'E': 16},
...     'D': {'F': 12, 'G': 21},
...     'E': {'G': 4},
...     'F': {'H': 3},
...     'G': {'J': 3},
...     'H': {'G': 3, 'J': 5},
...     'I': {},
...     'J': {'I': 8},
... }
4

2 に答える 2

0

与えられたソースコードの例では、重みは単なる整数であり、辞書ではありませんでした。グラフには「重み」キーの付いた辞書があるため、それに応じてコードを変更する必要があります。

コードの正しいバージョンは次のとおりです。

def dijkstra(self, graph, start, end):
        D = {} # Final distances dict
        P = {} # Predecessor dict

        for node in graph.keys():
            D[node] = -1 # Vertices are unreachable
            P[node] = ""
        D[start] = 0 # The start vertex needs no move
        unseen_nodes = graph.keys() # All nodes are unseen

        while len(unseen_nodes) > 0:
            shortest = None
            node = ''
            for temp_node in unseen_nodes:
                if shortest == None:
                    shortest = D[temp_node]
                    node = temp_node
                elif (D[temp_node] < shortest):
                    shortest = D[temp_node]
                    node = temp_node
            unseen_nodes.remove(node)
            for child_node, child_value in graph[node].items():
                if D[child_node] < D[node] + child_value['weight']:  # I changed the code here
                    D[child_node] = D[node] + child_value['weight']   # I changed the code here
                    P[child_node] = node
        path = []
        node = end
        while not (node == start):
            if path.count(node) == 0:
                path.insert(0, node) # Insert the predecessor of the current node
                node = P[node] # The current node becomes its predecessor
            else:
                break
        path.insert(0, start) # Finally, insert the start vertex
        return path
于 2013-02-13T22:44:49.597 に答える
0

これでうまくいくと思いますが、コードによって異なります。より完全な回答が必要な場合は、残りのコードを投稿してください。

また、2D 配列を作成するだけでなく、辞書を操作する方がおそらく頭痛の種になるでしょう。本当に dict を使用したい場合は、デフォルトの dictを使用することをお勧めします。

于 2013-02-13T22:04:44.040 に答える