다익스트라

다익스트라(Dijkstra) 알고리즘 이란?

최단경로Shortest Path 알고리즘 중 하나로써, 어떤 시작 노드를 기준으로 다른 특정 노드로 가는 최단 경로를 구하는 알고리즘 이다.

 

특징

• 특정 노드로부터 그래프의 어떤 다른 노드라도 최단 경로를 알 수 있다.
• 항상 짧은 경로를 선택하는 그리디 알고리즘에 속한다
• 간선의 가중치가 음수인 경우 사용할 수 없다.

기본 진행 과정

1. 각 노드로 이동하는 최단 거리를 세팅한 1차원 배열(distance)을 만들고 무한대 값으로 초기화한다. 
2. 시작노드를 지정하고 distance 배열 내 시작노드의 최단 거리를 0으로 만든다.
3. 방문하지 않은 노드들 중에서 distance를 이용해 가장 거리가 짧은 노드(cursor)를 선택한다.
4. cusror에 연결된 노드들을 순회하며, distance와 비교해 거리(cursor + 가중치)가 짧을 경우 갱신한다.
5. 모든 노드가 방문 처리될 때까지 3~4를 반복한다.

진행 과정 그래프

1) 방문 안된 가장 가까운 노드인 1번 가지고 경로 순회

노드번호	1	2	3	4	5	6
거리	0	2	5	1	INF	INF

 

2) 그 다음 방문 안된 가장 가까운 노드인 4번 가지고 경로 순회 후 기존값과 비교하며 작으면 갱신

노드번호	1 [방문완료]	2	3	4	5	6
거리	0	2	4	1	2	INF

 

3) 그 다음 방문 안된 가장 가까운 노드인 2번 가지고 경로 순회 후 기존값과 비교하며 작으면 갱신

노드번호	1 [방문완료]	2	3	4[방문완료]	5	6
거리	0	2	4	1	2	INF

4) 그 다음 방문 안된 가장 가까운 노드인 5번 가지고 경로 순회 후 기존값과 비교하며 작으면 갱신

노드번호	1 [방문완료]	2 [방문완료]	3	4[방문완료]	5	6
거리	0	2	3	1	2	4

5) 그 다음 방문 안된 가장 가까운 노드인 3번 가지고 경로 순회 후 기존값과 비교하며 작으면 갱신

노드번호	1 [방문완료]	2[방문완료]	3	4[방문완료]	5[방문완료]	6
거리	0	2	3	1	2	4

6) 그 다음 방문 안된 가장 가까운 노드인 6번 가지고 경로 순회 후 기존값과 비교하며 작으면 갱신

노드번호	1 [방문완료]	2[방문완료]	3[방문완료]	4[방문완료]	5[방문완료]	6
거리	0	2	3	1	2	4

 

기본 진행 과정에 따른 코드

INF = 999999999;
graph = [
    [(2,2),(4,1),(3,5)],
    [(4,2),(3,3)],
    [(2,3),(3,5)],
    [(3,3),(5,1)],
    [(3,1),(6,2)],
    []
]

distances = [INF for _ in range(0,6)];
visited = [0 for _ in range(0,6)]
# 시작지점은 비용이 0
distances[0] = 0
cursor = 0
# 현재 업데이트 된 가중치리스트 중 방문하지 않은 것에서 가장 가벼운 이동거리인 노드 선택(중계용)
def get_shortest():
    global distances
    temp = INF
    res = -1
    for n in range(0, len(distances)):
        if(visited[n] == 1): continue
        distance = distances[n]
        if(distance < temp):
            res = n
            temp = distance
    return res

for i in range(0,6):
    nodenum = get_shortest();
    if(nodenum == -1): break
    visited[nodenum] = 1
    node = graph[nodenum]
    # 위에 선택된 가장 가까운 노드(중계용)와 현재 거리를 비교해서 중계시에 갱신되는지 확인
    for e in range(0, len(node)):
        edge = node[e]
        c1 = distances[nodenum] + edge[1]
        if(distances[edge[0] - 1] > c1):
            distances[edge[0] - 1] = c1
        
