파이썬 플로이드 워셜 최단경로에 대해 질문 드립니다
조회수 805회
처음으로 이 사이트를 써봅니다 다름이 아니라 공부를 하는중 최단 시간은 구할수 있지만 경로를 구하지 못해서 질문 드립니다
INF=int(1e9)
def print_d(x=0):
if x:
print(f'=[{n+1}]노드 거쳐간 후 최단거리=')
else:
print('=탐색전 초기값=')
for i in range(len(d)):
for j in range(len(d)):
if d[i][j]==INF:
print(' ∞', end=' ')
else:
print(f'{d[i][j]:2}', end=' ')
print()
node=int(input('노드 개수 입력:'))
d=[[INF]*node for i in range(node)]
for i in range(node):
for j in range(node):
if i == j:
d[i][j] = 0
else:
line = int(input(f'{i+1}→{j+1}의 거리 입력(없으면 0):'))
if line:
d[i][j] = line
print_d()
재 위의 코딩을 아래의 최단 경로 처럼 표현할려면 어떻게 해야하는지 제발 알려주세요.
-
(•́ ✖ •̀)
알 수 없는 사용자 - 〉
1 답변
-
플로이드 워셜은 아닌데 저도 과제때문에 했던 다익스트라 경로 구하는 코드입니다. 참고가 됐으면 좋겠네요
from math import inf from collections import defaultdict def dijkstra_path(W): V = len(W) F = defaultdict(list) # 최단경로를 구성하는 이음선들의 집합 P = defaultdict(list) # 각 마디들의 최단경로 집합 S = defaultdict(list) # 각 마디까지의 최단거리 집합 path = [] # 최단경로를 저장하는 리스트 touch = [0] * V length = [W[0][i] for i in range(V)] length[0] = -1 for _ in range(V-1): min = inf for i in range(V): if (0 < length[i] < min): min = length[i] vnear = i F[touch[vnear]].append(vnear) t=0 k=[] if len(path) == 0: path.append([touch[vnear]+1]) elif len(F[touch[vnear]]) > 1: # 한 개의 마디에서 여러 마디로 가는 경우 k = [] # path리스트 복사 for i in path: k.append(i) for i in k: # 새로운 경로 생성시 무한으로 생성되지 않게 복사한 k를 사용 for j in range(len(i)): if (i[j] == touch[vnear]+1) & (t != 1): t = 1 # 경로를 중복으로 생성하는걸 방지 path.append(i[0:j+1]) if t != 1: # 새로운 경로를 생성하지 않은 경우 기존 경로에 마디 추가 for i in path: for j in range(len(i)): if i[j] == touch[vnear]+1: i.insert(j+1, vnear+1) else: # 새로 생성된 경로에 마디 추가 for i in range(len(k), len(path)): for j in range(len(path[i])): if path[i][j] == touch[vnear]+1: path[i].insert(j+1, vnear+1) for i in range(V): if (length[vnear] + W[vnear][i] < length[i]): length[i] = length[vnear] + W[vnear][i] touch[i] = vnear S[vnear].append(length[vnear]) # 최단거리 저장 length[vnear] = -1 for i in range(V-1): P[i+2].append(-1) for k in P: for i in path: for j in range(len(i)): if (k == i[j]) & (P[k][0] == -1): P[k].append(str(i[:j+1]).strip('[]')) P[k].remove(-1) for i in P: print("V{0}까지 최단 경로(거리 : {1}) : V{2}".format(i, str(S[i-1]).strip('[]'),'->V'.join(P[i][0].split(', ')))) W = [[0, 7, 4, 6, 1], [inf, 0, inf, inf, inf], [inf, 2, 0, 5, inf], [inf, 3, inf, 0, inf], [inf, inf, inf, 1, 0]] dijkstra_path(W)
댓글 입력