플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 다익스트라 알고리즘과 비슷하게 최단 경로를 구하는 것은 같습니다.

다익스트라 알고리즘은 하나의 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이고, 플로이드 워셜 알고리즘은 모든 쌍의 최단 경로를 구하는 알고리즘입니다.

또한 다익스트라 알고리즘과 달리 플로이드 워셜 알고리즘은 분산 시스템(Distributed System)에서 적용이 가능합니다. 그래서 Graph of Grap와 같은 데이터 구조에 적합합니다.

N개의 노드 값이 주어지면 N * N 형태의 2차원 배열로 다음과 같이 표현 할 수 있습니다.

Graph = [[0, 5 inf, inf],
	     [50, 0 ,15, 5],
         [30, inf, 0, 15],
         [15, inf, 5, 0]

이제부터는 다른 노드들을 지나서 본격적으로 중간노드를 활용하여서 최소 거리를 탐색하는 과정입니다.

Graph [i, j] = min (Graph [i , j], Graph [i , k] + Graph [k , j])

다음과 같은 형태로 최소 거리를 계산 할 수 있습니다.

1을 중간노드로 활용하는 경우

3 -> 1 -> 2
Graph[3][2] = min(inf, 35) => Graph[3][2] 는 35로 업데이트

4 -> 1 -> 2
Graph[4][2] = min(inf, 20) => Graph[4][2] 는 20으로 업데이트

Graph = [[0, 5, inf, inf],
	     [50, 0, 15, 5],
         [30, 35, 0, 15],
         [15, 20, 5, 0]

2를 중간노드로 활용하는 경우

1 -> 2 -> 3
Graph[1][3] = min(inf, 20) => Graph[1][3] 은 20으로 업데이트

1 -> 2 -> 4
Graph[1][4] = min(inf, 10) => Graph[1][4] 는 10으로 업데이트

Graph = [[0, 5, 20, 10],
	     [50, 0, 15, 5],
         [30, 35, 0, 15],
         [15, 20, 5, 0]

최종적으로

위와 같은 방식으로 1,2,3...n까지 거치는 경우를 계산한 경우 중간에서 최소값이 변경하고 가장 최적의 값을 찾아줍니다. 위의 예시 그래프는 다음과 같은 결과값이 나오게 됩니다.

Graph = [[0, 5, 15, 10],
	     [20, 0, 10, 5],
         [30, 35, 0, 15],
         [15, 20, 5, 0]

코드는 다음과 같습니다.

def FWA(Graph):
    dist = list(map(lambda i: list(map(lambda j: j, i)), Graph))

    # 정점을 개별적으로 적용
    for i in range(nV):
        for j in range(nV):
            for k in range(nV):
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])
        sol(dist, i)

def sol(dist, i):
    if i + 1 !=  nV:
        print(str(i) + "번째 결과값 입니다.")
    else:
        print("최종 결과값 입니다.")

    for i in range(nV):
        for j in range(nV):
            if(dist[i][j] == INF):
                print("INF", end=" ")
            else:
                print(dist[i][j], end="  ")
        print(" ")
    print("") # 가독성을 위해서 추가

INF = 1 << 10 # 1024
nV = 4 # 정점의 갯수

Graph = [[0, 5, INF, INF],
         [50, 0, 15, 5],
         [30, INF, 0, 15],
         [15, INF, 5, 0]]

FWA(Graph)

읽어주셔서 감사합니다.