인프런 커뮤니티 질문&답변

안녕하세요 ,xk130님!

다익스트라 알고리즘에서 의문을 가질만한 점을 잘 짚어주신 것 같습니다.

강의의 예시 코드는 다익스트라 코드를 좀 더 간략하게 표현한 것이며, 사실은 아래의 코드와 같이 # 추가된 부분을 적어 주는 것이 정석적인 코드입니다. 아래의 코드에서는 음수 간선이 존재하는 경우에 다익스트라를 쓰지 못하는 이유가 이해가실 거라고 생각합니다.
편의상 강의의 예시 코드를 A, 아래의 정석적인 코드를 B라고 부르겠습니다.

while not pq.empty(): # pq.queue
    cur_dist, cur_node = pq.get()
    
    if cur_dist > dist[cur_node]: # 추가된 부분
        continue

    for adj_node, adj_dist in adj_list[cur_node]:
        temp_dist = cur_dist + adj_dist
        if temp_dist < dist[adj_node]:
            pq.put([temp_dist, adj_node])
            dist[adj_node] = temp_dist

음수 간선이 존재하지 않는 경우에 #추가된 부분을 작성하지 않은 A코드에서도 다익스트라 알고리즘이 잘 돌아갑니다. 이유: 첫 방문이 아닌 경우에 B코드에서는 cur_dist > dist[cur_node]으로 바로 걸러지지만, A코드에서는 아래의 for문을 돌며 인접한 간선을 둘러보는 작업을 하기 때문에 약간의 연산이 더 걸리게 됩니다. (하지만, for문만 수행할 뿐 최단 heap에 경로의 후보를 넣는 일은 발생하지 않습니다.) 즉, A코드는 B코드보다 상수배 정도 비효율적인 알고리즘이라고 생각하시면 됩니다.

A코드와 B코드 모두 잘 돌아가며 시간 복잡도에서도 별 차이가 없지만, A코드는 다익스트라 알고리즘을 이해하기에 헷갈림을 유발할 수 있을 거 같아, B코드로 강의 자료를 업데이트하였습니다.

강의의 예시 코드 A는 음수 간선이 존재할 때 잘 돌아갈까?

이제 강의의 예시 코드 A에서는 음수 간선이 존재하는 경우에 제대로 동작하는지 생각해 봅시다.

결론부터 말씀드리자면, 쓸 수는 있으나 시간 복잡도가 굉장히 크게 나올 수 있습니다. (즉, 이러한 경우에는 벨만-포드나 플로이드-워셜 알고리즘을 쓰는 게 더 나은 것이죠.) 시간 복잡도가 크게 나오는 이유는 다익스트라 알고리즘에서 어떤 노드가 최단 거리로 확정되는 순간은 그 노드가 heap에서 나오는 시점입니다. 하지만, 음수 간선이 존재한다면 이러한 전제가 틀리게 되는데요.

즉, 음수 간선이 존재하는 경우의 A코드(강의의 예시 코드를 의미)는 어떤 노드가 heap에서 나오더라도 그 노드까지의 다른 최단 경로가 존재할 수 있습니다. 이러한 이유 때문에 각 노드의 방문은 최단 거리로써의 방문이 1번이 아닌 여러 번을 할 수 있게 되므로 시간 복잡도가 굉장히 커지게 됩니다.

사실, A코드가 B코드에 비해 상수배 느린지에 대한 증명, A코드가 음수 간선이 존재할 때 잘 돌아간다는 타당성, 음수 간선이 존재할 때 A코드의 최악의 시간 복잡도 등에 대해 정확히 짚고 넘어가는 것이 맞지만 답변이 너무 길어질 거 같아 간단하게 답변을 드렸습니다. 위의 내용이 정확히 이해가지 않더라도 정석적인 코드B가 잘 돌아간다는 정도만 이해하고 넘어가셔도 될 것 같습니다!

혹시 제가 설명한 부분에 대해서 더 자세히 알고 싶으시다면, 추가 질문 주시면 감사하겠습니다!
더 자세한 동작 과정과 증명에 대한 디테일한 내용을 알려드리겠습니다 :)