다익스트라 알고리즘

다익스트라 알고리즘

📄 설명

다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 거리를 찾는 알고리즘입니다.
음수 가중치가 있는 그래프에서는 정확한 최단 거리를 구할 수 없으므로 사용하면 안됩니다.(그럴 땐 벨만-포드)

단일 정점에서 다른 정점으로의 최단거리를 구하는 알고리즘이기 때문에 모든 정점들 간의 최단거리를 알고 싶다면 플로이드-와샬 알고리즘을 사용하는 것이 구현이 편합니다

우선순위큐를 이용한 정렬을 이용하기 때문에 O(ElogV)의 시간 복잡도를 가지게 됩니다.

---

💡동작 과정

1. 각각의 정점마다 현재까지 발견한 최소 경로를 저장할 dist 배열을 만듭니다. 최단 경로를 구해야 하기 때문에 처음에는 모든 값을 아주 큰 값으로 초기화 시킵니다. 여기서는 1번 정점을 시작점으로 정했기 때문에 dist[1] = 0으로 초기화 해주었습니다.

   

2. 1번 정점과 연결되어 있는 정점들의 dist 배열을 갱신시켜 줍니다. 이 때 현재까지의 거리 + 다음 정점까지의 간선 거리 가 dist[다음정점] 보다 작다면 dist 배열을 갱신시키고 우선순위 큐에 넣습니다.

   

3. 현재 상황일 때 2번 정점에서 3번 정점으로 가는 경로는 2 + 5 > 4 이기 때문에 스킵하게 됩니다

4. 4번 정점 갱신

   

5. 5, 6번 정점 갱신

   

6. 마지막에 dist배열에 저장되어 있는 값들이 각 정점들까지 가는 최단 경로가 됩니다.

---

⌨️ 코드

public static int[] Dijkstra() {
    PriorityQueue<Edge> pq = new PriorityQueue<>();
    int[] dist = new int[N + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[S] = 0;
    pq.offer(new Edge(S, 0));
    while(!pq.isEmpty()) {
        Edge cur = pq.poll();
        if(cur.weight > dist[cur.to]) continue;
        for(int i = 0; i < adj[cur.to].size(); i++) {
            int next = adj[cur.to].get(i).to;
            int nextDistance = adj[cur.to].get(i).weight + cur.weight;
            if(nextDistance < dist[next]) {
                dist[next] = nextDistance;
                pq.add(new Edge(next, nextDistance));
            }
        }
    }
    return dist;
}