print(distances)

 

기본 진행 코드의 문제점

시간복잡도가 O\(EV\) -> O\(V^2\) 가 된다. 가장 가벼운 이동거리인 노드를 구할 때 O\(V\)만큼 걸리기 때문이다.

게다가 여기서 최악의 경우 완전그래프 일때 E는 거의 V에 수렴하므로 O\(V^2\) 의 시간이 소요된다. 이는 노드의 갯수가 많을 경우 시간초과의 원인이 된다.

 

개선 방향

힙을 이용하여 O\(ElogV\)로 바꿀 수 있다. 힙이 자신의 내용물을 정렬(삽입,삭제) 할때 logV 만큼 시간이 걸리고, 간선 단위로 해당 행위를 반복하긴 하지만 애초에 힙에 넣을때 갱신이 되는 경우만 힙에 들어가므로 위의 기본진행 코드와는 다르게 E로 볼 수 있다. 따라서 위 두 시간복잡도를 조합해서 O\(ElogV\)만에 수행이 가능하다.

 

개선한 코드

import heapq


INF = 999999999;
graph = [
    [(2,2),(4,1),(3,5)],
    [(4,2),(3,3)],
    [(2,3),(3,5)],
    [(3,3),(5,1)],
    [(3,1),(6,2)],
    []
]

distances = [INF for _ in range(0,6)];
visited = [0 for _ in range(0,6)]
# 시작지점은 비용이 0
distances[0] = 0
cursor = 0
shortest = []
heapq.heappush(shortest, (0,0))
while shortest:
    # 현재 업데이트 된 가중치리스트 중 방문하지 않은 것에서 가장 가벼운 이동거리인 노드 선택(중계용)
    shortest_item = heapq.heappop(shortest);
    shortest_node = shortest_item[1]
    # 굳이 이미 힙에 있는게 갱신된거 보다 긴 거리라면 무시 (중복방지)
    if(distances[shortest_node] < shortest_item[0]): continue
    node = graph[shortest_node]
    # 위에 선택된 가장 가까운 노드(중계용)와 현재 거리를 비교해서 중계시에 갱신되는지 확인
    for e in range(0, len(node)):
        edge = node[e]
        c1 = distances[shortest_node] + edge[1]
        if(distances[edge[0] - 1] > c1):
            distances[edge[0] - 1] = c1
            # 갱신된 정보를 기준으로 가장 짧은걸 선택해야 하므로, 갱신된 값을 기준으로 가장 짧은 노드 선택 가능하게 힙에 넣기
            heapq.heappush(shortest, (c1, edge[0] - 1)); 

print(distances)

 

 

재구현한 코드

데이크스트라는 ** 가장 짧은 간선** 기준으로 순회하기 때문에, 아래와 같은 로직으로 기억하면 된다.

1) 시작지점으로 가는게 가장 빠르므로 해당 간선 큐에 추가

2) 이 간선을 시작으로 순회하며, 기존 dp와 다르게 갱신되는경우 해당 간선을 큐에 추가한다

3) 이미 처리된 간선의 경우 중복탐색을 안하도록 무시한다.

import heapq
INF = 10e9
def dijkstra(graph, start):
    global INF
    dp = [INF for _ in range(len(graph))];
    dp[start] = 0
    # 시작지점이 가장 짧은 간선임
    queue = [(0,start)]
    heapq.heapify(queue)
    while queue:
        node = heapq.heappop(queue)
        # 이미 처리된 아이라면 pass
        if(dp[node[1]] < node[0]): continue
        for cidx in range(len(graph[node[1]])):
            child = graph[node[1]][cidx]
            # 중간에 거친게 더 짧아서 갱신할 아이라면
            if(dp[cidx] > node[0] + child):
                dp[cidx] = node[0] + child
                heapq.heappush(queue,(node[0] + child, cidx))
    return dp