다익스트라 알고리즘

다익스트라 알고리즘

Dijkstra Algorithm

---

짧은 요약

 

다익스트라, 그게 뭔데?

음의 간선이 없을 때, 특정 노드로부터 다른 노드까지의 최소 경로를 구하는 알고리즘. 만약 간선의 비용이 일정하다면 BFS로도 충분.

매 순간 가장 비용이 적은 노드를 선택하여 누적 비용을 갱신하므로 그리디 알고리즘으로 분류된다.

 

시간 복잡도, 얼마나 빠른데?

구현 방법에 따라서 시간 복잡도가 다르다.

• 우선순위 큐를 사용하지 않았을 때,

$$O(V^2)$$

• 우선순위 큐를 사용했을 때,

$$O(E + VlogV)$$

 

필요한 요소, 그래서 뭘 하면 되는데?

• 각 노드의 연결상태를 저장하는 행렬, 2차 배열.
• 시작 노드로부터 각 노드로의 누적 비용을 저장하는 리스트
• 방문한 노드를 저장하는 리스트

---

예시

다익스트라 그래프, 초기상태(dijkstra wiki)

 

초기 설정

• 출발 노드, 누적 비용 0
• 출발 노드 외, 누적 비용 INF
• 각 노드의 연결 상태를 저장하는 그래프, 위 그림의 그래프는 양방향(bidirectional)임에 주의
• 방문 리스트
• 위 그림의 경우, a에서 b로 향하는 최소 비용을 구하는 것이지만 출발 노드 외에 모든 노드와의 비용을 구할 때도 사용할 수 있다.

 

입력

input.txt

number of node(vertex), edge

startnode

node another_node cost

...

6 9
1
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9

 

소스 코드

import sys
sys.stdin = open(r'python\short_path\input.txt')
input = sys.stdin.readline
INF = int(1e9)

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

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

위 코드처럼 input.txt에 입력값을 저장하여 실행 할 때마다 입력하지 않도록 한다.

연결되지 않은 노드의 비용을 infinite, INF로 설정

각 리스트의 첫 번째 index(0)은 사용하지 않으므로 n+1의 개수를 맞춘다.

문제의 그래프는 양방향이므로 a와 b를 바꾸어 대입

def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if not visited[i] and distance[i] < min_value:
            min_value = distance[i]
            index = i
            
    return index

누적비용이 제일 적으면서 방문하지 않은 노드를 찾는 함수

def dijkstra(start):
    distance[start] = 0
    visited[start] = 0
    
    for j in graph[start]:
        distance[j[0]] = j[1]
    
    for i in range(n-1):
        cur = get_smallest_node()
        visited[cur] = True
        for j in graph[cur]:
            cost = distance[cur] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost

다익스트라 구현 함수

다익스트라는 특정 노드에서 다른 노드까지 최소 경로를 구하는 알고리즘이다.

• 방문하지 않은 노드 중에서 누적 비용이 가장 적은 노드를 선택한다.
• 선택한 노드의 인정 노드로의 거리를 통해 최소 누적 비용 리스트를 갱신한다. (위 코드의 if문 참고)
• 다시 방문하지 않은 노드 중에서 누적 비용이 가장 적은 노드를 선택하므로 위 과정을 반복한다.