최단 거리는 두 지점 사이의 가장 짧은 경로를 찾는 문제입니다. 그래프에서 각 간선 또는 엣지에 가중치가 부여되어 있을 때, 최단 거리를 찾는 문제는 너비 우선 탐색(BFS), 다익스트라 알고리즘, 벨만-포드 알고리즘 등을 사용하여 해결할 수 있습니다.

최단 거리 문제의 주요 특징:

  1. 가중치: 그래프의 간선에 가중치가 부여되어 있는 경우, 최단 거리는 간선의 가중치의 합으로 정의됩니다.
  2. 단일 출발점 또는 모든 쌍: 최단 거리 문제는 한 정점에서 다른 정점까지의 최단 거리를 구하는 단일 출발점 문제와, 모든 정점 쌍 간의 최단 거리를 구하는 모든 쌍 문제로 나뉩니다.
  3. 음의 가중치: 음의 가중치가 있는 경우, 벨만-포드 알고리즘을 사용하여 최단 거리를 찾을 수 있습니다.
  4. 양의 가중치: 양의 가중치가 있는 경우, 다익스트라 알고리즘을 사용하여 최단 거리를 찾을 수 있습니다.

최단 거리의 활용 예시:

파이썬 코드를 통해 최단 거리 알고리즘을 예시로 살펴보겠습니다. 다음은 그래프에서 다익스트라 알고리즘을 사용하여 단일 출발점에서 모든 정점까지의 최단 거리를 구하는 코드입니다.

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 그래프의 인접 리스트 표현
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_vertex = 'A'
shortest_distances = dijkstra(graph, start_vertex)
print("출발점", start_vertex, "에서의 최단 거리:")
for vertex, distance in shortest_distances.items():
    print(f"{vertex}: {distance}")

이 코드는 그래프에서 다익스트라 알고리즘을 사용하여 단일 출발점에서 모든 정점까지의 최단 거리를 구하는 예시입니다. 우선순위 큐(Heap)를 사용하여 각 정점까지의 최단 거리를 업데이트하며 찾습니다.

벨만-포드 알고리즘은 음수 가중치를 포함하는 그래프에서 최단 경로를 찾는 알고리즘입니다. 다익스트라 알고리즘이 음수 가중치를 다루지 못하는 상황에서도 사용할 수 있는 알고리즘이며, 음수 가중치 사이클이 없는 경우에 사용됩니다.

알고리즘의 주요 아이디어는 다음과 같습니다:

  1. 출발 노드의 최단 거리를 0으로 설정하고, 다른 모든 노드의 최단 거리를 무한대로 초기화합니다.
  2. 모든 간선에 대해서 출발 노드에서 도착 노드까지의 거리를 갱신합니다. 이때, 이전 노드의 최단 거리와 현재 간선의 가중치를 더한 값과 비교하여 갱신합니다.
  3. 음수 가중치 사이클을 탐지하는 추가 단계를 수행합니다. 만약 음수 가중치 사이클이 존재한다면, 최단 경로는 무한대로 발산할 것입니다.

벨만-포드 알고리즘의 시간 복잡도는 O(V * E)로, 다익스트라 알고리즘보다 더 높은 복잡도를 가지지만 음수 가중치를 처리할 수 있는 장점이 있습니다.