[코드트리] 2차원 배열 입력 > 플로이드-워셜 알고리즘(Warshall algorithm)

플로이드-워셜 알고리즘
한 정점으로부터 다른 모든 정점까지의 최단거리를 모든 정점에 대해 구하는 알고리즘

dist[A][B] = min(dist[A][B], dist[A][C] + dist[C][B])

 

- 왼쪽과 같은 그래프가 존재할 때, 오른쪽 표는 i -> j로 가는 최단거리

- 자기 자신은 0으로, 도달할 수 없는 노드(선으로 연결되어 있지 않은 노드)는 무한대로 초기화

 

플로이드 와샬 알고리즘은 노드 선택 순서가 중요!

제일 먼저 거칠 노드  C를 정한 후, 시작 노드 A와 도착 노드 B를 정해야 함

=> 그래야 시작 노드에서 도착 노드의 최솟값 갱신이 순서에 상관없이 가능

 

 

ex)

2번 노드를 거쳐 가는 경우

 

 

이 그래프에서 2번 노드를 거쳐가면서 경로가 짧아지는 경우는 3번 노드 -> 4번 노드로 가는 경우

따라서 값이 ∞->4로 변경됨

(방향이 정해져 있으므로 대칭행렬 아님)

 

3번 노드를 거쳐 가는 경우

 

 

1번 노드 -> 2번노드는 6 -> 5로

4번 노드 -> 2번 노드 ∞->2로 갱신

 

 

마지막으로 4번 노드를 거치는 경우

 

 

1번 노드 -> 3번 노드 4->2

1번 노드 -> 2번 노드 5 -> 3으로 갱신

이전 3번 노드를 거치면서 최소 거리를 갱신했으므로 이렇게 구할 수 있음

2번 노드 -> 3번 노드 ∞->4로 갱신

 

이러한 원리로 모든 정점에서 다른 모든 정점까지의 최단거리를 구할 수 있다.

 

---

문제

arr = [[0, 0, 1],
       [1, 0, 0],
       [0, 1, 0]]

for k in range(3):
    for i in range(3):
        for j in range(3):
            if arr[i][k] and arr[k][j]:
                arr[i][j] = 1

result = 0
for i in range(3):
    result += sum(arr[i])
print(result)

#### 결과
9

실행 풀이

f947a5e8-5501-4496-b30a-8f7edadb0e56.mp4

1.82MB

 

 

 

 

 

 

[출처] [알고리즘] Floyd - Warshall (플로이드 - 와샬)|작성자 홍거루