[알고리즘] 다익스트라 알고리즘

다익스트라

---

다익스트라는 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.

bfs, dfs처럼 원리를 통해 특정 경로, 비용 등을 계산하는 알고리즘이다.

 

최단경로(출발, 도착, 비용)

**이때 cost는 양의 가중치, 유향 그래프

 

특징

---

1. 시작점이 주어진다.
2. 시작점을 출발지로 [INF] * (n+1)로 초기화된 node의 가중치 정보를 갱신하며 그래프 탐색을 한다.
3. 이때 노드들을 방문하면서 python heapq를 사용하여 노드 번호와 가중치를 체크하면 최단거리를 찾을 수 있다.
4. graph는 i번째 노드에서 j번째 가는 가중치(w)를 저장해야 하므로 이차원 리스트로 구현한다.

 

 

구현 방법

---

구현은 python heapq를 활용한다.

 

python의 우선순위 큐.

원소들이 항상 정렬된 상태로 추가되고 삭제되며 min값은 언제나 루트(idx = 0)에 위치한다.

heappush() heappush(li, 4) O(log(n))

heappop()	heappop(li)	O(log(n))

• heappop: 가장 작은 원소 삭제

 

 

출발, 시작, 가중치 노드를 다음과 같이 해당 노드 번호에 (연결되는 도착 노드, 비용)으로 저장한다.

 

① 노드 연결 정보 담기

 

# 그래프 초기화
graph = [[] for _ in range(n+1)]

# 정점 정보들 저장
for _ in range(m):
    i, j, c = map(int, input().split())
    graph[i].append((j,c))

 

② 최단 거리 테이블 무한으로 초기화하기

 

node = [INF] * (n+1)

 

 

기본 세팅

---

def dijkstra(start):

# 시작 노드로 가기 위한 최단 경로는 0으로 설정 
    q = []
    heapq.heappush(q, (0, start))
    node[start] = 0
    
    while q:
    	# 최단 거리 노드에 대한 정보 꺼내기
        d, now = heapq.heappop(q)
        # 현재 노드가 이미 처리되었다면 무시
        if node[now] < d: continue
        
        # 현재 노드와 연결된 다른 인접 노드를 확인해서 
        for i in graph[now]:
            dst = i[0]
            cost = d+i[1]
            
            # 해당 인접 노드가 최단거리라면 그 값으로 갱신
            if cost < node[dst]:
                heapq.heappush(q, (cost, dst))
                node[dst] = cost

우선순위 큐를 통해 배열을 구현하였기 때문에 heappop을 하면 자동으로 min값이 도출된다.

이를 통해 가장 최단거리인 노드에 대한 정보를 꺼낼 수 있다.  d: cost, now: node

 

만약 heaqp에서 꺼낸 노드가 이미 처리된 값이라면 무시를 하고, 다른 인접노드를 확인하여 이 값들을 비교해 최단 거리를 구한다.