[알고리즘] 최단거리 알고리즘 - 플로이드 와샬 알고리즘

포인트

• 플로이드 와샬 알고리즘은 최단거리를 구하는 알고리즘으로 모든 점에서 모든 점에 최단 거리를 구해주는 알고리즘 입니다.  단, 그래프 내부에 음수 사이클이 있는 경우 최단 거리를 구할 수 없습니다. 
• dp (다이나믹) 을 활용하여 시간 복잡도 O(n^3)에서 문제를 해결합니다.

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

# 플로이드 와샬 알고리즘 O(n^3) 에 문제를 해결할 수 있으면,
# dp 를 사용하여 모든 점에서 모든 점 최단 거리를 구해준다.
# 음수 사이클이 있는 경우 구할 수 없다. (벨만 포드와 똑같다.)

INF = 987654321

data = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
]
number = len(data)

d = [[0] * number for _ in range(number)]
for i in range(number):
    for j in range(number):
        d[i][j] = data[i][j]


# 데이터 입력
def floyd_warshall():

    for k in range(number):
        for i in range(number):
            for j in range(number):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]


# a-> b 로 가는 것이 많은가? a -> c -> b로 거치는 것이 빠른가?
floyd_warshall()

# 플로이드 와샬 알고리즘

for i in range(number):
    for j in range(number):
        print(d[i][j], end=' ')
    print()

# 0 5 11 8
# 7 0 9 13
# 2 7 0 4
# 5 10 3 0