pythonでdijkstraのアルゴリズムを使って3次元のリストをどのように実行しますか？

Question

私は、DykstraのアルゴリズムのPython実装を書くことを試みている学生です。私はこの質問が100回前に尋ねられたことを知っていますが、私の状況についての詳細はいくつかありますが、私は完全に理解していません。

私は10ノードの重み付け無向グラフを持っています。私の実際のグラフにはさらに多くのノードがあります。グラフは3次元のリストとしてソートされます。グラフを生成するために書き込んだプログラムの出力を貼り付けています。

`こんにちは。私はDykstraのアルゴリズムのPython実装を書こうとしている（試みている）学生です。私はこの質問が100回前に尋ねられたことを知っていますが、私の状況についての詳細はいくつかありますが、私は完全に理解していません。

私は10ノードの重み付け無向グラフを持っています。私の実際のグラフにはさらに多くのノードがあります。グラフは3次元のリストとしてソートされます。グラフを生成するために書き込んだプログラムの出力を貼り付けています。

Node 1 : [[8, 3], [9, 11], [2, 12], [3, 12], [7, 6]] 
Node 2 : [[5, 6], [4, 3], [1, 12], [8, 11], [7, 1]] 
Node 3 : [[6, 2], [1, 12], [5, 7], [9, 1]] 
Node 4 : [[2, 3], [8, 2], [10, 5], [5, 10], [7, 4]] 
Node 5 : [[2, 6], [4, 10], [3, 7], [7, 8]] 
Node 6 : [[3, 2], [9, 10]] 
Node 7 : [[2, 1], [4, 4], [5, 8], [1, 6], [8, 3]] 
Node 8 : [[1, 3], [2, 11], [4, 2], [7, 3], [10, 4]] 
Node 9 : [[1, 11], [6, 10], [3, 1]] 
Node 10 : [[4, 5], [8, 4]] 

グラフは、3次元のリストとして保存されます。たとえば、インデックス0では、ノード8,9,2,3と7への接続があります。ノード8と0の間の重みは3です。ノード0と9と11の間の重みです。 。 [[8,3]、[9,11]、[2,12]、[3,12]、[7,6]]、[[5,6]、[4,3]）[0126] ]、[1,12]、[8,11]、[7,1]]、[[6,2]、[1,12]、[5,7]、[9,1]]、[[2 3]、[8,2]、[10,5]、[5,10]、[7,4]]、[[2,6]、[4,10]、[3,7]、[7 、[8]、[[3,2]、[9,10]]、[[2,1]、[4,4]、[5,8]、[1,6]、[8,3]] [[1,3]、[2,1]、[4,2]、[7,3]、[10,4]]、[[1,11]、[6,10]、[3,1

したがって、課題は入力としてリストを受け入れる最適なルートを出力するdykstraのPython実装を見つけることです。ほとんどのグラフは辞書のデータ型の周りに構築されているようですが、それは私の状況ではありません。

3Dリストを使用して私自身のバージョンのdijkstraを書き始めようとしましたが、運が足りませんでした。また、私はPythonでdijkstraのアルゴリズムの以前に投稿されたバージョンを使用しようとしましたが、三次元のリストではなく辞書を実行するように設計されています。ここに私の以前の試みがあります。

[[[4, 2], [2, 1], [3, 4]], [[1, 1], [4, 2], [3, 4]], [[1, 4], [2, 4], 
[4, 4]], [[1, 2], [2, 2], [3, 4]]] 

class Graph: 
    def __init__(self): 
    self.nodes = set() 
    self.edges = defaultdict(list) 
    self.distances = {} 

    def add_node(self, value): 
    self.nodes.add(value) 

    def add_edge(self, from_node, to_node, distance): 
    self.edges[from_node].append(to_node) 
    self.edges[to_node].append(from_node) 
    self.distances[(from_node, to_node)] = distance 


def dijsktra(graph, initial): 
    visited = {initial: 0} 
    path = {} 

    nodes = set(graph.nodes) 

    while nodes: 
    min_node = None 
    for node in nodes: 
     if node in visited: 
     if min_node is None: 
      min_node = node 
     elif visited[node] < visited[min_node]: 
      min_node = node 

    if min_node is None: 
     break 

    nodes.remove(min_node) 
    current_weight = visited[min_node] 

    for edge in graph.edges[min_node]: 
     weight = current_weight + graph.distance[(min_node, edge)] 
     if edge not in visited or weight < visited[edge]: 
     visited[edge] = weight 
     path[edge] = min_node 

    return visited, path 

私はしばらくの間、これで苦労してきたように私は本当に、誰も私に与えることができる任意のヘルプを大幅に感謝することでしょう。ありがとうございました！

Answer 1

利用可能な実装を試してみることをお勧めしますが、複雑なアルゴリズムではないので、独自のコードを試すことができます。 simple case of dijkstra

図のように、すべてのノードでアルゴリズムを別々に実行し、ノード0を考慮に入れるだけで、「選択されたルート」と「すべての未訪問のもの」、以前の反復で未使用 '単純なリストの比較やチェクキングで実装可能なネイバーをチェックし、最もコストの低いネイバーを選択して選択したルートに追加し、未使用のネイバーを前回のイテレーションで未使用として追加します。あなたが選択したルートノードに行き、それを隣のノードと以前の繰り返しのノードと比較すると、選択したルート構造ですべてのノードが使用可能になるまでこれを続行します。

Answer 2

次はあなたのデータ構造で動作するようです：

initial=1  #This is the number-label (not the index) of your starting node 
assigned={} #When a node has been given a permenant min-weight 
visited={initial:0} #When a node has a temporary min-weight 
path={initial:[initial]} #stores the path after a permenant weight has been assigned 

myGraph = [[[8, 3], [9, 11], [2, 12], [3, 12], [7, 6]], [[5, 6], [4, 3], [1, 12], [8, 11], [7, 1]], [[6, 2], [1, 12], [5, 7], [9, 1]], [[2, 3], [8, 2], [10, 5], [5, 10], [7, 4]], [[2, 6], [4, 10], [3, 7], [7, 8]], [[3, 2], [9, 10]], [[2, 1], [4, 4], [5, 8], [1, 6], [8, 3]], [[1, 3], [2, 11], [4, 2], [7, 3], [10, 4]], [[1, 11], [6, 10], [3, 1]], [[4, 5], [8, 4]]] 

while len(assigned)<len(myGraph): 
    next_node= min(visited,key=visited.get) 
    assigned[next_node]=visited[next_node] 
    del visited[next_node] 
    for node in myGraph[next_node-1]: # The minus one is because your nodes are numbered from 1 (as apposed to 0). 
     if node[0] in visited: 
      if visited[node[0]]>assigned[next_node]+node[1]: 
       visited[node[0]]=assigned[next_node]+node[1] 
     else: 
      if node[0] in assigned: 
       if assigned[node[0]]+node[1]==assigned[next_node]: 
        path[next_node]=path[node[0]]+[next_node] 
      else: 
       visited[node[0]]=assigned[next_node]+node[1] 

pathは、あなたの最初のノードが何であれから始まるパスを表示するリストを含む辞書です。私は各ステップを説明しますが、私はちょうどあなたがすでに知っているように思うDikstraのアルゴリズムをexplaingしていると思う - もしあなたが質問がある場合は、コメントの明確化を求めてください。これがあなたに役立つことを願っています