Python3에서 재귀를 사용한 Dijkstra 방법

5851 단어 Python3algorithm

코드



dijkstra.py
def Dijkstra(u, w):
    Q = [i for i in range(n)]
    if len(Q) != 0:
        Q.remove(u)
        for next in G[u]:
            v = next[0]
            u_to_v = next[1]
            if distance[v] > u_to_v + w:
                distance[v] = u_to_v + w
            Dijkstra(v, u_to_v + w)


n = int(input())
G = []
for i in range(n):
    G.append([])
    b = list(map(int, input().split()))
    for j in range(0, len(b) - 1, 2):
        G[i].append([b[j], b[j + 1]])

inf = 9999
distance = [inf] * n
start = 0
distance[start] = 0
Dijkstra(start, 0)
for i in distance:
    print(i)


변수 설명


  • n
    노드 수
  • G
    유향 그래프
  • distance
    start와 각 노드 사이의 거리
  • Q
    노드 집합(노드를 통과했는지 결정용)

  • 입출력



    입력


    ノードの数(n)
    ノード0から進めるノードx ノード0とノードxとの距離 ・・・
    ノード1から進めるノードx ノード1とノードxとの距離 ・・・
    ノード2から進めるノードx ノード2とノードxとの距離 ・・・
    ・
    ・
    ・
    ノードnから進めるノードx ノードnとノードxとの距離 ・・・
    

    출력


    startノードとノード0との最短距離
    startノードとノード1との最短距離
    startノードとノード2との最短距離
    ・
    ・
    ・
    startノードとノードnとの最短距離
    



    입력


    8
    1 5 4 9 7 8
    3 15 2 12 7 4
    3 3 6 11
    6 9
    5 4 7 5 6 20
    2 1 6 13
    
    2 7 5 6
    



    출력


    0
    5
    14
    17
    9
    13
    25
    8
    

    좋은 웹페이지 즐겨찾기