보통 많이 사용하는 그래프 탐색 알고리즘은 다익스트라가 있죠?

그런데 다익스트라는 음수 가중치가 있을 때 사용하지 못합니다… 왜냐! 보통 작은 값들로 업데이트하는데 음수가 들어가버리면 무한 사이클이 발생하니까요.. 이런 그리디한 특성 때문에 처리가 안되는데 벨만-포드는 그걸 처리할 수 있다니까요?!

그래서 벨만-포드가 뭐냐!

벨만-포드 알고리즘#

가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘!

기본적인 아이디어

1. 출발 정점의 거리를 0으로 초기화
2. 다른 모든 정점까지의 거리를 무한대로 초기화
3. 모든 간선에 대해 완화(relaxation) 작업을 수행하는 과정을 (정점 수 - 1)번 반복
4. 음수 사이클 검사를 위해 한 번 더 모든 간선을 확인

완화(Relaxation) 연산#

완화 연산은 벨만-포드 알고리즘의 핵심 작업입니다. 정점 u에서 정점 v로 가는 간선 (u, v)의 가중치가 w일 때…

if distance[u] + w < distance[v] then
distance[v] = distance[u] + w
predecessor[v] = u

이 연산은 “정점 u를 경유하여 정점 v로 가는 경로가 현재까지 알려진 v까지의 최단 경로보다 짧다면, 최단 경로를 갱신한다”라는 의미!

그럼 중요한 것들을 알아보죠!

시간 복잡도 및 공간 복잡도#

시간 복잡도#

• 최악의 경우: O(VE)
• 초기화: O(V)
• 완화 작업: O(VE) (V-1번 반복하면서 각 반복마다 E개의 간선 검사)
• 음수 사이클 검사: O(E)

공간 복잡도#

• O(V + E)
  • 거리 배열과 선행자 배열: O(V)
  • 그래프 표현: O(E)

비교해볼까? with Dijkstra#

그러면 약간 효율이 안 좋아보이긴 합니다.. 그죠? 그래서 최적화 기법들이 여럿 있는데요!

일단 제일 유명한 것들부터 알아봅시다.

1. SPFA(Shortest Path Faster Algorithm)#

벨만-포드의 변형으로, 큐를 사용하여 완화될 필요가 있는 정점만 처리합니다.

이거는 사실 찾아보면서 알게된 것인데.. 이게 따로 이름이 있었네요..?

from collections import deque

def spfa(graph, source):
    distance = {vertex: float('infinity') for vertex in graph}
    predecessor = {vertex: None for vertex in graph}
    distance[source] = 0
    
    queue = deque([source])
    in_queue = {vertex: False for vertex in graph}
    in_queue[source] = True
    
    while queue:
        u = queue.popleft()
        in_queue[u] = False
        
        for v, weight in graph[u]:
            if distance[u] + weight < distance[v]:
                distance[v] = distance[u] + weight
                predecessor[v] = u
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
    
    # 음수 사이클 검사 부분 생략...
    
    return distance, predecessor

2. 조기 종료(Early Stop)#

음.. 무슨 인공지능 학습도 아니고.. ㅋㅋ 그냥 이거는 코드 짜다보면 보이니까 굳이 따로 보진 않겠습니다. 아마 코드를 작성하다보면 당연히 짜게 되실테니..

그러면 좀 질문해볼만한 것들을 해볼까요??

조금 더 깊게..#

Q1: 벨만-포드 알고리즘의 (정점 수 - 1)번 반복이 필요한 이유는 무엇인가요?#

A: 최악의 경우, 한 정점에서 다른 정점으로 가는 최단 경로는 최대 (정점 수 - 1)개의 간선을 포함할 수 있습니다. 각 반복마다 최소한 하나의 정점에 대한 최단 경로가 확정되므로, (정점 수 - 1)번의 반복 후에는 모든 최단 경로가 확정됩니다.#

Q2: SPFA는 항상 벨만-포드보다 빠른가요?#

A: 평균적으로는 SPFA가 더 빠르지만, 최악의 경우에는 여전히 O(VE)의 시간 복잡도를 가집니다. 특정한 그래프 구조에서는 오히려 더 느릴 수도 있습니다. 물론!? 대부분 사용하는게 좋겠죠..? 최적화를 위해서는 말이죠#

연습 문제를 떨구고 가겠습니다.

웜홀 이거 한번 츄라이 츄라이#