다익스트라 알고리즘 : Dijkstra Algorithm

다익스트라 알고리즘 : Dijkstra Algorithm

그래프에서 특정 꼭짓점에서 다른 모든 꼭짓점 간의 최단 경로를 찾는 알고리즘

시간 복잡도

1. 우선순위 큐를 사용하지 않는 경우 : O(V^2)

2. 우선순위 큐를 사용하는 경우 : O(ElogV)

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
 
public class Dijkstra {
 
    // 정점의 개수
    public static int V = 9;
    
    // 최소 거리를 갖는 점
    public static int getMinVertex(int[] dist, boolean[] visit) {
        int index = 0;
        int minDist = Integer.MAX_VALUE;
        for(int i=0; i<dist.length; i++) {
            if(!visit[i] && minDist>dist[i]) {
                minDist = dist[i];
                index = i;
            }
        }
        return index;
    }
    
    // 그래프로 이차원 배열로 나타냈을 때의 다익스트라
    public static int[] dijkstra(int[][] graph, int source) {
        int[] dist = new int[V];
        boolean[] visit = new boolean[V];
        
        for(int i=0; i<V; i++) {
            dist[i] = Integer.MAX_VALUE;
            visit[i] = false;
        }
        dist[source] = 0;
        
        for(int i=0; i<V; i++) {
            int u = getMinVertex(dist, visit);
            visit[u] = true;
            
            for(int j=0; j<V; j++) {
                if(graph[u][j]!=0 && !visit[j] && dist[j]>dist[u]+graph[u][j]) {
                    dist[j] = dist[u]+graph[u][j];
                }
            }
        }
        return dist;
    }
    
    // 연결리스트와 우선순위 큐를 사용한 다익스트라
    public static int[] dijkstraWithPQ(List<int[]>[] adj, int source) {
        int[] dist = new int[V];
        for(int i=0; i<dist.length; i++) dist[i] = Integer.MAX_VALUE;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] arg0, int[] arg1) {
                return Integer.compare(arg0[1], arg1[1]);
            }
        });
        
        // {다음 정점, 다음 정점까지의 거리}
        pq.add(new int[] {source, 0});
        dist[source] = 0;
        while(!pq.isEmpty()) {
            int[] cur = pq.poll();
            
            if(dist[cur[0]]<cur[1]) continue;
            
            for(int i=0; i<adj[cur[0]].size(); i++) {
                int[] next = adj[cur[0]].get(i);
                if(dist[next[0]]>cur[1]+next[1]) {
                    dist[next[0]]=cur[1]+next[1];
                    pq.add(new int[] {next[0], cur[1]+next[1]});
                }
            }
        }
        
        
        return dist;
    }
    
    public static void main(String[] args) {
        List<int[]>[] adj = new List[V];
        int[][] graph = new int[][] {
            { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
            { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, 
            { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, 
            { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, 
            { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, 
            { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, 
            { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, 
            { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, 
            { 0, 0, 2, 0, 0, 0, 6, 7, 0 }            
        };
        for(int i=0; i<graph.length; i++) {
            adj[i] = new ArrayList<int[]>();
            for(int j=0; j<graph[i].length; j++) {
                if(i!=j && graph[i][j]!=0)
                    adj[i].add(new int[] {j, graph[i][j]});
            }
        }
        int[] dist = dijkstra(graph, 0);
        System.out.println(Arrays.toString(dist));
        dist = dijkstraWithPQ(adj, 0);
        System.out.println(Arrays.toString(dist));
    }
}