최단 경로 알고리즘

다익스트라(Dijkstra) 알고리즘

• 한 정점에서 다른 모든 정점으로 가는 최단거리를 구하는 알고리즘.
• 매번 방문하지 않은 노드 중 가장 가까운 노드를 선택하여 하나씩 최단 거리를 구해나간다.
• 다이나믹 프로그래밍, 그리디 알고리즘에 포함됨.
• 음의 가중치를 가진 간선을 포함할 수 없음. 음의 가중치를 간선이 있다면 벨만-포드 알고리즘 사용.

import heapq        

graph = [[] for _ in range(v)]

def dijkstra(start):
    distance = [int(1e9)] * (v)
    distance[start] = 0

    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:    # 이미 방문한 경우
            continue
        for nx in graph[now]:
            if dist + 1 < distance[nx]:
                distance[nx] = dist + 1
                heapq.heappush(q, (dist+1, nx))
    return distance

• 시간 복잡도 : $O((V+E)logV)$ (V는 정점의 개수, E는 한 정점의 주변 노드)
  • 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 $O(VlogV)$의 시간 소요. (모든 노드($O(V)$)에 대해 힙에서 최소값을 추출($O(logV)$))
  • 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 $O(ElogV)$의 시간 소요. 각 노드마다 모든 이웃을 확인하는 것은 모든 edge를 확인하는 것과 같고($O(E)$), 매번 힙에서 최단 거리를 갱신($O(logV)$)해야 하기 때문이다.

 

 

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

• 모든 노드쌍에 대한 최단 거리를 구하는 알고리즘.
• 음의 가중치를 갖는 간선이 있어도 사용 가능.

graph = [[0] * (v) for _ in range(v)]

# i->j로 갈 때 k번 노드를 거쳐서 가는 것이 더 최단 경로인지 확인
for k in range(v):  # 거쳐가는 노드
    for i in range(v):  # 출발 노드
        for j in range(v):  # 도착 노드
						# k번 노드를 거쳐가는 것이 더 빠르다면 값을 갱신
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

• 시간 복잡도 : $O(V^3)$

 

 

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

• 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘.
• 음의 가중치를 가진 간선이 있어도 가능. (다익스트라는 불가능)
• 다이나믹 프로그래밍.
• 벨만 포드는 음의 간선 때문에 모든 경우의 수를 다 탐색하기 때문에 가까운 간선을 선택하여 가는 다익스트라보다는 시간이 오래 걸린다.
• 동작 원리
  • 시작 정점 선택
  • 모든 간선을 탐색하며 시작 정점에서 다른 정점까지의 거리가 INF가 아니라면 거리를 갱신. 이 과정을 V-1번 반복.
    • (V-1)번 반복하는 이유? ⇒ V개의 정점과 E개의 간선이 있는 가중 그래프에서 정점 A에서 B까지의 최단 거리는 최대 V-1개의 정점을 지나기 때문.
  • 마지막으로 2번 과정 한 번 더 수행 ⇒ 음의 사이클 유무 판단. 만약 V개의 정점을 지났는데 최단 경로가 갱신이 된다면음의 사이클이 발생한 것이며 비용이 무한하게 갱신되어 최단 경로를 구할 수 없다.