[파이썬/Python] 최단 경로 알고리즘 작동원리 이해하기 ( Floyd-washall )

[파이썬/Python]  최단 경로 알고리즘 작동원리 이해하기 ( Floyd-washall )

---

서론

[파이썬/Python] 최단 경로 알고리즘 구현하기 ( Dijkstra / Bellman-ford / floyd-warshall )

이전 시간 구현하였던 Floyd-washall 알고리즘의 작동원리에 대해 간단한 예제를 통해 그림으로 이해해보려고 합니다.

---

본론

문제 1. Floyd-washall 알고리즘을 이용하여 위 그래프의 𝑑𝑖𝑗𝑘와 𝑝𝑖𝑗𝑘가 만들어지는 과정을 그림으로 제시하시오.

for k in self.graph.nodes: # 중간 정점 집합 {1, 2, ..., k}
    for i in self.graph.nodes: # i : 시작 정점
        for j in self.graph.nodes: # j : 마지막 정점
            if d[i][k] + d[k][j] < d[i][j]: # 더 짧을 경우
                self.floyd_warshall_p[i][j] = k # 정점 저장
                d[i][j] = d[i][k] + d[k][j] # 경로 길이 저장

핵심 코드입니다.

i → j 로 도달하기 위해 k는 i → k → j 로 중간 지점을 맡고 있으며,

W에는 중간 없이 한번에 이동할 수 있는 값들이,

D에는 새롭게 추가된 최단 경로들이,

P에는 그 최단 경로로 가기 위해 거쳐가야하는 정점(k)가 저장됩니다.

 

k=1 일 때 입니다.

 

행렬 D에 저장되어 있는 값에 따라 새롭게 추가 될 수 있는 경로는 2 → 1 → 6 입니다.

 

k=2 일 때 입니다.

 

행렬 D에 저장되어 있는 값에 따라 새롭게 추가 될 수 있는 경로는

1 → 2 → 4, 3 → 2 → 1, 3 → 2 → 4, 3 → 2 → 6, 4 → 2 → 1, 4 → 2 → 6입니다.

 

기존에 최단 경로로 설정되어 있던 4 → 6 ( =19 )가 4 → 2 → 6 ( =18 )로 교체됩니다.

 

k=3 일 때 입니다.

 

행렬 D에 저장되어 있는 값에 따라 새롭게 추가 될 수 있는 경로는

4 → 3 → 2, 5 → 3 → 2, 5 → 3 → 1, 5 → 3 → 6 입니다.

 

새롭게 추가되려 했던 4 → 3 → 2 (=21) 가 기존에 최단 경로로 설정되어 있던 4 → 2 ( =5 )로 인해 추가되지 못했습니다.

 

k=4 일 때 입니다. 노드 4가 대부분의 노드들과 연결되어 있어 경우의 수 가 많이 나왔습니다.

 

행렬 D에 저장되어 있는 값에 따라 새롭게 추가 될 수 있는 경로는

2 → 4 → 3, 2 → 4 → 5, 2 → 4 → 6, 2 → 4 → 7, 5 → 4 → 2, 5 → 4 → 3, 5 → 4 → 6, 5 → 4 → 7, 7 → 4 → 2, 7 → 4 → 3, 7 → 4 → 5, 7 → 4 → 6, 1 → 4 → 5, 1 → 4 → 3, 3 → 4 → 5, 3 → 4 → 7, 5 → 4 → 1, 7 → 4 → 1 입니다.

 

새롭게 추가되려 했던 2 → 4 → 6 (=37), 5 → 4 → 3 (=16) 가

기존에 최단 경로로 설정되어 있던 2 → 1 → 6 ( =13 ), 5 → 3 ( =12 )로 인해 추가되지 못했습니다.

 

기존 최단 경로였던

5 → 3 → 2 (=18),  5 → 3 → 6 (=31)이  

5 → 4 → 2 (=6), 5 → 4 → 6 (=19)으로 교체되었습니다.

 

k=5 일 때 입니다. 노드 4에서 노드 3으로 이동할 때, 4 → 3 과 4 → 5 → 3 의 경로 길이가 1이 차이나는데, 이 부분으로 많은 최단 경로들이 갱신되었습니다.

 

행렬 D에 저장되어 있는 값에 따라 새롭게 추가 될 수 있는 경로는

1 → 5 → 3, 1 → 5 → 7, 2 → 5 → 3, 4 → 5 → 3, 7 → 5 → 1, 7 → 5 → 3 입니다.

 

기존 최단 경로였던

1 → 4 → 3 (=37), 2 → 4 → 3 (=33), 4 → 3 (=15), 7 → 4 → 3 (=23)이

1 → 5 → 3 (=36), 2 → 5 → 3 (=32), 4 → 5 → 3 (=14), 7 → 5 → 3 (=22)으로 교체되었습니다.

 

k=6 일 때 입니다. 노드 6은 노드 7로만 연결되어 있기 때문에 노드 7이 갱신되지 않아 아직 대부분이 갱신되지 않았습니다.

 

