✍🏻플로이드 와샬(Floyd Warshall) 알고리즘

📢다익스트라 알고리즘 vs 플로이드 와샬 알고리즘

• 다익스트라 알고리즘 : 하나의 정점에서 다른 모든 정점으로의 최단거리(음의 가중치 불가능)
• 플로이드 와샬 알고리즘 : 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘(음의 가중치 가능)

---

💡 플로이드 와샬 알고리즘이란?

• 플로이드 와샬 알고리즘은 인접 행렬 표기법을 사용한다.

👏🏻플로이드 와샬 알고리즘은 어떤 알고리즘일까?

• 우선 다음과 같은 그래프가 있다고 해보자!
  
• 이 그래프를 인접 행렬로 나타내면 아래와 같다.
  
• 우리가 궁금한 것은 모든 정점 사이의 최단 거리로, 즉 i번 정점에서 j번 정점 사이의 최단거리이다. (여기서 i, j는 1~4 사이의 임의의 숫자이다.)

• 따라서, 미리 플로이드 와샬 알고리즘을 적용한 최종 결과 그래프를 살펴보면 다음과 같다.
  
• 위의 행렬을 해석하는 방법은 행이 i, 열이 j일때 i번 정점에서 j번 정점 사이의 최단거리임을 기억하면 된다.
• 예를 들어서 i=1, j=3일때 행렬의 값을 읽으면 -2이다.
  이는 i번 정점에서 j번 정점 사이의 최단거리는 -2라고 해석하면 된다.

---

👏🏻플로이드 알고리즘의 핵심

• 핵심 ☞ adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

• i에서 j사이의 최단 거리를 구하려면 2가지 경우를 비교해야 된다. k를 경유지(임의의 정점)라고 하자.
  1) 경유지 k를 지나지 않는 경로 (i → j)
  2) 경유지 k를 지나는 경로 (i → k → j)

• 따라서 플로이드 와샬 알고리즘은 임의의 (경유지) 정점 k에 대해서 k를 지나는 경로 vs k를 지나지 않는 경로 중에서 더 작은 값을 최단 경로로 선택하는 알고리즘이다.

• 두 꼭짓점 간의 추정 최단 경로를 최적이 될 때까지 점진적으로 개선시켜서 최단경로를 찾는다.

---

👏🏻직접 차례대로 구해보자!

1. 다음과 같은 그래프를 인접 행렬로 나타낸다.

• 예시 그래프

✔ 인접행렬로 나타내는 방법

• 자기자신으로 가는 간선(i, i)의 가중치는 0으로 초기화한다.
• 아직 경로가 지정되지 않은 간선 사이의 거리는 무한대(∞)로 초기화한다.

• 인접 행렬로 나타낸 것
  

---

2. 경유지 k에 대해 경유지k를 지나는 최단 경로 vs 경유지 k를 지나지 않을 때의 최단 경로를 비교해나가자.

• k = 1 / 경유지가 <1>인 경우
  • 1 -> 1 vs 1 -> <1> -> 1
  • 1 -> 2 vs 1 -> <1> -> 2
    ... (생략)
  • 2 -> 3 vs 2 -> <1> -> 3 ⭐경유지를 지날 때가 더 최솟값이므로 갱신한다⭐
    ... (생략)
  • 4 -> 4 vs 4 -> <1> -> 4

---

• k = 2 / 경유지가 <2>인 경우
  • 1 -> 1 vs 1 -> <2> -> 1
  • 1 -> 2 vs 1 -> <2> -> 2
  • 1 -> 3 vs 1 -> <2> -> 3
    ... (생략)
  • 4 -> 1 vs 4 -> <2> -> 1 ⭐경유지를 지날 때가 더 최솟값⭐
  • 4 -> 2 vs 4 -> <2> -> 2
  • 4 -> 3 vs 4 -> <2> -> 3 ⭐경유지를 지날 때가 더 최솟값⭐
  • 4 -> 4 vs 4 -> <2> -> 4

---

• k = 3, k = 4에 대해서도 반복하면 최종적으로 아래과 같은 결과가 나온다!
  

• 이것이 바로 최종적으로 모든 정점 사이의 최단 거리를 행렬로 표현한, 플로이드 와샬 알고리즘의 최종 결과이다 :D

---

👏🏻플로이드 와샬 알고리즘 코드 (python)

def make_graph(n, arr):
    # 자기자신으로 가는 간선은 0으로, 나머지는 무한대로 초기화
    graph = [[0 if (i == j) else float("inf") for i in range(n)] for j in range(n)]

    for u, v, w in arr:
        graph[u - 1][v - 1] = w

    return graph # 인접행렬으로 만든 후 리턴


def floyd_warshall(n, arr):
    # 1. 인접 행렬로 나타내기
    graph = make_graph(n, arr)

    # 2. [경유지(k)를 지나는 최단 거리] vs [경유지(k)를 지나지 않는 최단 거리]
    # 두 꼭짓점 간의 추정 최단 경로를 최적이 될 때까지 점진적으로 개선시켜서 최단경로를 찾음.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]

    return graph
   

⭐입력⭐

• 예시로 이 그래프를 출력해봅시다 :D
  

# n은 정점 개수 / arr은 [시작 정점, 도착 정점, 가중치(거리)]
n = 4
arr = [[1, 3, -2], [3, 4, 2], [4, 2, -1], [2, 1, 4], [2, 3, 3]]
answer = floyd_warshall(n, arr)

# 출력해보기
for ans in answer:
    print(ans)

⭐출력⭐

• 잘 나오네요 XD
  

---