Dijkstra's Algorithm, Floyd-Warshall Algorithm

다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프 내에서 두 노드 사이의 최단 경로를 찾는 알고리즘이다. 주로 네트워크 라우팅 프로토콜, 지도의 경로 탐색 등에 활용된다. 이 알고리즘은 음의 가중치를 갖지 않는 그래프에 적용된다.

 

다익스트라 알고리즘은 시작 노드 설정 후, 시작 노드로부터 각 노드까지의 거리(가중치)를 저장하는 배열을 무한대로 초기화한다. 시작 노드의 거리는 0으로 설정하고, 방문하지 않은 노드 중 시작 노드로부터 가장 가까운 노드를 선택한다. 그리고 선택한 노드를 경유지로 하여 갈 수 있는 다른 노드들까지의 거리를 계싼하고, 기존에 저장된 거리보다 짧을 경우 갱신한다. 모든 노드를 방문할 때 까지 이 과정을 반복하면 시작 노드로부터 각 노드까지의 최단 거리가 계산된다.

 

다익스트라 알고리즘은 그리디 알고리즘을 적용하여 매 선택에서 지역적으로 최적인 해를 선택해 나가는 방식으로, 전체적으로 최적의 해를 찾는다.

 

음의 가중치가 있을 경우, 알고리즘은 정확한 결과를 보장할 수 없다.

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])

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

        if distances[current_node] < current_distance:
            continue

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

            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])

    return distances

# 그래프 예시
graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

start_node = 'A'
print(dijkstra(graph, start_node))

#출력 결과
{'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

 

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 쌍 최단 경로 문제를 해결하는 알고리즘이다. 이 문제는 주어진 가중치 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 것이 목표이다. 플로이드-워셜 알고리즘은 동적 프로그래밍을 기반으로 한다.

 

알고리즘의 기본 아이디어는 각 단계마다 '경유점'을 하나씩 추가하며, 이 경유점을 통해 갈 수 있는 모든 정점 쌍의 최단 거리를 업데이트하는 것이다. 여기서 '경유점'이란 특정 정점을 거쳐 가는 경로를 말한다.

 

최단 거리 정보를 저장할 2차원 배열 D를 준비한다. D[i][j]는 정점 i에서 j로 가는 직접 경로의 가중치를 나타낸다. 직접 경로가 존재하지 않는 경우, 해당 값은 무한대로 설정한다. 자기 자신으로 가는 경로의 가중치는 0으로 설정한다.

 

각 정점을 경유점으로 고려: 모든 정점 쌍 (i, j)에 대해서, 가능한 모든 경유점 k에 대하여 D[i][k] + D[k][j]의 값을 계산하고, 이 값이 D[i][j]보다 작은 경우 D[i][j]를 D[i][k] + D[k][j]로 업데이트한다. 그리고 모든 정점을 경유점으로 고려한 후, 배열 D에는 모든 정점 쌍 사이의 최단 경로의 가중치가 저장된다.

 

시간 복잡도는 O(N^3)이며, 여기서 N은 그래프의 정점 수이다. 음의 가중치가 있는 그래프에서도 사용할 수 있다. 단, 그래프에 음의 사이클이 있으면 안 된다. 동적 프로그래밍 방식을 사용하여 문제를 해결한다.

# 무한대를 의미하는 값으로 초기화한다. 실제 사용에서는 충분히 큰 수를 사용한다.
INF = float('inf')

# 그래프의 가중치를 나타내는 2차원 리스트. graph[i][j]는 정점 i에서 j로 가는 가중치를 의미한다.
# 직접 연결이 없는 경우 INF로 설정한다.
graph = [
    [0, 3, INF, 5],
    [2, 0, INF, 4],
    [INF, 1, 0, INF],
    [INF, INF, 2, 0]
]

# 플로이드-워셜 알고리즘 실행
def floyd_warshall(graph):
    n = len(graph)
    
    # 최단 거리를 저장할 2차원 리스트를 그래프의 가중치로 초기화한다.
    dist = [row[:] for row in graph]
    
    # 모든 정점을 경유점으로 하여 최단 거리를 업데이트한다.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

# 최단 거리 계산
shortest_distances = floyd_warshall(graph)

for row in shortest_distances:
    print(row)

#출력 결과
#[0, 3, 7, 5]
#[2, 0, 6, 4]
#[3, 1, 0, 5]
#[5, 3, 2, 0]