그래프 최단 경로 알고리즘 (다익스트라)

[16강] 그래프(Graph) 최단 경로 알고리즘

안녕하세요 Gliver 입니다.이번 글에서는 그래프(Graph) 최단 경로 알고리즘에 대해 알아보겠습니다. <span style="color: #00000..

https://gliver.tistory.com/38

그래프에서 최단 경로란?

• 그래프에서 최단 경로란 어떤 노드 A에서 어떤 노드 B까지의 최단 경로를 의미한다.

• 즉, A에서 B로 가는 다양한 경로가 있다면 그중에서 거리가 가장 짧은 거리를 최단 거리라 하며 그때의 경로를 최단 경로라고 한다.

• 거리가 짧다는 것의 기준은 무엇일까?
• 가중 그래프가 아닌 경우에는 경로 상에 있는 간선의 수가 적을수록 짧다.
• 가중 그래프인 경우에는 경로 상에 있는 간선의 가중치의 합이 작을수록 짧다.

• 최단 경로는 항상 정의될 수 있는가?



• 사이클이 존재하며, 그 사이클이 음수 사이클이라면 최단 거리가 정의될 수 없다.
• 왜냐하면, 사이클을 거치면 거칠수록 경로의 거리가 줄어드는 구조이기 때문에 최단 거리가 무한히 작아질 수 있기 때문이다.

• 음수 사이클이 없는 경우에 최단 경로/거리 알고리즘
1. 다익스트라(Dijkstra) 알고리즘
• 제약 조건: 음수 간선 존재 X
• 결과물: 한 노드에서 다른 모든 노드까지의 최단 경로/거리
시간 복잡도:
• : 노드의 개수
• : 간선의 개수
 
2. 벨만-포드(Bellman-Ford) 알고리즘
• 제약 조건: 없음
• 결과물: 한 노드에서 다른 모든 노드까지의 최단 경로/거리
시간 복잡도:
• : 노드의 개수
• : 간선의 개수
 
3. 플로이드-워셜(Floyd-Warshall) 알고리즘
• 제약 조건: 없음
• 결과물: 모든 노드에서 다른 모든 노드까지의 최단 경로/거리
시간 복잡도:
• : 노드의 개수
• : 간선의 개수

다익스트라 알고리즘

• 한 노드에서 다른 모든 노드까지의 최단 경로/거리를 구하는 알고리즘이다.

• 다익스트라 알고리즘은 음수 간선이 존재하지 않을 때만 사용할 수 있다.

• 다익스트라 알고리즘은 시작(기준) 노드로부터 가까운 노드를 그리디하게 방문한다.

음수 간선이 존재하지 않는 경우에는 경로가 늘어나면 항상 경로의 길이 또한 늘어나므로, 시작 노드로부터 가까운 노드를 그리디하게 선택하는 전략을 사용해도 되는 것이다.

• 다익스트라 알고리즘 로직
• 현재 살펴보지 않은 경로 중에서 가장 거리가 짧은 경로를 먼저 살펴봐야 한다.
• 따라서, 경로들을 heap(priority queue) 자료형에 담고 짧은 경로부터 꺼내서 탐색하면 된다.

시작 노드를 0번 노드로 하여 다익스트라 알고리즘 수행

from queue import PriorityQueue

INF = int(1e12)
N = 5

adj_list = [[] for _ in range(N)]
dist = [INF] * N

# Create Adjacency List
adj_list[0].append([1, 5]); adj_list[0].append([3, 1]);
adj_list[1].append([2, 2])
adj_list[2].append([4, 2])
adj_list[3].append([1, 2]); adj_list[3].append([4, 7]);

# Execute Dijkstra Algorithm with standard(start) node '0'
pq = PriorityQueue()
pq.put([0, 0])
dist[0] = 0

while not pq.empty(): # pq.queue
    cur_dist, cur_node = pq.get()
    for adj_node, adj_dist in adj_list[cur_node]:
        temp_dist = cur_dist + adj_dist
        if temp_dist < dist[adj_node]:
            pq.put([temp_dist, adj_node])
            dist[adj_node] = temp_dist

# Print result
print(dist)

최단 경로 알고리즘 정리

• Case1. 한 노드에서 다른 (모든) 노드까지의 최단 경로/거리 (음수 간선 존재 X)
• 다익스트라 알고리즘

• Case2. 한 노드에서 다른 (모든) 노드까지의 최단 경로/거리 (음수 간선 존재 O)
• 벨만-포드 알고리즘

• Case3. 모든 노드에서 모든 노드까지의 최단 경로/거리
• 플로이드-워셜 알고리즘