[알고리즘] 플로이드 와샬 알고리즘 파이썬(Python)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. 플로이드 와샬 알고리즘 파이썬(Python)

- 모든 노드에서 모든 노드까지 최단 경로를 계산하는 알고리즘

- 다이나믹 프로그래밍과 비슷한 알고리즘

- 시간 복잡도는 O(N^3)

 

#경유지
for k in range(N):
    #출발지
    if k == i continue
    for i in range(N):
        #도착지
        for j in range(N):
            if (i==j) or (j==k): continue
            if adj[i][j]>adj[i][k] + adj[k][j] :
                adj[i][j] = adj[i][k] + adj[k][j]