다익스트라 Dijkstra

강의 출처 : 

 

요약 : 가중치 그래프에서 사용하는 알고리즘

 

가중치 그래프란 ?

그래프

비용이 가장 작게 드는 경로는 ?

 

생각할 경우가 2가지 있다.

 

1. 가중치가 없는 경우 (모든 경로의 가중치는 1)

 

가장 짧은 경로가 가장 비용이 적게 든다. 이 경우는 이전과 동일한 BFS를 이용

 

가중치 그래프

2. 가중치가 있는 경우

 

비용이 가장 적게 드는 경로를 경유해야 한다.

 

간선마다 가중치가 주어진 경우 

 

BFS를 사용하지 않고 이때 다익스트라 알고리즘을 사용해야 한다.

 

 

 

다익스트라

 

다익스트라 알고리즘은 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최단경로를 RETURN 하는 알고리즘

 

 

방문할 수 있는 노드중에 가장 비용이 작은 곳 방문 (우선순위가 높은 곳 방문)

 

 

# 다익스트라 원리

 

1. 우선순위큐에 시작노드 추가

우선순위큐 구현

- 1번 노드 추가 ( 0, 1)

튜플 ( 1번까지 가는 데 필요한 비용 ,  노드)

 

2. 우선순위가 가장 높은 노드 추출 

 

   2-1. 방문여부 확인

- 우선수위 큐의 원리로 인해 방문했던 곳이 중복 방문되면 이 후에 방문한 경우가 비용이 크므로 생략하기 위함.

 

   2-2. 방문여부가 없다면 비용 업데이트

- 해당 노드를 처음 방문하는 경우가 최소비용이므로 으로 업데이트

 

3. 현재 노드와 연결된 노드 우선순위 큐에 추가

- 1번노드와 연결된 2번과 4번 노드 우선순위 큐에 추가

즉 (2, 2) 와 (1,4) 우선순위큐 추가 ( 이때 우선순위큐이기 때문에 자동으로 우선순위 순으로 정렬된다.)

 

- 2번을 반복한다. while 우선순위 큐가 비어있을 때 까지

 

4. 목적지에 기록된 비용(=최소비용) 반환 return

 

 

# 실제 코드 구현

 

# 가중치 그래프

import heapq

# 가중치 그래프 구현

graph = {

  1: [(2,2),(1,4)],

  2: [(1, 3), (9, 5),(6, 6)],

  3: [(4, 6)],

  4: [(3,3), (5, 7)],

  5: [(1, 8)],

  6: [(3, 5)],

  7: [(7, 6), (9,8)],

  8: []

}

# 다익스트라

# 다익스트라 구현

# 템플릿 처럼 머리에 박을 것

# 문제마다 코드를 수정하며 활용해야 함

def dijkstra(graph, start, final):

  costs = {} # 비용 업데이트

  pq = [] # 우선순위 큐

  heapq.heappush(pq,(0, start)) # 우선순위큐에 시작노드 추가

  while pq: # 우선순위 큐가 비어있을 때 까지 반복 == 마지막 노드 업데이트 까지

    cur_cost, cur_v = heapq.heappop(pq)

    if cur_v not in costs: # 방문한적 없다면

      costs[cur_v] = cur_cost # 비용 업데이트

      for cost, next_v in graph[cur_v]:

        next_cost = cur_cost + cost

        heapq.heappush(pq, (next_cost, next_v))  # 연결된 노드 우선순위 큐에 추가

       

  return costs[final] # 마지막 노드의 비용 return (최소 비용)