플로이드 워셜은 아닌데 저도 과제때문에 했던 다익스트라 경로 구하는 코드입니다. 참고가 됐으면 좋겠네요

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)