다익스트라

1. 다익스트라

- 음수 가중치가 없는 그래프에서 시작 정점에서 다른 정점으로 최단 경로를 구하는 알고리즘

- 우선순위 큐를 활용하여 구현

- 기본동작

 . 모든 정점의 거리를 무한대로 설정

 . 출발점에서 주변의 정점들을 방문하며 거리 갱신

 . 미방문 정점 중 가장 거리가 짧은 정점 선택

 . dist[A] + Edge[A,X] <= dist[X] 이면 거리 배열을 갱신

 . 모든 정점을 방문하였으면 알고리즘 종료, dist[정점]이 A부터 정점까지의 최소거리

public void dijkstra() {
	int[] dist = new int[num];
    for(int i = 0; i< dist.length; i++){
    	dist[i] = INF;
    }
    
    PriorityQueue<V> pq = new PriorityQueue<>();
    
    dist[start] = 0;
    pq.add(new V(0,0));
    
    while(!pq.isEmpty()) {
    	int curV = pq.poll().vertex;
        
        for(V v:adjList[curV]) {
        	int next = v.vertex;
            
            if(dist[curV] + v.distance < dist[next]) {
            	dist[next] = dist[curV] + v.distance;
                pq.add(new V(next, curV + v.distance));
            }
        }
     }
  }

 

클래스 만들기

public static class nc{
	int node, cost;
    
    public nc(int node, int cost){
    	this.node = node;
        this.cost = cost;
    }
}

 

클래스로 ArrayList 만들기

private static ArrayList<nc>[] edgeList;

edgeList = new ArrayList[N+1];
for(int n = 1; n <= N; n++){
	edgeList[n] = new ArrayList<>();
}

for(int i = 1; i <= I; i++){
	st = new StringTokenizer(br.readLine());
    a = Integer.parseInt(st.nextToken());
    b = Integer.parseInt(st.nextToken());
    c = Integer.parseInt(st.nextToken());
    
    //Two way
    edgeList[a].add(new nc(b,c));
    edgeList[b].add(new nc(a,c));
}

 

다익스트라 함수와 PriorityQueue 구현

public static void dijkstra(){
	//ascending
    PriorityQueue<nc> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
    
    pq.add(new nc(1,0));
    
    
    while(!pq.isEmpty()){
    	nc now = pq.poll(); // 위에서 넣은 첫번째 값이 선택됨
        visited[now.node] = true;
        
        if(now.node == N) break;
        if(distance[now.node] < now.cost) continue;
        
        for(nc next : edgeList[now.node]){
        	if(distance[now.node] + next.cost < distance[next.node] && ! visited[next.node]){
            	distance[next.node] = distance[now.node] + next.cost;
                pq.add(new nc(next.node, distance[next.node]));
            }
        }
    }
}

 

백준 1916

문제 : https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

풀이 : https://machine-geon.tistory.com/158

[BAEKJOON_1916 - JAVA] 최소비용 구하기