글 읽기 - dijkstra 에서 cycle 생성 시 최단거리 갱신하는 경우

silence1230 2년 전 1

벨만 포드의 시간 복잡도가 O(EV) 인데,

dijkstra에서 방문했던 node들을 set에 담아서 저장하고,

최단 거리를 갱신할 때, 현재 node가 이미 방문한 node라면,

음의 순환이 발생한 것으로 간주하고 -1을 반환하도록 했습니다.

이렇게 하면 시간복잡도가 dijkstra와 동일한 O(ElogV)가 될 거라고 생각했는데,

실제로 검사해보니 약 45%에서 시간 초과가 발생했습니다.

혹시 어떤 부분에서 문제가 발생하는 지 알 수 있을까요?

set의 메모리 계산 비용이 너무 커서 그런 것인가 하고 짐작 중이긴 한데,

확실하게 확인할 방법이 없어 질문 드립니다.

# my (python3)
# dijkstra 응용
# heapq 에 기존 방문한 node들 정보를 set에 담아 추가해서
# 기존 최단거리보다 작으면서, cycle 이 발생하는 경우 -1 반환
import sys
input = sys.stdin.readline
from heapq import heappop, heappush
import math

def sol(n: int, m: int) -> str:
    INF = math.inf
    isinf = math.isinf

    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b,c = map(int, input().split())
        graph[a].append((c,b))
    
    dijkstra_one = [INF]*(n+1)
    dijkstra_one[1] = 0
    q = [(0,1,{1})]

    while q:
        p_w,p_n,v_nodes = heappop(q)
        if p_w > dijkstra_one[p_n]:
            continue
        for c,b in graph[p_n]:
            if p_w+c < dijkstra_one[b]:
                if b in v_nodes:
                    return -1
                dijkstra_one[b] = p_w+c
                heappush(q, (dijkstra_one[b],b,v_nodes|{b}))
    
    return '\n'.join(map(lambda x: '-1' if isinf(x) else str(x), dijkstra_one[2:]))


print(sol(*map(int, input().split())))

shjohw12 2년 전 0

간선의 가중치가 음수라서 다익스트라로 못하지 않나요?

shjohw12 2년 전 1

정확히는 O(ElgV)가 보장되지 않습니다.

silence1230 2년 전 0

지난 경로에서 이미 방문했던 노드를 다시 방문할 때,

출발점에서 그 노드까지 최단 거리를 갱신하게 된다면,

음의 순환이 발생하는 것으로 판단하고

-1을 반환하도록 코드를 짰습니다.

테스트 케이스 몇 개로 확인해본 결과 답이 틀리진 않아서,

이 아이디어가 자체가 틀리진 않았다고 생각하는데,

시간 초과가 발생하네요;;

silence1230 2년 전 0

O(ElgV)와 O(EV) 사이에 있을 것 같아서,

벨만 포드보다는 빠를 것 같았는데,

그게 아닌 거 같아서 고민 중이에요 ㅠㅠ

shjohw12 2년 전 0

음의 사이클을 찾는 로직은 이해가 되지 않아서 둘째 치고, 최악의 경우에 O(VE)보다 훨씬 느릴 것입니다

silence1230 2년 전 0

답변 감사합니다

음의 사이클은

다익스트라 특성상 하나의 경로에서

이전에 방문했던 노드를 새로운 최단 거리를 갖고 다시 방문한다면

사이클을 형성해서 결국 그 노드에서 출발해서 더욱 짧은 최단 경로로 다시 그 노드로 돌아올 것이다

라고 생각했습니다.

혹시 log(EV) 보다 시간복잡도가 훨씬 나쁜 케이스가 어떤게 있을까요?

y2kdj9723 1년 전 0

새로운 최단거리를 가지고 방문 하더라도 음수 사이클이 발생하지 않는 경우를 예로 들을 수 있을 것 같습니다

그래프 이미지 링크

위 이미지를 보시면,

다익스트라 알고리즘을 사용하였다면

a -> c로 가는데 4

a -> b로 가는데 10

현재 최단거리 상태 [0, 4, 10]

하지만 b -> c 로 갈 때 -90의 최단거리를 갖고

c까지의 최단거리는 -90이지만 음수 싸이클은 발생하지 않습니다

한마디로 표현하자면 간선에 방향성도 존재하기 때문에 음수 싸이클에 대한 깊은 고민이 더 필요할 것 같습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dijkstra 에서 cycle 생성 시 최단거리 갱신하는 경우

silence1230 2년 전 1

shjohw12 2년 전 0

shjohw12 2년 전 1

silence1230 2년 전 0

silence1230 2년 전 0

shjohw12 2년 전 0

silence1230 2년 전 0

y2kdj9723 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말