플로이드 워셜

이름은 진짜 많이 들었는데 이번에 처음 공부하는 알고리즘이다.

먼저 책을 읽고 와야겠다.

 

아 처음공부하는거라 생각했는데 이거 학부생때 알고리즘 수업시간에 배운거같다.

개념은 읽고 코드는 안봤다. 이해한 개념을 바탕으로 코드를 직접 구현해보자.

 

INF = 9999999

V = int(input("노드 개수 : "))
E = int(input("간선 개수 : "))
graph = [[INF] * (V + 1) for _ in range(V + 1)]

print("노드1,노드2,거리순으로 간선정보를 하나씩 입력하기")
for i in range(E):
    src, dst, dist = map(int,input(f'{i+1}번째 간선 입력 (총 {E}개)\n').split())
    graph[src][dst] = dist

#자기 자신으로 가는건 항상 0
for i in range(V + 1):
    graph[i][i] = 0

#플로이드 워셜 Floyd-Warshall
for v in range(1, V + 1):
    for src in range(1, V + 1):
        for dst in range(1, V + 1):
            graph[src][dst] = min(graph[src][dst], graph[src][v] + graph[v][dst])

#수행 결과 출력
for a in range(1, V + 1):
    for b in range(1, V + 1):
        if graph[a][b] == INF:
            print("INF", end=" ")
            continue
        print(graph[a][b], end=" ")
    print()

 

진짜 단순하다.. 엄청 쉽네 ㄷㄷ

다익스트라 한 번 더 복습하고 문제 풀이 들어가야겠다.