[Python]다익스트라 알고리즘 구현(Dijkstra algorithm)

이번 글에서는 파이썬 언어를 사용하여 다익스트라 알고리즘을 구현합니다.

1. 다익스트라 알고리즘이란?

노드(node)간에 방향과 가중치를 가지는 간선(edge)으로 연결된 그래프에서,

A지점에서 B지점으로 가는 최단거리를 구할 수 있는 알고리즘.

단, 간선의 가중치가 양수일 경우에만 사용 가능하다.

 

2. 구현 코드

우선순위 큐 준비

import heapq

그래프 인접 리스트 준비

node_n = 6
# (출발노드,도착노드,이동값)
arr = [(0,1,7),(1,2,3),(2,0,1),(0,3,4),(2,3,5),(3,2,1),(3,4,8),(4,3,1),(2,4,2),(1,4,4),(4,5,2),(3,5,9)]
adj_lst = [[] for x in range(6)]


for sp, ep, cost in arr:
    adj_lst[sp].append((ep,cost))
    
print(adj_lst)

방문여부 및 이동거리 저장 리스트 생성

-1로 모두 초기화(-1일 경우 해당 노드는 방문되지 않음)

visit = [-1 for x in range(node_n)]

우선순위큐로 사용될 리스트 생성

초기값인 노드0의 값을 삽입

que = [(0,0)] #(시작부터의 거리, 도착노드)
# 시작부터 0노드에 도착하기까지는 0의 거리가 걸린다는 의미

반복문을 통해서 모든 노드들 조사

이때, 방문된 노드의 경우 무시

※우선순위큐에서 시작부터의 도착 거리를 사용했기때문에,
   같은 노드일경우 먼저 나온 값이 최적의 값이므로 나중에 나온 값을 무시한다

while que:
    # 큐에서 가장 시작으로부터의 거리가 가까운 노드를 뽑아옴(우선순위큐)
    now_cost, now_node = heapq.heappop(que)
    print("현재 조사 대상 : Node_{}, 시작부터의 거리 : {}".format(now_node,now_cost))
    
    # 방문된적이 없다면 수행
    if visit[now_node] == -1:
        print("방문된적이 없는 노드 => 방문 처리")
        print('원본 방문기록:{}'.format(visit))
        
        # 방문기록 리스트에 현재까지의 이동거리 저장
        visit[now_node] = now_cost
        print('수정된 방문기록:{}'.format(visit))

        # 현제 노드(now_node)로부터 갈수 있는 노드들을
        # 추가되는 거리값을 더해서 큐에 삽입
        for next_node, next_c in adj_lst[now_node]:
            next_cost = now_cost + next_c # 현재까지의 거리 + 다음노드로 가기위한 거리
            heapq.heappush(que,(next_cost,next_node)) # 큐에 삽입
    
    # 방문된적이 있다면 무시
    else:
        print('방문된적이 있어 무시')
    print('--------------')
    
# 최종적으로 방문기록에서 마지막 노드까지의 거리 확인
print('마지막 노드까지의 최단 거리 :',visit[end_node])

3. 코드 종합본

import heapq

node_n = 6
start_node = 0
end_node = node_n -1
arr = [(0,1,7),(1,2,3),(2,0,1),(0,3,4),(2,3,5),(3,2,1),(3,4,8),(4,3,1),(2,4,2),(1,4,4),(4,5,2),(3,5,9)]
adj_lst = [[] for x in range(6)]


for sp, ep, cost in arr:
    adj_lst[sp].append((ep,cost))
    
print(adj_lst)

visit = [-1 for x in range(node_n)]

que = [(0,0)]

while que:
    # 큐에서 가장 시작으로부터의 거리가 가까운 노드를 뽑아옴(우선순위큐)
    now_cost, now_node = heapq.heappop(que)
    print("현재 조사 대상 : Node_{}, 시작부터의 거리 : {}".format(now_node,now_cost))
    
    # 방문된적이 없다면 수행
    if visit[now_node] == -1:
        print("방문된적이 없는 노드 => 방문 처리")
        print('원본 방문기록:{}'.format(visit))
        
        # 방문기록 리스트에 현재까지의 이동거리 저장
        visit[now_node] = now_cost
        print('수정된 방문기록:{}'.format(visit))

        # 현제 노드(now_node)로부터 갈수 있는 노드들을
        # 추가되는 거리값을 더해서 큐에 삽입
        for next_node, next_c in adj_lst[now_node]:
            next_cost = now_cost + next_c # 현재까지의 거리 + 다음노드로 가기위한 거리
            heapq.heappush(que,(next_cost,next_node)) # 큐에 삽입
    
    # 방문된적이 있다면 무시
    else:
        print('방문된적이 있어 무시')
    print('--------------')
    
# 최종적으로 방문기록에서 마지막 노드까지의 거리 확인
print('마지막 노드까지의 최단 거리 :',visit[end_node])