글 읽기 - 다익스트라 알고리즘은 음수 간선이 존재할 때 사용 할 수 없다?

hellowfriend 1년 전 1

아래 코드는 다익스트라 알고리즘입니다.

다익스트라 알고리즘은 음수 간선이 있으면 사용하지 못한다고 보통 설명되있던데,

음수 간선은 되고 음수 순환이 안되는 것 아닌가요?

예를 들어서,

A -> B, cost: 1

A -> C, cost: 10

C -> B, cost: -100

인 그래프가 있을 때,

다익스트라 알고리즘을 실행하면

먼저, 시작점이 A 노드에 대해서 처리하니까

dist[B] = 1, dist[C] = 10이 되고,

우선순위 큐에 (1, B), (10, C) 순으로 정렬이 되고,

이후 (1, B)가 우선순위 큐에 빠져나오고 인접 노드가 없으니,

우선순위큐에 (10, C)가 남고,

이후 (10, C)가 우선순위 큐에서 빠져나오면서 C의 인접 노드 B에 대해서 처리하면서,

dist[C] + (-100) < dist[B]이므로, dist[B]는 -90으로 갱신.

따라서, dist[A] = 0, dist[B] = -90, dist[C] = 10으로 음수 간선이 존재할 때도 사용할 수 있는 것처럼 보여서 혼란스럽네요.

void dijk(int start)
{
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; 
    q.push({ dist[start], start });
    while (!q.empty()) {
        int cur = q.top().second;
        int curDist = q.top().first;
        q.pop();
        
        if(curDist > dist[cur]) continue; 
        
        for (int i = 0; i < v[cur].size(); i++) {
            int next = v[cur][i].first;
            int nextDist = v[cur][i].second;
            if (dist[next] > curDist + nextDist) {
                dist[next] = curDist + nextDist;
                q.push({ dist[next],next });
            }
        }
    }
}

pmn0001 1년 전 2

저도 작성자님의 질문글을 보고 궁금해서 찾아봤는데요. 아래 링크를 참고하니 이해가 잘 됐습니다.

https://kangworld.tistory.com/...

다익스트라는 그리디 알고리즘으로 최단거리를 구하는 알고리즘인데, 핵심 아이디어는 최단 거리에 최단 거리를 더해서 최종 거리를 구합니다.

근데 작성자님의 말씀대로면 최단 거리에 최단 거리를 더한게 아니게 되므로 아이디어가 깨지게 된다네요.

근데 구현방식에 따라 최단거리를 구할 수도 있다는건 첨 알았네요ㅎㅎ

djs100201 1년 전 1

시간복잡도가 보장이 안됩니다.
https://www.acmicpc.net/proble...
위 문제에서도 알 수 있듯이..

hellowfriend 1년 전 0

pmm0001님. 저도 그 아이디어와 구현방식이 작동하는 순서가 차이가 있는데 그 차이에 대한 설명을 해논 글이 없어서 많이 당황스럽더라구요ㅠㅠ.

djs100201님 그럼 위와 같은 코드로 다익스트라가 구현됬을 때, 그래프에 음수 순환 말고, 음수 간선만 존재해도 말그대로 O(|E||log|V|)의 시간복잡도가 보장이 안된다는 말씀이신거죠?

제가 당장 확인하기가 어려워 미리 무슨 말씀인지 확실히 여쭤보고 나중에 시간될 때 확인해보려고요.

혹시 위의 코드말고 다른 방식으로 다익스트라 알고리즘을 구현하는 방법들이 있을까요?

제가 인터넷을 찾아본다고 찾아본 것 같은데 위와 같은 코드 밖에 찾질 못해서 여쭤봅니다.

다들 답변해주셔서 정말 감사합니다.

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

문제

문제

출처

ICPC

다익스트라 알고리즘은 음수 간선이 존재할 때 사용 할 수 없다?

hellowfriend 1년 전 1

pmn0001 1년 전 2

djs100201 1년 전 1

hellowfriend 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말