[알고리즘] CHAP 4. GA - Dijkstra's algorithm (다익스트라 알고리즘)

이번 게시글은 탐욕 알고리즘의 마지막 알고리즘으로 다익스트라 알고리즘을 정리할 예정이다. 목차는 다음과 같다.

• Dijkstra's algorithm (다익스트라 알고리즘)

 

탐욕알고리즘은 아래 게시글에 설명되어있다.

https://wanna-developer02.tistory.com/51

[알고리즘] CHAP 4. The Greedy Approach (탐욕알고리즘) - Prim's alg (프림알고리즘)

---

1. Dijkstra 알고리즘

다익스트라 알고리즘은 가중치그래프에서 출발점으로부터 각 노드까지의 최단경로를 찾는 알고리즘이다. 특이하게 다익스트라알고리즘에서는 시작노드가 지정되어있다. 그래서 시작점에서 각 노드까지의 최단경로를 저장한다.

 

또 다른 특징은 한 번 방문된 정점의 D 원소값이 변하지 않는다는 것인데, 이러한 특징때문에 음수 가중치가 있을 때 무한루프에 걸리게 된다.

 

위에서부터 순서대로 기본, v5까지, v4까지, v3까지, v2까지 경로이다.

 

시작점은 v1이다!

 

# Code

visited = [False] * N
D = [sys.maxsize] * N
D[s] = 0
previous = [None] * N
previous[s] = s

for k in range(N) :
	m = -1
    min_val = sys.maxsize
    for j in rnage(N) :
    	if not visited[j] and D[j] < min_val :
        	min_val = D[j]
            m = j
    visited[m] = True
    
    for v, wt in list(g[m]) :
    	if not visited[v] :
        	if D[m] + wt < D[v] :
            	D[v] = D[m] + wt
                previous[v] = m

 

시간복잡도는 프림과 동일하므로 생략할 예정이다! 다음 게시글에서는 Greedy Approach를 이용한 Knapsack Problem에 대해 정리할 예정이다!