[최단거리] 벨만 포드

☝🏻 양수 , 음수 가중치가 존재하는 최단 거리

☝🏻 단일 출발 - 모든 도착 : 단일 정점 v에서 출발 → 나머지 모든 정점에 도착하는 최단 경로

☝🏻 모든 출발 - 단일 도착 : 모든 정점에서 출발 → 단일 정점 v로 도착하는 최단 경로 (그래프 내 간선 뒤집으면 단일출발-모든도착 문제랑 똑같다.)

☝🏻단일 쌍 : 단일 정점 v 출발 → 다른 정점 v’로 가는 최단 경로

☝🏻 다익스트라와 같이 `단일 출발 - 모든 도착`, `모든 출발 - 단일 도착`, `단일 쌍`과 같은 상황을 커버하지만 음수 가중치까지 커버할 수 있는 것이 벨만포드 특!

☝🏻 음의 사이클 감지 목적으로 사용 가능: 최단 경로를 찾는 것 말고도 음의 사이클이 있는지 확인할 때 good

벨만 포드 특징

• 용도: 단일 출발점에서 모든 정점까지의 최단 경로를 찾는 알고리즘
• 그래프 유형: 음의 가중치를 허용하며, 음의 사이클도 감지할 수 있음
• 장점: 음의 가중치가 있는 그래프에서도 동작하며, 음의 사이클을 감지할 수 있음
• 단점: 시간 복잡도가 다익스트라 알고리즘보다 높음. So, 음수 가중치 상황에서는 SPFA 알고리즘이 더 효율적 !!

알고리즘

시간 복잡도 O(VE)
: 모든 간선에 대해 V-1번 반복하면서 최단거리를 갱신하는 핵심 알골 파트가 시간 복잡도에 영향을 미치고, 이는 O(VE)이다.

for _ in range(n - 1): # O(V-1)
    for u, v, w in edges: # O(E)
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

 아이디어
: 그래프의 모든 간선을 반복적으로 검사해서 최단거리를 갱신한다. 노드 V개에 대해 V-1번의 반복을 한 후에도 거리가 갱신되면, 음의 사이클이 존재한다고 판단할 수 있다.

 

1. 최단거리 배열 초기화

• dist = [int(1e9)]*n
• 출발 지점의 dist는 0으로 초기화

dist = [int(1e9)] * n
dist[start] = 0

2. 모든 간선에 대해 반복적으로 최단 거리 갱신

• 모든 간선을 V-1 번 반복하면서 최단거리를 갱신한다.
  • 왜 V-1번 반복하죠??
    • 최단 경로는 최대 V-1개의 간선을 포함하기 때문이다.
    • : 그래프에 V개의 정점이 있다면 두 정점 사이의 최단 경로에는 최대 V-1개의 간선을 모두 거쳐가는 경우가 존재한다.
    • 그래서 모든 정점에 대해 V-1번 반복하면 최단 경로를 보장할 수 있다.
  • 거리 갱신 기준은 뭐죠??
    1. dist[u] != int(1e9) 이고 !!: 유효하지 않으면(=int(1e9)) v까지 가는 경로를 계산할 필요가 없다. 불필요 한 연산을 하지 말자
    2. : (시작노드,도착노드,가중치) = (u,v,w) 일 때, v 노드 최단 거리를 갱신하기 위해서라면 u까지의 거리가 유효해야 한다. 그래야 계산해서 뭐 어찌하든 하지 !!
    3. dist[u] + weight < dist[v]이면
    4. ⇒ dist[v]를 갱신합니다. 이는 시작 정점에서 u를 거쳐 v로 가는 경로가 더 짧다면, 이를 반영하는 것이다.

for _ in range(n - 1):
    for u, v, w in edges:
        if dist[u] != int(1e9) and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

3. 음의 사이클 존재 판단하기

