다익스트라 알고리듬(파이썬)

namu.wiki/w/다익스트라%20알고리즘

다익스트라 알고리즘 - 나무위키

https://www.youtube.com/watch?v=611B-9zk2o4 

기본적으론 이렇게 코딩할 수 있고.....
O(V^2)의 시간복잡도를 가집니다. 

# 다익스트라
# 2021.05.01
# ComDoc

def dijkstra(start, pairs):
    graph = {}
    for v1, v2, distance in pairs:
        graph.setdefault(v1, {v2: distance})
        graph[v1][v2] = distance
        graph.setdefault(v2, {v1: distance})
        graph[v2][v1] = distance

    # 출발점으로부터의 최단거리를 저장할 딕셔너리 distances를 만들고,
    # 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 float('inf')를 채워 넣는다.
    distances = {key: float('inf') for key in graph}
    distances[start] = 0

    # 깊이 우선 탐색(stack), 너비 우선 탐색(queue) 무엇을 써도 지금은 상관은 없다.. 어짜피 완전 검색을 하니까...
    # 여기서 시간을 더 절약할 수 있는 방법이 있긴 하지만.... 지금은 때가 아니다.
    stack = [(start, 0)]  # (노드, 시작점과 노드의 거리)
    while stack:
        node, new_distance = stack.pop()  # 스택의 가장 마지막 원소를 꺼낸다.
        print(stack)
        print(node, new_distance, distances)
        if new_distance <= distances[node]:  # 기존 거리와 새 거리가 같은 경우에도 진행이 되어야 한다. 작은 경우는 당연.
            distances[node] = new_distance
            for next_node in graph[node]:
                stack.append((next_node, distances[node] + graph[node][next_node]))  # 기존 거리에 그래프의 거리를 더함
    return distances


print(dijkstra('A', (('A', 'B', 8), ('A', 'C', 1), ('A', 'D', 2), ('B', 'C', 5), ('C', 'D', 2), ('C', 'E', 3),
                     ('D', 'F', 5), ('E', 'F', 1))))

길다~!

