[TIL] 다익스트라 : 가중치로 0이 들어온다면

참고 문제

https://www.acmicpc.net/problem/17182

 

포스팅 목적

플로이드 워셜과 다익스트라의 개념을 알고 있다면 두 개를 혼용해서 사용할 수 있는걸 알 수 있습니다.

그래서 위 문제 풀이를 위해 플로이드 워셜이 아닌 다익스트라를 N번 수행했습니다.

다익스트라 코드는 평소와 같이 작성을 했지만 제출했을 때 메모리 초과가 발생하여 이유를 찾는 과정에서 다음번에도 실수할 수 있을 것 같은 반례를 찾아서 기록하기 위해 작성합니다.

---

최초 다익스트라 코드

static void Dijkstra(int start) {
    PriorityQueue<int[]> pq = new PriorityQueue<>(((o1, o2) -> o1[1] - o2[1]));
    pq.offer(new int[]{start, 0});

    while(!pq.isEmpty()) {
        int[] cur = pq.poll();

        if(dist[start][cur[0]] < cur[1]) continue;
        dist[start][cur[0]] = cur[1];

        for(int i=0; i<N; i++) {
            if(cur[0] == i) continue;
            pq.offer(new int[]{i, cur[1] + map[cur[0]][i]});
        }
    }
}

코드설명

시작 정점으로부터 모든 정점까지의 최소 거리를 구하는 로직입니다.

여기서 주의해야하는 부분은 if(dist[start][cur[0]] < cur[1]) continue; 입니다.

기존 비용보다 큰 비용에 대해서는 탐색하지 않는 로직으로 구성했습니다.

일반적인 다익스트라의 경우 같은 비용에 대해서도 탐색을 해야 최단경로를 구할 수 있기 때문에 위 코드처럼 작성했습니다.

---

문제의 반례

2 0
0 0
0 0

 

설명

다익스트라 특성 상 dist배열에 대해 최대값으로 갱신합니다.

또한 시작 정점으로부터 각 정점까지의 거리를 계속 갱신하며 최소비용을 탐색해나갑니다.

 

그러나 위의 코드로 해당 예제를 수행하면 무한루프가 발생하는 것을 알 수 있습니다.

이유로는 각 정점까지의 최소비용은 0이며, 계속 탐색을 진행해도 0보다 커지는 일은 없기 때문입니다.

 

가중치가 전부 0으로 들어오는 상황을 고려하면,

if(dist[start][cur[0]] < cur[1]) continue; 가 아닌

if(dist[start][cur[0]]<=cur[1]) continue; 처럼 작성을 해야 위 반례에서 제대로된 값을 구할 수 있습니다.

 

정리

다익스트라를 통해 특정 정점에서 다른 정점까지의 최단경로를 갱신할 때, 가중치의 범위가 0이 나올 수 있는 경우 조건문에 따라 무한루프가 발생할 수 있습니다.

따라서 위 반례의 경우를 주의해야하고, 입력값을 확실하게 체크해야합니다.

 

웹에 퍼져있는 다익스트라 코드를 확인했을 때 조건문에 등호가 없는 경우가 많은데, 웬만한 경우에는 등호를 붙여주는게 다익스트라 알고리즘의 안전성을 높여줄 수 있을 것 같습니다.