• V-1번 반복 후에도 거리가 갱신이 된다면, 이것은 음의 사이클이 존재한다는 것을 의미한다. (왜냐면, 음의 사이클은 돌면서 끝없이 최단 거리를 줄일 수 있게 되기 때문이다.)
• 최단 거리 갱신할 수 있는지 판단하는 로직과 동일하다. 이미 최단 거리를 구하는 벨만포드 실행을 모두 끝난 후에 !!!! 이 음의 사이클 존재 판단 로직을 돌리는 것이기 때문에, 여기서 if문을 통과한다는 것은 !!! 또 다른 최단 거리가 존재할 수 있다는 의미이고 = 이는 즉, 음의 사이클이 있다는 의미이다 !!!

for u, v, w in edges:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        print("Graph contains a negative weight cycle")
        return None

구현

def bellman_ford(n, edges, start):
    # 거리 테이블 초기화
    dist = [float('inf')] * n
    dist[start] = 0

    # 벨만 포드 알고리즘
    for i in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # 음의 사이클 검출
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            print("Graph contains a negative weight cycle")
            return None

    return dist

# 예제 그래프
n = 5
edges = [
    (0, 1, -1),
    (0, 2, 4),
    (1, 2, 3),
    (1, 3, 2),
    (1, 4, 2),
    (3, 2, 5),
    (3, 1, 1),
    (4, 3, -3)
]

start = 0
distances = bellman_ford(n, edges, start)
if distances:
    print(distances)

SPFA 알고리즘 특징

• SPFA(Shortest Path Faster Algorithm)
• 벨만 포드 알고리즘의 개선된 버전으로, 일반적인 경우에 더 빠르게 작동하는 단일 출발점 최단 경로 알고리즘
• SPFA 알고리즘은 음수 가중치를 처리할 수 있으며, 음의 사이클도 감지할 수 있다.
• 큐를 사용한 최적화:
  • 벨만 포드 알고리즘은 모든 간선을 매 반복마다 검사하지만, SPFA 알고리즘은 큐를 사용하여 갱신이 필요한 정점만 큐에 넣고, 큐에서 꺼내서 그 정점과 연결된 간선들만 검사하기에 더 효율적이다.
• 중복 검사를 줄임:
  • 벨만 포드 처럼 매번 V-1번 검사하는 것이 아니라, queue를 사용해서 큐에서 꺼낸 정점과 연결된 간선만 확인하기 때문에 갱신이 필요하지 않은 정점을 불필요하게 검사하는 것을 방지한다.
• 음의 사이클 감지:
  • 각 정점이 큐에 몇 번 들어갔는지를 기록하여 음의 사이클을 감지한다.

알고리즘

시간복잡도 O(VE)

: 최악의 경우 O(VE)이지만, 평균적으로는 훨씬 빠르게 작동한다. 큐를 사용하여 갱신이 필요한 노드만 처리하기 때문에, 실제 수행 시간이 벨만 포드 알고리즘보다 훨씬 낮다.

1. 최단거리 배열 초기화

dist = [int(1e9)] * n
dist[start] = 0

2. 큐 초기화, 음의 사이클 탐지를 위한 count 초기화

• 시작 노드를 큐에 추가하고,
• n개에 노드에 대해 다 queue에 없다고 False로 초기화 하고
• 시작 노드는 queue에 있다고 True 만들어주기

from collections import deque

queue = deque([start])
in_queue = [False] * n
in_queue[start] = True

count = [0] * n # 음의 사이클 감지를 위한 count 배열 최고하

3. 큐를 사용한 최단 거리 갱신

• 큐에서 노드를 하나씩 꺼낸다. 꺼냈으면 in_queue[]=False 처리
• 그 노드과 연결된 모든 간선을 검사한다.
• 각 간선을 통해 최단 거리가 갱신 되면 해당 노드를 큐에 append & in_queue=True

while queue:
    u = queue.popleft()  # 큐에서 정점을 하나 꺼냄
    in_queue[u] = False  # 큐에 더 이상 이 정점이 없음을 표시

    for v, w in edges[u]:  # 정점 u와 연결된 모든 간선 검사
      if dist[u] + w < dist[v]:  # 최단 거리 갱신 조건
          dist[v] = dist[u] + w  # 최단 거리 갱신
          if not in_queue[v]:  # 정점 v가 큐에 없다면
              queue.append(v)  # 큐에 추가
              in_queue[v] = True  # 큐에 추가되었음을 표시

4. 음의 사이클 감지

