다익스트라_Dijkstra

다익스트라

• 그래프의 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점뿐만 아니라 모든 다른 정점까지 최단경로로 방문하여 각 정점까지의 최단 경로를 모두 찾게된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

동작과정

1. 출발노드와 도착노드를 설정한다
2. ‘최단 거리 테이블’을 초기화 한다.
3. 현재 위치한 노드의 인접노드 중 방문하지않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 짧은 노드를 선택한다. 그 노드를 방문처리한다.
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)를 계산해 ‘최단 거리 테이블’ 을 업데이트 한다.
5. 3-4 과정을 반복한다.

• ‘최단거리 테이블’ 은 1차원 배열로, N개의 노드까지 오는데 필요한 최단거리를 기록한다. N개 크기의 배열을 선언하고 큰 값을 넘어 초기화 시킨다.

특징

• 가중치가 양수일 때만 사용가능하다.
  • 그래야 한번 방문한 정점에 대해서는 값을 업데이트 하지 않아도 된다.
• 방문하지 않은 노드 중 거리값이 가장 작은 노드’ 를 선택해 다음 탐색 노드로 삼는다.
• 순차탐색 O(N²)
  • 순차탐색을 사용할 경우 노드 개수에 따라 탐색시간이 매우 오래 걸릴 수 있다. 이를 개선하기 위해서 우선 순위 큐를 도입한다.

우선순위 큐 구현

• 거리값을 담을 우선순위 큐는 힙으로 구현하고, 만약 최소힙으로 구현한다면 매번 루트 노드가 최소 거리를 가지는 노드가 될 것이다.
• 파이썬의 경우 Priority queue, heapq 라이브러리 사용
• 우선순위 큐에서 사용할 ‘우선순위’의 기준은 ‘기작노드로 부터 가장 가까운 노드’가 된다. 따라서 큐의 정렬은 최단거리인 노드를 기준으로 최단거리를 가지는 노드를 앞에 배치한다.
• 위의 순차탐색을 쓰는 구현과는 다르게 우선순위 큐를 사용하면 방문여부를 기록할 배열은 없애도 된다. 우선순위 큐가 알아서 최단거리의 노드를 앞으로 정렬하므로 기존 최단거리보다 크다면 무시하면 그만이다. 만약 기존 최단거리보다 더 작은 값을 가지는 노드가 있다면 그 노드와 거리를 우선순위 큐에 넣는다. 우선순위 큐에 삽입되는 형태는 <거리,노드>

def dijkstra(start):
	q = []
	heapq.heappush(q,(0,start))
	distance[start] = 0
	while q:
		dist, node = heapq.heappop(q)
		if distance[node]<dist:
			continue
		for next in graph[node]:
			cost = distance[node] + next[1]
			if cost < distance[next[0]]
				distance[next[0]] = cost
				heapq.heappush(q,(cost,next[0]))