Dijkstra

우선순위 큐(Priority Queue)

• 가장 높은 우선순위를 가진 데이터가 큐에서 먼저 추출되는 자료 구조

우선순위 큐(최솟값 찾기) 구현 방식

• 	배열	연결리스트	☆완전이진트리 ☆
  enqueue()	들어오는 대로 배열에 append 시간복잡도 O(1)	append 시 정렬 시간복잡도 O(nlogn)	우선순위 높은 값을 노드쪽으로 swap 시간복잡도 O(logn)
  dequeue()	모든 인덱스 확인하여 원하는 값 찾음 시간복잡도 O(n)	따로 확인 없이 추출 시간복잡도 O(1)	우선순위 높은 값을 노드쪽으로 swap하여 추출 시간복잡도 O(logn)

• 완전이진트리로 우선순위 큐 구현하는 것이 가장 시간복잡도 측면에서 효율적.
  이러한 완전 이진트리는 힙 자료구조로 되어있음.

---

힙(Heap)

• 완전 이진 트리(complete binary tree) 형태의 자료구조
  완전 이진 트리의 경우 노드를 구성하지 않고 리스트 만으로도 구현 가능
• min heap과 max heap으로 구성
  min heap: 부모 노드의 값이 자식 노드의 값보다 작은 트리 형태의 자료구조
  max heap: 부모 노드의 값이 자식 노드의 값보다 큰 트리 형태의 자료구조
• 형제 노드 간에는 대소 관계 X
• Root 노드가 가장 큰(작은) 값을 가짐

Heap의 method

• heapify()
  리스트를 힙으로 변환
  시간 복잡도 O(N)
• heapify_max()
  리스트를 맥스힙으로 변환
• heappush()
  enqueue()
  시간 복잡도 O(logN)
• heappop()
  dequeue()
  시간 복잡도 O(logN)

---

다익스트라(Dijkstra)

• 가중치 그래프에서 시작점과 도착점이 주어졌을 때 최단경로를 return하는 알고리즘
• 방문할 수 있는 노드 중에 가장 비용이 적은 곳 방문
• 다익스트라 구현 과정
  1. 우선순위큐에 시작 노드 추가
      2. 우선순위가 가장 높은 노드 추출
      3. 방문여부 확인
          4. 비용 업데이트
          5. 현재 노드와 연결된 노드 우선순위 큐에 추가
  6. 목적지에 기록된 비용 반환

가중치 그래프

#비가중치 그래프 => (인접노드)
graph = {
	1: [2, 4]
	2: [3, 5, 6]
	3: [6]
	4: [3, 7]
	5: [8]
	6: [5]
	7: [6, 8]
	8: []
}

#가중치 그래프 => (가중치, 인접노드)
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, n):
    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 cost[final]
    
graph = {...}
dijkstra(graph, 1, 8)

 

참고자료

https://www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC