다익스트라(Dijkstra)

필요 항목

PriorityQueue

graph[][]

dist[]

 

ex) 양방향

Vertex = n

Edge[][] = [[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]]

(u, v, cost)

 

다익스트라는 2차원 배열을 선언하여 graph[u][v] = cost 를 저장한다.

(벨만포드는 edge(u, v, cost)만 보고 2중 반복문)

int[][] graph = new int[n][n];

 

양방향이기 때문에 graph[u][v] 와 graph[v][u] 를 둘다 채워준다.

for( int[] edge... Edge ){

    int u = edge[0];

    int v = edge[1];

    int cost = edge[2];

    

    graph[u][v] = cost;

    graph[v][u] = cost;

}

 

dist = 해당 지점까지 거리

PriorityQueue.add(new int[]{해당 지점, dist[해당지점]})

 

Dijkstra(graph[][], dist[], priorityQueue, start){

    

    dist[start] = 0;

    priorityQueue.add(new int[]{start, dist[start]});

 

    while(!priorityQueue.isEmpty()){

        

        int[] pop = priorityQueue.remove();

        int now = pop[0];

 

        for( i = 0 ... vertex개수 ){

            if( graph[now][i] != 0 ){

                if( dist[i] > dist[now] + graph[now][i] ) {

                    dist[i] = dist[now] + graph[now][i];

                    priorityQueue.add(new int[]{i, dist[i]});

                }

            }

        } 

    }

}