파이썬 플로이드 워셜 최단경로에 대해 질문 드립니다

조회수 68회

처음으로 이 사이트를 써봅니다 다름이 아니라 공부를 하는중 최단 시간은 구할수 있지만 경로를 구하지 못해서 질문 드립니다 이미지 이미지

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()

이미지

재 위의 코딩을 아래의 최단 경로 처럼 표현할려면 어떻게 해야하는지 제발 알려주세요.

  • 코드를 이미지로 올리지 마세요 초보 2021.6.8 08:50
  • 죄송합니다 처음 써봐서 ㅎㅎ 주의 하겠습니다. 도마맛 2021.6.8 15:00

1 답변

  • 좋아요

    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)
    
    
    • 와 정말 감사합니다. 좋은 참고가 될것 같습니다. 도마맛 2021.6.8 14:47

답변을 하려면 로그인이 필요합니다.

Hashcode는 개발자들을 위한 무료 QnA 사이트입니다. 계정을 생성하셔야만 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 계정을 생성하셔야만 글을 작성하실 수 있습니다.