플로이드 워샬 알고리즘 요약 정리

플로이드 워샬 알고리즘 이란

모든 정점의 쌍 사이의 최단 거리를 구하는 알고리즘 

정점 사이의 최단 거리를 구하기 때문에 방향 그래프와 무방향 그래프 모두 상관없이 해당 알고리즘을 사용할 수 있다.

푸는 방법은 꽤 단순한데 N개의 정점이 있다면 NxN의 배열로 그래프를 나타낸 후에 해당 그래프를 최단거리 그래프로 교체해준다.

교체하는 방법은 거쳐가는 임의의 정점이 있다고 할때의 최단거리를 차례로 구한 후에 최솟값을 구하는 것. 

 

보통 3중 for문을 사용해서 풀며 다음과 같이 가장 첫 for문의 k가 거쳐가는 정점을 의미한다. 그리고 j와 i는 시작 정점과 도착 정점을 의미한다. 여기서 아래 코드와 같이 거쳐가는 정점이 있을 때의 거리와 원래의 j -> i로 가는 거리 중 최단거리를 선택하도록 하면 된다. 

for k in range(N):
    for j in range(N):
        for i in range(N):
            graph[j][i] = min(graph[j][i], graph[j][k] + graph[k][i])

추가적으로 각각의 최단 거리의 경로를 추적하는 방법은 최단거리를 구하는 알고리즘에 중간 정점을 저장하는 그래프를 추가하면 된다. 

기본적으로 graph[a][b] = b 의 도착 정점을 저장하는 그래프이며 다음과 같이 저장해주면 된다. 

for k in range(N):
    for j in range(N):
        for i in range(N):
            if graph[j][k] + graph[k][i] < graph[j][i]:
                graph[j][i] = graph[j][k]

그후에 경로를 출력할 때는  다음과 같이 queue나 stack으로 추적해서  출력해주면 끝. 

for j in range(N):
    for i in range(N):
        queue = deque()
        queue.append((j, i))
        while queue:
            y, x = queue.pop()
            result.append(y)
            if graph[y][x] == 0:
                print(result)
            else:
                queue.append((graph[y][x], x))

 

 

Reference

• https://blog.encrypted.gg/1035