그래프 이론 - 4. 최소 비용 경로 알고리즘

 

4. 최소 비용 경로 알고리즘

4.1 다익스트라 알고리즘 (Dijkstra’s Algorithm)

📌 다익스트라의 제한 사항 및 주의할 점

⚠ 음수 가중치가 있는 그래프에서는 사용할 수 없음
⚠ 단일 출발점 기준 최단 경로만 계산 가능 (모든 정점 간 최단 경로를 원하면 플로이드-워셜 사용)

📌 추가된 예제 그래프

      (A)
     /   \
   4/     \2
   /       \
 (B)       (C)
   \       / \
   7\     /3 1
     \   /   \
      (D)    (E)
         \   /
          5/
         (F)

• A → B = 4, A → C = 2, B → D = 7, C → D = 3, C → E = 1, D → F = 5, E → F = 5
• 시작점 A에서 각 노드까지의 최단 경로를 구함

📌 변경된 다익스트라 알고리즘 예제 코드

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    previous = {node: None for node in graph}

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))

    return distances, previous

def reconstruct_path(previous, start, end):
    path = []
    while end:
        path.append(end)
        end = previous[end]
    return path[::-1] if path[-1] == start else []

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 7)],
    'C': [('D', 3), ('E', 1)],
    'D': [('F', 5)],
    'E': [('F', 5)],
    'F': []
}

distances, previous = dijkstra(graph, 'A')
print(f"최단 경로 (A → F): {reconstruct_path(previous, 'A', 'F')}")

📌 출력 결과:

최단 경로 (A → F): ['A', 'C', 'E', 'F']

---

4.2 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

📌 벨만-포드의 제한 사항 및 주의할 점

⚠ 𝑂(𝑁E)의 시간 복잡도를 가지므로 큰 그래프에서는 비효율적
⚠ 음수 가중치가 있는 경우에만 다익스트라보다 유리

📌 추가된 예제 그래프 (음수 가중치 포함)

      (A)
     /   \
   4/     \2
   /       \
 (B)       (C)
   \       / \
  -2\     /3 1
     \   /   \
      (D)    (E)
         \   /
        -3/
        (F)

• B → D = -2, E → F = -3 (음수 가중치 포함)

📌 변경된 벨만-포드 알고리즘 예제 코드

def bellman_ford(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous = {node: None for node in graph}

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node]:
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight
                    previous[neighbor] = node

    return distances, previous

distances, previous = bellman_ford(graph, 'A')
print(f"최단 경로 (A → F): {reconstruct_path(previous, 'A', 'F')}")

📌 출력 결과:

최단 경로 (A → F): ['A', 'C', 'E', 'F']

---

4.3 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

📌 플로이드-워셜의 제한 사항 및 주의할 점

⚠ 𝑂(𝑁³)의 시간 복잡도를 가지므로 정점 개수가 많으면 비효율적
⚠ 모든 정점 간 최단 경로를 한꺼번에 계산하는 경우에 적합

📌 변경된 플로이드-워셜 알고리즘 예제 코드

def floyd_warshall(graph):
    nodes = list(graph.keys())
    n = len(nodes)
    INF = float('inf')

    dist = {i: {j: INF for j in nodes} for i in nodes}
    next_node = {i: {j: None for j in nodes} for i in nodes}

    for node in nodes:
        dist[node][node] = 0
        for neighbor, weight in graph[node]:
            dist[node][neighbor] = weight
            next_node[node][neighbor] = neighbor

    for k in nodes:
        for i in nodes:
            for j in nodes:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_node[i][j] = next_node[i][k]

    return dist, next_node

dist, next_node = floyd_warshall(graph)
print(f"최단 경로 (A → F): {reconstruct_floyd_path(next_node, 'A', 'F')}")

---

🚀 알고리즘 실행 시간 비교 (벤치마크)

import time

# 벤치마크용 그래프 (정점 100개, 간선 500개)
import random
random.seed(42)

N = 100
graph_large = {str(i): [] for i in range(N)}
for _ in range(500):
    u, v = random.randint(0, N-1), random.randint(0, N-1)
    weight = random.randint(1, 10)
    graph_large[str(u)].append((str(v), weight))

# 실행 시간 측정
start = time.time()
dijkstra(graph_large, '0')
print(f"다익스트라 실행 시간: {time.time() - start:.6f}초")

start = time.time()
bellman_ford(graph_large, '0')
print(f"벨만-포드 실행 시간: {time.time() - start:.6f}초")

start = time.time()
floyd_warshall(graph_large)
print(f"플로이드-워셜 실행 시간: {time.time() - start:.6f}초")

📌 예상 출력 결과

다익스트라 실행 시간: 0.005초
벨만-포드 실행 시간: 0.150초
플로이드-워셜 실행 시간: 4.500초