행렬 D에 저장되어 있는 값에 따라 새롭게 추가 될 수 있는 경로는 1 → 6 → 7 입니다.

 

기존 최단 경로였던 1 → 5 → 7 (=30)이 1 → 6 → 7 (=20)으로 교체되었습니다.

 

k=7 일 때 입니다. 노드 7이 노드 6의 최단 경로를 찾아주는 모습입니다.

 

행렬 D에 저장되어 있는 값에 따라 새롭게 추가 될 수 있는 경로는

6 → 7 → 1, 6 → 7 → 2, 6 → 7 → 3, 6 → 7 → 4, 6 → 7 → 5입니다.

---

문제 2. 𝑝𝑖𝑗𝑘의 마지막 행렬을 이용하여 다음 2 가지 경우에 대한 경로를 풀이과정과 함께 제시하시오.

• 출발 : 𝑣1, 도착 : 𝑣5
• 출발 : 𝑣3, 도착 : 𝑣6

플로이드-와샬 알고리즘에서 배열 P는 해당 최단 경로로 가고 싶을 때 중간 정점이자 꼭 거쳐야 하는 정점을 저장해놓은 값입니다.

배열 P에 0이 저장되어 있다면 그 경로가 곧 최단 경로가 됩니다.

 

1.

출발이 v1, 도착이 v5라면 i=1, j=5이고,

P[1][5] = 4이므로 1 → 5로 가고 싶다면 4를 거쳐야합니다.

 

따라서 1 → 4를 구해보면,

P[1][4] = 2이므로 1 → 4로 가고 싶다면 2를 거쳐야합니다.

 

따라서 1 → 2, 2 → 4를 구해보면, P[1][2], P[2][4] = 0이므로,

1 → 4 까지 도달하기 위한 최단 경로는 1 → 2 → 4 입니다.

 

이제 중간 지점 4를 기준으로 앞의 경로를 구했으니 뒷 경로를 구해야합니다.

우리는 5를 도착지로 하고 싶으므로 4 → 5 를 구해야합니다.

P[4][5] = 0 이므로, 4 → 5 를 위한 최단 경로도 4 → 5 입니다.

 

따라서, 1 → 5 로 도달하기 위한 최단 경로는 1 → 2 → 4 → 5 입니다.

 

2. 

출발이 v3, 도착이 v6라면 i=3, j=6이고,

P[3][6] = 2이므로 3 → 6로 가고 싶다면 2를 거쳐야합니다.

 

따라서 3 → 2를 구해보면,

P[3][2] = 0이므로 3 → 2 를 위한 최단 경로도 3 → 2 입니다.

 

이제 중간 지점 2를 기준으로 앞의 경로를 구했으니 뒷 경로를 구해야합니다.

우리는 6을 도착지로 하고 싶으므로 2 → 6 을 구해야합니다.

P[2][6] = 1 이므로, 2 → 6 으로 가고 싶다면 1을 거쳐야합니다.

 

따라서 2 → 1, 1 → 6을 구해보면, P[2][1], P[1][6] = 0 이므로,

2 → 6 까지 도달하기 위한 최단 경로는 2 → 1 → 6 입니다.

 

따라서, 3 → 6 으로 도달하기 위한 최단 경로는 3 → 2 → 1 → 6 입니다.

---

floyd_warshall_adjacency_list = {
    '1': {'2': 4, '6': 10},
    '2': {'1': 3, '4': 18},
    '3': {'2': 6},
    '4': {'2': 5, '3': 15, '5': 2, '6': 19, '7': 5},
    '5': {'3': 12, '4': 1},
    '6': {'7': 10},
    '7': {'4': 8}
}

행렬을 제대로 그렸는지 확인하기 위해 지난번 작성한 코드에서 딕셔너리를 수정하여 컴파일해보았습니다.

출력 결과 직접 그려본 행렬을 통한 최단 경로와 코드의 결과가 일치함을 확인할 수 있었습니다.

---

결론

지난 시간 플로이드 와샬 알고리즘의 코드를 작성해보면서, 알고리즘의 원리에 대해 이해하였습니다.

이번 시간 그 알고리즘의 작동 원리를 그림을 통해 그려보면서 보다 자세하게 알고리즘의 작동 원리에 대해 이해하는 시간을 가질 수 있었습니다.

특히 직접 그림을 그리며 알고리즘의 작동 원리를 확인해보는게 훨씬 빠르고 쉽게 알고리즘을 이해할 수 있는 것 같습니다.

 

플로이드-와샬 알고리즘은 매우 간단한 코드를 가지고 있지만 이를 풀어내면 매우 복잡하다는 사실을 느꼈습니다.

특히 사람이 문제를 풀면 계산 실수가 너무 많은 것 같습니다...

알고리즘을 직접 그리면서 풀어보면 풀어볼 수록 알고리즘을 생각해내는 사람들은 머리가 정말 똑똑하다는 걸 느낍니다..