어떻게 python에서 dijkstra의 알고리즘을 통해 3 차원 목록을 실행합니까?

Question

저는 다이크 스트라의 알고리즘의 파이썬 구현을 작성하려고하는 학생입니다. 나는이 질문이 100 번 전에 물었다는 것을 알고있다. 그러나 나의 상황에 대한 약간의 구체화가있다. 나는 완전히 이해하지 못하고있다.

나는 10 개의 노드를 가진 가중치 있고 무향 인 그래프를 가지고 있습니다. 내 실제 그래프에는 더 많은 노드가 있습니다. 그래프는 3 차원 목록으로 정렬됩니다. 그래프를 생성하기 위해 작성한 프로그램의 일부 출력을 붙여 넣습니다.

`안녕하세요. 저는 Dykstra 's Algorithm의 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 사이의 가중치입니다. .

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] 3, 7, 8, 10, 5, 10, 7, 4, , [8]], [[3,2], [9,10]], [[2,1], [4,4], [5,8], [1, 6] , [1, 3], [2, 11], [4,2], [7,3], [10,4]], [[1,11], [6,10], [3,1 ] [] [], [[4,5], [8, 4]]

그래서 도전 과제는 목록을 입력으로 받아 들일 최적의 경로를 출력하는 dykstra의 파이썬 구현을 찾는 것입니다. 대부분의 그래프는 사전 데이터 유형을 중심으로 구축 된 것처럼 보이지만 그건 내 상황이 아닙니다.

3D 목록을 사용하여 내 자신 만의 dijkstra를 작성하려고했지만 운이 좋지 않았습니다. 조금 복잡하기 때문에. 또한 이전에 게시 된 dijkstra의 알고리즘을 Python에서 사용하려고 시도했지만 3 차원 목록이 아닌 사전을 실행하도록 설계되었습니다. 여기에 나의 이전 시도가있다. 나는 잠시 동안 고민 했어요으로

[[[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을 고려하면 '선택한 경로'와 '모두 방문하지 않은 노드'에 대한 3 가지 데이터 구조가 있어야하고 ' 이전 반복에서 사용되지 않음 '. 간단한 목록 비교 또는 체킹 (chekcking)으로 구현할 수있는 이웃 라우터를 확인하고 가장 비용이 적게 드는 이웃을 선택하여 선택한 경로에 추가 한 다음 사용되지 않은 이웃 노드를 이전 반복에서 사용하지 않은 것으로 추가합니다. 선택한 경로 노드로 이동하여 이웃 라우터와 이전 반복 노드를 비교하면 모든 경로가 선택한 경로 구조에서 사용 가능할 때까지 계속됩니다.

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 할 것이라고 생각한다. - 질문이있을지라도 코멘트에 명확한 설명을달라고한다. 나는 이것이 당신을 돕기를 바랍니다.