다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall)

다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로 구하는 알고리즘

플로이드 와샬 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

둘 다 최단 경로 비교라는 공통점이 존재하지마니

용도, 구현 방식, 시간 복잡도 등에 차이가 난다

다익스트라 알고리즘

개념

하나의 시작 정점에서 다른 모든 정점까지의 최단 경로…

생각해보면 알겠지만 GPS다

양의 가중치만을 허용하며, 가장 가까운 노드부터 순서대로 거리 정보를 갱신한다

시간 복잡도 : $O((V + E) log V)$       (우선 순위 큐 사용시)

그리디 방식이라 음수 넣으면 최단 경로 보장 못함;;

예제

🔷 그래프

             # 간선 정보 (A~D)
    [A]        
 1 / | \       # A-B: 1
  /  | 2\      # A-C: 2
 /  4|   \     # A-D: 4
[B]--3--[C]    # B-C: 3
1\   |   /     # B-D: 1
  \  |  /5     # C-D: 5
    [D]        

🔷 목표

• 시작점 : A
• A에서 모든 점정까지의 최단거리
  
  

🔷 초기 설정

distance = {
    A: 0,     # 시작점은 0
    B: ∞,
    C: ∞,
    D: ∞
}
visited = {
    A: False,
    B: False,
    C: False,
    D: False
}

단계별 수행

🔷 시작점 선택

• 현재 거리: A = 시작점 = 0
• A의 인접 노드:B(1), C(2), D(4)
• 갱신 :

    B: min(∞, 0+1) = 1
    C: min(∞, 0+2) = 2
    D: min(∞, 0+4) = 4
  

  # 현상태
  distance = { A: 0, B: 1, C: 2, D: 4 }
  visited =  { A: ✅, B: ❌, C: ❌, D: ❌ }
  

🔷 가장 가까운 노드 선택

• 현재 가장 가까운 노드 = B = 1
• B의 인접 노드: C(3), D(1)
• 갱신:

    C: min(2, 1+3) = 2 (변화 없음)
    D: min(4, 1+1) = 2 (더 짧아짐)
  

  # 현상태
  distance = { A: 0, B: 1, C: 2, D: 2 }
  visited =  { A: ✅, B: ✅, C: ❌, D: ❌ }
  

🔷 가장 가까운 노드 선택

• 현재 가장 가까운 노드 = C = 2
• C의 인접 노드: D(5)
• 갱신:

    D: min(2, 2+5) = 2 (변화 없음)
  

  # 현상태
  distance = { A: 0, B: 1, C: 2, D: 2 }
  visited =  { A: ✅, B: ✅, C: ❌, D: ❌ }
  

🔷 마지막으로 D 방문

• 모든 노드 방문시 완료

최종 결과

A → A = 0
A → B = 1
A → C = 2
A → D = 2

플로이드 와샬

혹은 플로이드 워샬

개념

모든 정점 쌍 사이의 최단 거리를 구한다

중간에 거쳐갈 수 있는 모든 정점을 하나씩 고려하며 갱신하는는 느낌’s~
(Dynamic Programming)

핵심 아이디어는

정접 i에서 j로가는 최단 경로 중
k를 거쳐가는 것이 더 빠르면 i → k → j로 갱신

예시)

distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

얘는 음수 가중치도 가능하다

단, 음수 사이클은 없어야 한다

음수 사이클 판별도 가능

시간 복잡도는 $O(V^3)$이다 (3중 for문)

예제

🔶 그래프

       [0]
    ↙     ↘
   4         5
   ↓         ↓
  [1] → 2 → [2]
   ↑ ↘      ↓
   1    1    3
    ↖  ↓  ↙
       [3]

🔶 거리 행렬 초기화

우선 거리행렬 (2차원 배열)로 초기화 한다

dist[i][j] = i에서 j로 가는 최소 거리
            (처음엔 직통 거리 또는 INF)

초기상태

• 직통 불가시 INF로 표현 ___

🔶 각 정점을 경유지(k)로 삼아 갱신

모든 정점 k를 거쳐가며
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 수행

3중 for문 구조:

# py

for k in range(V):
    for i in range(V):
        for j in range(V):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

🔶 단계별 결과

🔸K = 0 (0을 거쳐가는 경우)

• 가능한 갱신 경로:

  • 없음 (0으로 가는 입력 간선 ❌)

🔸K = 1 (1을 거쳐가는 경우)

• 갱신된 경로:

  • 0 → 3: 0→1→3 = 4 + 1 = 5
    (기존 INF)

  • 3 → 2: 3→1→2 = 1 + 2 = 3
    (기존 INF)

🔸K = 2 (2를 거쳐가는 경우)

• 갱신된 경로:

  • 0 → 3: 0→2→3 = 5 + 3 = 8
    기존 5 가 더 짧음 → 변화 없음

  • 1 → 3: 1→2→3 = 2 + 3 = 5
    기존 1 이 더 짧음 → 변화 없음

🔸K = 3 (3을 거쳐가는 경우)

• 갱신된 경로:

  • 2 → 1: 2→3→1 = 3 + 1 = 4
    (기존 INF)

  • 나머지 경로는 변화 없음

• 위 표가 최종 행렬이다

• 최종 행렬은 “모든 정점 쌍 간 최단 거리” 를 나타내며,
  특정 노드에서 다른 노드까지의 최소 이동 비용을 한눈에 파악할 수 있습니다.

🔶 추가 정보

🔸 음수 사이클 파악법

• 사이클이 음수인 경우를 파악해야 한다

• 무시하고 냅둘 경우 무한히 순회하며 비용이 무한히 줄어들어 최단 거리의 의미가 없어진다

의외로 탐지 방법은 쉽다

알고리즘 종료 후 dist[i][i] < 0인 정접이 존재시
=> 음수 사이클 존재

자기 자신으로 돌아오는 사이클 비용이 음수라는 뜻임

• 코드 예시:

  for i in range(V):
    if dist[i][i] < 0:
        print("음수 사이클 존재")
  

  ---

🔸 경로 복원

• 거리 말고도 어떤 경로로 이동했는지 알고 싶을때

• 방법 :

  • 거리 갱신 사이에 중간 경유지 따로 저장

① path 배열 생성

next = [[None] * V for _ in range(V)]

② 초기화

for u, v, w in edges:
    dist[u][v] = w
    next[u][v] = v  # 직접 갈 수 있는 경우는 다음 노드를 바로 기록

③ 갱신할 때 중간 경유지 저장

if dist[i][j] > dist[i][k] + dist[k][j]:
    dist[i][j] = dist[i][k] + dist[k][j]
    next[i][j] = next[i][k]  # i→j로 가려면, 일단 i→k로 간 뒤 계속 따라감

🔸 경로 복원 함수 예시

def get_path(u, v):
    if next[u][v] is None:
        return []  # 경로가 없으면 빈 리스트 반환

    path = [u]      # 출발 정점을 먼저 경로에 넣고
    while u != v:   # 도착 정점에 도달할 때까지
        u = next[u][v]   # 다음 정점으로 이동
        path.append(u)   # 이동한 정점을 경로에 추가
    return path

• 예시 : get_path(2,1) (2 → 3 → 1 이라는 가정)
  • 출력 : [2, 3, 1]