소개

지금까지는 붙일 뿐이었던 라이브러리의 내용을 조금씩 공부해 나가고 싶은 소존. 이 기사를 쓰는 이유는, 자신의 생각의 확인과 어드바이스등을 받고 싶기 때문에 꼭 코멘트 부탁합니다!(특히 고속화, 계산량)

목적

음의 비용의 변이 없는 그래프에 대해, 하나의 시점으로부터 다른 정점에의 최단 거리를 구한다. (단일 시점 최단로)

원리

그래프의 정점수가 $V$, 변의 수가 $E$일 때를 생각한다. 우선은 2개의 리스트를 준비한다. 하나는 시작점에서 최단 거리를 기록하는 것이고 다른 하나는 최단 경로가 결정되었는지 여부를 기록하는 것입니다. (하나로 정리할 수도 있을 것 같습니다만, 이해할 때와 같이 합니다.) 여기서, 자신의 점에의 거리는 0으로 확정, ​​다른 점에의 거리는 INF로 한다.
가장자리 비용에 대한 최소값을 검색하기위한 우선 순위가있는 대기열을 준비합니다. 그리고, 자신의 점으로부터 늘어나고 있는 변을 우선도 첨부 큐에 넣는다. 이 때, 비용이 최소값 인 변의 목적지에 관해서는, 다른 변을 경유하여 보다 적은 비용이 되지 않는다. 왜냐하면 비용은 비 부정적이기 때문에 원회하게 되기 때문이다.
라고 하는 것으로, 코스트가 최소치가 되는 변을 꺼내, 이 행선지의 정점에의 최단 거리를 확정한다. 또한,이 정점에서 뻗어있는 변에 대해서도 마찬가지로 우선도가있는 큐에 넣습니다. 거리는 이 정점까지의 거리 + 변의 비용. 여기서, 최단 거리가 확정되어있는 목적지를 갖는 변에 관해서는 최단 거리에 관여하지 않기 때문에, 넣지 않게 하면 계산량이 가벼워진다.
위의 작업을 모든 최단 거리가 확정될 때까지 반복한다. (구현에서는 우선도 첨부 큐가 비게 될 때까지 하고 있습니다)

구현

import heapq
def dijkstra(s):
    # 始点から各頂点への最短距離
    d = [float('inf')]*n
    d[s] = 0
    # 各頂点が訪問済みかどうか
    used = [False]*n
    used[s] = True
    # 仮の距離を記録するヒープ
    que = []
    for e in g[s]:
        heapq.heappush(que, e)
    while que:
        u, v = heapq.heappop(que)
        if used[v]:
            continue
        d[v] = u
        used[v] = True
        for e in g[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d

입력

n = 4
g = [[[1, 1], [4, 2]], [[1, 0], [2, 2], [5, 3]], [[4, 0], [2, 1], [1, 3]], [[1, 2], [5, 1]]] # 隣接リスト
print(dijkstra(0))

출력

[0, 1, 3, 4]

계산량 해석

우선도 첨부 큐에의 추가는 변의 수에 의한 $O(E)$. 우선도 첨부 큐의 사이즈는, 변을 최단 거리가 되지 않는 경우에는 넣지 않는 것에 의해, $V$에 비례가 되므로 각 조작은 $O(logV)$. 따라서 계산량은 $O(ElogV)$.

의문

우선도 첨부 큐의 사이즈가 변의 수 $E$에 비례일까라고 생각했습니다만 가지지기로 $V$에 비례하는 곳이 조금 저항이 있었습니다. 구체적으로 내보내 보면 뭐 $E$에는 도저히 닿지 않는 것은 알 수 있습니다만 뭔가 수식등으로 간단하게 표현할 수 있으면 가르쳐 주었으면 합니다 웃음. 원래 가장자리가 모든 정점 사이에 붙어있을 때 등은 $ E∝V ^ 2 $가되어 다른 $ O (V ^ 2) $의 알고리즘보다 악화되기 때문에 생각할 필요없는 생각도합니다!

구체적인 예

위의 예입니다. 도달 가능한 정점 중에서 최소의 비용의 것을 선택해 갱신해 갑니다.

결론

향후도 비망록으로서 갱신해 가고 싶습니다. 가끔 기사를 참고문헌으로 해주는 것도 늘어났기 때문에 모치베가 오르고 있습니다.

참고문헌

프로그래밍 콘테스트 챌린지북
쥬피의 블로그