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

https://gliver.tistory.com/38

그래프에서 최단 경로란?

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

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

• 거리가 짧다는 것의 기준은 무엇일까?

  • 가중 그래프가 아닌 경우에는 경로 상에 있는 간선의 수가 적을수록 짧다.
  • 가중 그래프인 경우에는 경로 상에 있는 간선의 가중치의 합이 작을수록 짧다.

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

  

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

• 음수 사이클이 없는 경우에 최단 경로/거리 알고리즘

  1. 다익스트라(Dijkstra) 알고리즘
     • 제약 조건: 음수 간선 존재 X
     • 결과물: 한 노드에서 다른 모든 노드까지의 최단 경로/거리

2. **벨만-포드(Bellman-Ford) 알고리즘**
    - **제약 조건**: 없음
    - **결과물**: 한 노드에서 다른 모든 노드까지의 최단 경로/거리

3. **플로이드-워셜(Floyd-Warshall) 알고리즘**
    - **제약 조건**: 없음
    - **결과물**: 모든 노드에서 다른 모든 노드까지의 최단 경로/거리

다익스트라 알고리즘

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

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

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

  Note

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

• 다익스트라 알고리즘 로직

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

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. 모든 노드에서 모든 노드까지의 최단 경로/거리
  • 플로이드-워셜 알고리즘