[]
A 0 {'A': 0, 'B': inf, 'C': inf, 'D': inf, 'E': inf, 'F': inf}
[('B', 8), ('C', 1)]
D 2 {'A': 0, 'B': inf, 'C': inf, 'D': inf, 'E': inf, 'F': inf}
[('B', 8), ('C', 1), ('A', 4), ('C', 4)]
F 7 {'A': 0, 'B': inf, 'C': inf, 'D': 2, 'E': inf, 'F': inf}
[('B', 8), ('C', 1), ('A', 4), ('C', 4), ('D', 12)]
E 8 {'A': 0, 'B': inf, 'C': inf, 'D': 2, 'E': inf, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('C', 4), ('D', 12), ('C', 11)]
F 9 {'A': 0, 'B': inf, 'C': inf, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('C', 4), ('D', 12)]
C 11 {'A': 0, 'B': inf, 'C': inf, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('C', 4), ('D', 12), ('A', 12), ('B', 16), ('D', 13)]
E 14 {'A': 0, 'B': inf, 'C': 11, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('C', 4), ('D', 12), ('A', 12), ('B', 16)]
D 13 {'A': 0, 'B': inf, 'C': 11, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('C', 4), ('D', 12), ('A', 12)]
B 16 {'A': 0, 'B': inf, 'C': 11, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('C', 4), ('D', 12), ('A', 12), ('A', 24)]
C 21 {'A': 0, 'B': 16, 'C': 11, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('C', 4), ('D', 12), ('A', 12)]
A 24 {'A': 0, 'B': 16, 'C': 11, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('C', 4), ('D', 12)]
A 12 {'A': 0, 'B': 16, 'C': 11, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('C', 4)]
D 12 {'A': 0, 'B': 16, 'C': 11, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4)]
C 4 {'A': 0, 'B': 16, 'C': 11, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('A', 5), ('B', 9), ('D', 6)]
E 7 {'A': 0, 'B': 16, 'C': 4, 'D': 2, 'E': 8, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('A', 5), ('B', 9), ('D', 6), ('C', 10)]
F 8 {'A': 0, 'B': 16, 'C': 4, 'D': 2, 'E': 7, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('A', 5), ('B', 9), ('D', 6)]
C 10 {'A': 0, 'B': 16, 'C': 4, 'D': 2, 'E': 7, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('A', 5), ('B', 9)]
D 6 {'A': 0, 'B': 16, 'C': 4, 'D': 2, 'E': 7, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('A', 5)]
B 9 {'A': 0, 'B': 16, 'C': 4, 'D': 2, 'E': 7, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('A', 5), ('A', 17)]
C 14 {'A': 0, 'B': 9, 'C': 4, 'D': 2, 'E': 7, 'F': 7}
[('B', 8), ('C', 1), ('A', 4), ('A', 5)]
A 17 {'A': 0, 'B': 9, 'C': 4, 'D': 2, 'E': 7, 'F': 7}
[('B', 8), ('C', 1), ('A', 4)]
A 5 {'A': 0, 'B': 9, 'C': 4, 'D': 2, 'E': 7, 'F': 7}
[('B', 8), ('C', 1)]
A 4 {'A': 0, 'B': 9, 'C': 4, 'D': 2, 'E': 7, 'F': 7}
[('B', 8)]
C 1 {'A': 0, 'B': 9, 'C': 4, 'D': 2, 'E': 7, 'F': 7}
[('B', 8), ('A', 2), ('B', 6), ('D', 3)]
E 4 {'A': 0, 'B': 9, 'C': 1, 'D': 2, 'E': 7, 'F': 7}
[('B', 8), ('A', 2), ('B', 6), ('D', 3), ('C', 7)]
F 5 {'A': 0, 'B': 9, 'C': 1, 'D': 2, 'E': 4, 'F': 7}
[('B', 8), ('A', 2), ('B', 6), ('D', 3), ('C', 7), ('D', 10)]
E 6 {'A': 0, 'B': 9, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
[('B', 8), ('A', 2), ('B', 6), ('D', 3), ('C', 7)]
D 10 {'A': 0, 'B': 9, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
[('B', 8), ('A', 2), ('B', 6), ('D', 3)]
C 7 {'A': 0, 'B': 9, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
[('B', 8), ('A', 2), ('B', 6)]
D 3 {'A': 0, 'B': 9, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
[('B', 8), ('A', 2)]
B 6 {'A': 0, 'B': 9, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
[('B', 8), ('A', 2), ('A', 14)]
C 11 {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
[('B', 8), ('A', 2)]
A 14 {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
[('B', 8)]
A 2 {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
[]
B 8 {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
{'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 4, 'F': 5}

 

힙 큐를 사용하면 
O(lg N)의 시간복잡도를 가집니다. 

# 다익스트라 heapq
# 2021.05.01
# ComDoc

from heapq import heappush, heappop


def dijkstra(start, pairs):
    graph = {}
    for v1, v2, distance in pairs:
        graph.setdefault(v1, {v2: distance})
        graph[v1][v2] = distance
        graph.setdefault(v2, {v1: distance})
        graph[v2][v1] = distance

    distances = {key: float('inf') for key in graph}
    distances[start] = 0

    queue = []
    heappush(queue, (distances[start], start))  # 힙큐에 튜플이(나 리스트가) 들어갈 경우 튜플의 원소 순으로 정렬된다.
    while queue:
        new_distance, node = heappop(queue)
        print(queue)
        print(node, new_distance, distances)
        if new_distance <= distances[node]:
            distances[node] = new_distance
            for next_node in graph[node]:
                next_distance = distances[node] + graph[node][next_node]
                # heapq는 가장 작은 원소가 pop 되므로, 만약 next_distance가 기존 거리보다 크다면 탐색하지 않아도 된다.
                if next_distance < distances[next_node]:
                    heappush(queue, (next_distance, next_node))
    return distances


print(dijkstra('A', (('A', 'B', 8), ('A', 'C', 1), ('A', 'D', 2), ('B', 'C', 5), ('C', 'D', 2), ('C', 'E', 3),
                     ('D', 'F', 5), ('E', 'F', 1))))

짧다~!

[]
A 0 {'A': 0, 'B': inf, 'C': inf, 'D': inf, 'E': inf, 'F': inf}
[(2, 'D'), (8, 'B')]
C 1 {'A': 0, 'B': inf, 'C': inf, 'D': inf, 'E': inf, 'F': inf}
[(3, 'D'), (4, 'E'), (6, 'B'), (8, 'B')]
D 2 {'A': 0, 'B': inf, 'C': 1, 'D': inf, 'E': inf, 'F': inf}
[(4, 'E'), (7, 'F'), (6, 'B'), (8, 'B')]
D 3 {'A': 0, 'B': inf, 'C': 1, 'D': 2, 'E': inf, 'F': inf}
[(6, 'B'), (7, 'F'), (8, 'B')]
E 4 {'A': 0, 'B': inf, 'C': 1, 'D': 2, 'E': inf, 'F': inf}
[(6, 'B'), (7, 'F'), (8, 'B')]
F 5 {'A': 0, 'B': inf, 'C': 1, 'D': 2, 'E': 4, 'F': inf}
[(7, 'F'), (8, 'B')]
B 6 {'A': 0, 'B': inf, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
[(8, 'B')]
F 7 {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
[]
B 8 {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 4, 'F': 5}
{'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 4, 'F': 5}