플로이드 워셜 Floyd-Warshall 알고리즘

" 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 "

- 다익스트라 알고리즘과 비교하면 구현 과정에서 어렵진 않음

- 다만, 핵심 아이디어를 이해하는 것이 중요

그래프의 정보를 2차원 행렬(배열)을 이용하여 3중 루프를 반복하여 구성된 최단 경로 알고리즘

 

다익스트라(Greedy) VS 플로이드 워셜(Dynaminc)

<다익스트라 알고리즘>

https://cord-ai.tistory.com/165

최단경로 Shortest Path

- 단계마다 최단 거리를 가지는 노드를 반복적으로 선택

- 그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작

- 출발 노드가 1개이므로 다른 모든 노드까지의 "최단 거리"를 저장하기 위해 1차원 리스트 이용

= 인접 리스트 방식, Greedy

= 노드의 개수가 많을때

 

<플로이드 워셜 알고리즘>

- 시간 복잡도 O(N³)

- 단계마다 "거처 가는 노드"를 기준으로 수행 

- 하지만 " 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다 "는 점이 다르다.

노드의 개수가 N개일 때, 알고리즘상으로 N의 단계를 수행하며, 단계마다 O(N²)의 연산을 통해
" 현재 노드를 거쳐 가는 " 모든 경로를 고려한다.
= 2 → 3은 2 → 1 → 3과 같다(= 2 → 1, 1 → 3)
따라서 플로이드 워셜 알고리즘의 총시간 복잡도는 O(N³)이다

- 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문에 2차원 리스트에 "최단 거리" 저장

- 다시 말해 2차원 리스트를 처리해야 하므로 N번의 단계에서 매번 O(N²)의 시간이 소요된다.

= 인접 행렬 방식, Dynamic Programming 

= 노드의 개수가 적을때

why???

노드의 개수가 N이라고 할 때, N번 만큼의 단계를 반복하며 " 점화식에 맞게 " 2차원 리스트를 갱신하기 때문

<점화식>

1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면된다.

= 정확히는 A → 1번 노드 → B로 가는 비용을 확인한 후에 최단 거리를 갱신한다.

= 현재 최단 거리 테이블에 A번 노드를 거쳐 B번 노드로 이동하는 비용이 2라는 것이 밝혀지면, A번 노드에서 B번 노드로 이동하는 비용을 2로 갱신하는 것이다.

 

따라서 알고리즘에서는 현재 확인하고 있는 노드를 제외하고, N - 1개의 노드 중에서 서로 다른 노드 (A, B)쌍을 선택한다. 이후에 A → 1번 노드 → B로 가는 비용을 확인한 뒤에서 최단 거리를 갱신한다.
다시 말해, $$_{n-1}{P}_2개$$의 쌍을 단계마다 반복해서 확인하면 된다.
이때 $$O(_{n-1}{P}_2)$$는 O(N²)이라고 볼 수 있기 때문에, 전체 시간 복잡도는 O(N³)이라고 할 수 있다. 
구체적인 (K번의 단계에 대한) 점화식은 다음과 같다.
$$D_{ab} = min(D_ab, D_ak + D_kb)$$

= "A에서 B로 가는 최소 비용"과 "A에서 K를 거쳐 B로 가는 비용"을 비교하여 더 작은 값으로 갱신하겠다

따라서 전체적으로 3중 반복문을 이용하여 이 점화식에 따라 최단 거리 테이블을 갱신하면 된다.

 

" 바로 이동하는 거리 "가 " 특정한 노드를 거쳐서 이동하는 거리 "보다 더 많은 비용을 가진다면
이를 더 짧은 것으로 갱신한다는 것이다.

 

<구현>

각 노드를 거쳐갔을 때의 경우를 확인하고 값을 갱신

1번 노드를 거쳐가는 경우 확인(= 6개만 확인하면 됨)

왜 6개만 확인하면 되냐???
<갱신 일어나지 않는 부분>
1. 자기 자신에서 자기 자신으로 가는 비용은 0(= 대각선) 
2. ex 1번 노드를 거쳐가는 경우 해당 노드를 거쳐 가는 곳은 갱신이 일어나지 않음

 

## 초기 테이블 설정
# 1. [step 0]에서는 "연결된 간선"은 단순히 그 값을 채워 넣고, 연결되지 않은 간선은 "무한" 이라는 값을 넣는다
# "무한" = int(1e9)
# 2차원 리스트에서 각 값에 해당하는 Dab는 "a에서 b로 가는 최단 거리"

# 2. 자기 자신에서 자기 자신으로 가는 비용은 0이므로, (1 <= i <= n)의 범위를 가지는 모든 i에 대하여 Dii는 0으로 초기화
# 즉, 왼쪽 위에서 오른쪽 아래로 내려가는 대각선에 놓인 모든 원소는 0이다

'''
4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2

0 4 8 6
3 0 7 9
5 9 0 4
7 11 2 0
'''

import sys
import numpy as np

input = sys.stdin.readline
INF = int(1e9)

# 노드 개수
n = int(input())

# 간선 개수
m = int(input())

# 무한으로 초기화(= 2차원 리스트, 행렬)
graph = [[INF]*(n+1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용 0으로 초기화
# for i in range(1, len(graph)):
#     graph[i][i] = 0

for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

print(np.array(graph))


# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화    
for _ in range(m):
    a, b, c = map(int, input().split())

    # A에서 B로 가는 비용은 C
    graph[a][b] = c

# K번의 단계에 대한
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

print(np.array(graph))

for a in range(1, n+1):
    # 해당 코드는 각 노드에 접근할 수 없음
    # for j in range(n):
    #     print(graph[a][1:][j], end= " ")
    # print()
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print("무한", end= " ")

        else:
            print(graph[a][b], end= " ")
    print()

 

<수식 입력기>

# HTML

<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=alwaysneoi&logNo=220698343806 

[한글 수식 입력] 한글 수식편집기 사용매뉴얼