Python3에서 재귀를 사용한 Dijkstra 방법
코드
dijkstra.pydef 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)
변수 설명
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)
노드 수
유향 그래프
start와 각 노드 사이의 거리
노드 집합(노드를 통과했는지 결정용)
입출력
입력
ノードの数(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
Reference
이 문제에 관하여(Python3에서 재귀를 사용한 Dijkstra 방법), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/mk668a/items/3bf225eddcd5bf6ef581
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
ノードの数(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
Reference
이 문제에 관하여(Python3에서 재귀를 사용한 Dijkstra 방법), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/mk668a/items/3bf225eddcd5bf6ef581텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)