[고급 알고리즘] Graph(Shortest Path): Dijkstra Algorithm

1. Dijkstra Algorithm 이란?

• 시작 정점으로부터 모든 정점간의 최단 경로를 찾는 알고리즘 입니다. 
• 가중치가 양수인 그래프에서 사용됩니다.

 

Greedy

• 매 단계에서 현재까지 가장 짧은 경로를 선택합니다.
• 그 경로를 바탕으로 다음 경로를 업데이트 하는 방식입니다.
• 우선순위 큐와 간선 리스트를 사용합니다.

 

2. 동작 원리

• 교차점마다 출발지로부터의 거리를 기억하여 도착지와의 최단 거리를 찾는 방식입니다.

 

Initialization

• 모든 교차점의 거리를 무한대로 설정합니다. (해당 교차로로 가는 경로가 없음을 의미)
• 출발지의 거리를 0으로 설정합니다. (자기 자신에서 출발하므로)

 

Search & Memorization

• 출발지로부터 각 교차점까지의 최단 거리를 찾아내고 이 정보를 저장합니다.
• 각 교차점에 기록된 거리 값은 출발지로부터 해당 교차점까지 최단 거리를 나타냅니다.

 

Relaxation

• 각 이웃 정점까지의 경로를 재검사 및 필요 시 업데이트
  • 현재 위치와 연결되어 있는 모든 이웃 정점의 경로를 확인
  • 더 짧은 경로가 있다면 그 경로로 거리 값을 갱신합니다.

 

교차점 정보

• T : 현재 위치
• A : 현재 위치까지 최단 거리
• B : 이웃 교차로까지의 도로 길이
• C : 이웃 교차로에 기록된 최단 거리

 

동작

• A + B  < C 이면 C를 A + B로 갱신합니다.
• 이는 T를 거쳐 C를 가는 것이, 기존에 알려진 경로보다 더 짧다는 것을 의미합니다.

 

Repeat

모든 교차점 방문

• 모든 교차점을 방문할 때까지 위의 탐색 및 완화 과정을 반복합니다.

 

최단 거리 정보 유지

• 반복과정 동안 각 교차점에 대한 최단 거리 정보는 지속적으로 업데이트됩니다.
• 이를 통해 최신 상태의 최단 거리 정보가 유지됩니다.

 

최종 결과 도출

• 이 반복 과정을 통해, 출발지로부터 모든 교차점까지의 최단 거리를 찾아낼 수 있습니다.

 

3. 구현

static class Edge implements Comparable<Edge> {
    final int dest, weight;

    public Edge(int dest, int weight) {
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.weight, o.weight);
    }
}

private static void dijkstra(int start) {
    Arrays.fill(minDist, Integer.MAX_VALUE);
    visitBit.clear();

    minDist[start] = 0;
    pq.offer(new Edge(start, 0));

    while (!pq.isEmpty()) {
        Edge curE = pq.poll();
        int stopover = curE.dest, toStopOverD = curE.weight;
        int minStopOverD = minDist[stopover];

        if (toStopOverD > minStopOverD) continue;
        if (visitBit.get(stopover)) continue;
        visitBit.set(stopover);

        for (Edge destE : edges.get(stopover)) {
           int dest = destE.dest, toDestD = destE.weight;
           int newD = minStopOverD + toDestD;
           if (newD >= minDist[dest]) continue;

           minDist[dest] = newD;
           pq.offer(new Edge(dest, newD));
        }
    }
}

 

 

출처

• Wiki - Dijkstra Algorithm