[알고리즘] 다익스트라(dijkjstra) 알고리즘이란? with Python

 💡 다익스트라 알고리즘 

그래프에서 특정 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구해주는 문제
매번 최단 경로의 정점을 선택하여 탐색 반복 

 

 

🌱 다익스트라 알고리즘 특징 

도착노드는 해당 노드를 거쳐 다른 노드로 가는 길을 찾을 필요가 없다. 
다익스트라 알고리즘은 가중치가 양수일 때만 사용 가능하다.

 

 

☝ 동작 단계 

1. 출발노드와 동작노드 설정해주고 최단 거리 테이블을 초기화해준다. 

2. 현재 위치에서의 인접한 노드들 중에서 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한 뒤,   

    방문 처리 해준다. 

3. 해당 노드에서 다른 노드로 넘어가는 간선 비용(가중치)를 계산하여 최단 거리 테이블을 업데이트 해준다. 

4. 3~4번 과정 반복 

 

- 최단 거리 테이블 : 1차원 배열로 N개 노드까지 오는데 필요한 최단 거리를 기록 //  N개 크기의 배열을 선언하고 큰 값을 넣어 초기화 

- 방문 처리 배열 : 해당 노드가 방문한 노드인지 아닌지를 기록하기 위한 배열로, 전체 배열을 방문하지 않은 False로 두고 방문한 노드는 True로 변경해준다. 

 

✌ 동작 예시 

출발 노드는 1번, 도착 노드는 6번 

거리테이블은 큰 값인 무한대로 초기화해준다. 

노드들을 잇는 중간에는 간선 비용(가중치)를 작성해준다. 

 

출발 노드를 1, 도착노드를 6으로 설정해준뒤, 출발노드에서 자기 자신의 거리는 0이므로 거리를 0으로 설정해준다.

1번에서 출발할 때 인접 노드는 2와 4이다. 1에서 2로 갈때의 값은 2, 1에서 4로 갈때의 값은 1이다.

인접노드까지 가는 거리를 기존의 거리값과 비교하여 최소값으로 업데이트 해준다. 인접 노드 2까지 가는 최소 거리는 2와 inf 중에 2, 인접노드 4까지 가는 최소 거리는 1과 inf중에 1이다. 

거리 테이블을 업데이트 해준 뒤, 인접 노드까지의 거리를 모두 업데이트 한 노드 1은 방문 처리를 해준다. 

그 후 1에서 인접 노드로 갈 때 거리비용이 적은 4번 노드로 이동한다. 

 

노드 4에서 갈 수 있는 인접 노드는 2와 5이다. 

4번과 연결된 2, 5번까지 가는 거리를 계산하면, 먼저 4에서 2로 가는 경우에는 기존의 1번-> 4번으로 올때 거리비용 1과 4에서 2로 가는 거리비용 2를 더한 3이다. 

하지만 기존에 노드 2번에 거리비용이 2가 있는데, 이는 1에서 2로 갈때의 최소값을 갱신했던 값이다. 

2와 3을 비교했을 때 거리비용이 2가 더 적게 걸리므로 업데이트해주지 않고 2를 유지해준다. 

4번-> 5번 노드로 갈 때에는 위와 같이 1+ 1 = 2, 거리비용은 inf와 2를 비교했을 때 최소 값이 2로 업데이트 해준다. 

 

 

다음으로 갈 노드는 거리값이 가장 작은 2번 노드와 5번 노드 중 하나이다.

거리 값이 같을 때에는 인덱스가 작은 노드인 2부터 이동해본다. 

 

 

2번노드에서 인접 노드는 3번, 4번노드이다. 

2번-> 4번으로 갈때의 거리비용은 2+2 = 4이다. 

거리비용 4와 기존의 거리비용 1을 비교했을 때 최소값은 기존 값이므로 업데이트 해주지 않는다.

2번-> 3번으로 이동할 때의 거리비용은 2+ 3 = 5이다. 기존의 거리비용 inf와 5를 비교하였을 때 최소값은 5이므로 5번 거리 테이블을 5로 업데이트 해준다. 

다음으로 방문하지 않은 노드 3,5,6번 중 거리비용이 작은 5번으로 이동해준다. 

 

 

5번에서 갈 수 있는 인접노드는 4번과 6번이다. 

4번은 위와 같은 방법으로 업데이트 하지않는다. 

5번-> 6번 노드로 이동할 때에는 기존 노드 5번의 거리비용 2와 5번->6번 이동할때의 거리비용 2를 더한  4이므로 , 6번 테이블의 기존 거리비용 inf와 비교했을 때  4로 갱신해준다. 

 

최종적으로 1번 노드에서 6번 노드 까지 오는데 거치는 노드는 1-> 4-> 5-> 6 이고, 최소 거리비용은 4이다. 

 

 

🕒 시간 복잡도 

간선의 수: E(Edge) 
노드의 수: V(Vertex)
 => O(E logV)
하나의 간선에 대해서는 O(logE)이고,  최악의 경우에 대해서는 O(E logV)이다.

 

 

👩🏻‍💻 코드 구현 

1. 기본 동작 - heapq 방식 

INF = int(1e9)

n,m=map(int,input().split())
start = int(input())
graph=[[] for i in range(n+1)]
distance=[INF]*(n+1)

for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c))

def dijkstra(start):
    q=[]
    heapq.heappush(q,(0,start))
    distance[start]=0

    while q:
        # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 처리된적이 있는 노드라면 pass
        if distance[now]<dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]]=cost
                heapq.heappush(q,(cost,i[0]))
                
dijkstra(start)

for i in range(1,n+1):
    if distance[i]==INF:
        print("INFINITY")
    else:
        print(distance[i])

 

2. 최단 경로 추적 

mport heapq
INF = int(1e9)

n,m = 8,14 # 노드 수
start = 1 # 출발 노드
graph=[[] for i in range(n+1)]
# 최단거리 + 부모노드 저장 테이블 생성
distance=[[INF,i] for i in range(n+1)]

# 양방향 입력
# 노드 a와 노드 b의 비용 c
for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

def dijkstra(start):
    q=[]
    heapq.heappush(q,(0,start))
    distance[start][0]=0

    while q:
        # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 처리된적이 있는 노드라면 pass
        if distance[now][0]<dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]][0]:
                distance[i[0]][0]=cost # 최단거리 갱신
                distance[i[0]][1]=now  # 부모노드 저장
                heapq.heappush(q,(cost,i[0]))
                
dijkstra(start)

# 결과 출력
for i in range(1,n+1):
    length,_= distance[i] # 최단 길이
    parent_node=i
    path=[]
    while parent_node!=1:        
        path.append(parent_node)    
        _,parent_node = distance[parent_node]
        distance[parent_node]
    path.append(1)
    print("%s번 노드 : %s (%s)" % (i,">".join(map(str,path[::-1])),length))

1번 노드 : 1 (0)
2번 노드 : 1>2 (3)
3번 노드 : 1>3 (4)
4번 노드 : 1>3>4 (12)
5번 노드 : 1>3>5 (9)
6번 노드 : 1>2>6 (12)
7번 노드 : 1>3>5>7 (13)
8번 노드 : 1>2>6>8 (14)