• 각 노드가 큐에 몇 번 들어갔는지를 기록하여, 노드가 V번 이상 큐에 들어가면 음의 사이클이 존재한다고 판단한다.
  • 왜냐하면, 최대 V번 이상 큐에 들어갔다는 것은, 해당 노드의 최단 거리가 V-1번 이상의 갱신 과정을 거쳤다는 뜻이기 때문이다.
    • 아하 큐에 들어가면 들어간 횟수가 +1 이고, 큐에 넣은 다음에 음의 사이클 감지를 하고 있기 때문에 V이구나???

# queue에 append한 이후에 아래 로직 수행

if in_queue[v]:
    count[v] += 1
    if count[v] >= n:  # 음의 사이클 감지
        print("Graph contains a negative weight cycle")
        return None

구현

from collections import deque

def spfa(n, edges, start):
    dist = [float('inf')] * n
    in_queue = [False] * n
    count = [0] * n
    count[start] = 1

    dist[start] = 0
    queue = deque([start])
    in_queue[start] = True

    while queue:
        u = queue.popleft()
        in_queue[u] = False # queue에 없습니당

        for v, w in edges[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True # queue에 있습니당

                    # 음의 사이클 계산을 위한 코드
                    count[v] += 1
                    if count[v] > n-1:  # 음의 사이클 감지
                        print("Graph contains a negative weight cycle")
                        return None

    return dist

# 예제 그래프
n = 5
edges = {
    0: [(1, -1), (2, 4)],
    1: [(2, 3), (3, 2), (4, 2)],
    2: [],
    3: [(2, 5), (1, 1)],
    4: [(3, -3)]
}

start = 0
distances = spfa(n, edges, start)
if distances:
    print(distances)

이런 그래프에서 특히 좋습니당

1. 희소 그래프(Sparse Graph):

• 정점의 수에 비해 간선의 수가 적은 그래프.
• SPFA 알고리즘은 거리 갱신이 필요한 정점만 큐에 넣어 처리하므로, 전체 간선을 반복적으로 검사하지 않아서 효율적입니다.
• 희소 그래프/밀집 그래프 판단 수식
  • 희소 그래프:
    • 간선의 수 E가 정점의 수 V에 비해 상대적으로 적은 그래프.
    • 일반적으로 E≤O(VlogV) 또는 E≈O(V)로 간주됩니다. (V=1000, E=2000)
  • 밀집 그래프:
    • 간선의 수 E가 정점의 수 V에 비해 상대적으로 많은 그래프.
    • 일반적으로 E≈O(V^2)로 간주됩니다.
  • 희소 그래프:
    • 인접 리스트(Adjacency List)를 사용하면 공간 효율적입니다.
    • 최단 경로 알고리즘에서 다익스트라(Dijkstra) 알고리즘을 사용할 때도 힙을 사용하여 효율성을 높일 수 있습니다.
    • SPFA 알고리즘이 효율적으로 작동할 수 있습니다.
  • 밀집 그래프:
    • 인접 행렬(Adjacency Matrix)를 사용하면 공간 효율적입니다.
    • 플로이드-워셜(Floyd-Warshall) 알고리즘이 적합할 수 있습니다.

2. 거리가 자주 갱신 되지 않는 그래프:

• 거리 갱신이 빈번하지 않은 그래프.
• 큐에 추가되는 정점의 수가 적어져 불필요한 연산이 줄어들고, 효율적으로 최단 경로를 찾을 수 있습니다.

3. 양의 가중치와 음의 가중치가 섞인 그래프:

• 양의 가중치와 음의 가중치를 모두 포함하는 그래프.
• SPFA 알고리즘은 큐를 사용하여 필요한 간선만 처리하므로, 다양한 가중치가 섞인 그래프에서도 상대적으로 빠르게 최단 경로를 찾을 수 있습니다.

4. 음의 사이클이 없는 그래프:

• 음의 사이클이 존재하지 않는 그래프.
• 음의 사이클이 없는 경우 SPFA는 더 빠르게 최단 경로를 수렴할 수 있습니다.
• 음의 사이클이 있는 경우에도 감지할 수 있지만, 음의 사이클이 없는 경우에 더 효율적입니다.