[알고리즘] [최단거리 완전정복] 다익스트라 - 최소비용구하기

다익스트라

if(dist[to] > dist[from] + cost){   
	dist[to] = dist[from] + cost;
}

 

- D[i] = 시작 ->  i 로 가는 최단 거리

- C[i] = i가 체크되어 있으면 true, 아니면 false

 

1. 체크되어 있지 않는 정점 중에서 D의 값이 가장 작은 정점 x를 선택한다.

2. x를 체크한다.

3. x와 연결된 모든 정점을 검사한다.

• 간선을 (x,y,z)라고 했을 때
• d[y] > d[x] + z 이면 갱신해준다.

1, 2, 3단계를 모든 정점을 체크할 때까지 계속한다. 

 

- 모든정점 선택하므로(V-1) X 선택을 하는 데 걸리는 시간 O(V) = O(V^2)

 

1번 노드와 연결된 2, 5번 노트의 최단거리값을 넣어준다. 방문하지 않은 노드 중 가장짧은 곳을 다음으로 선택한다.

1 ->2 ->5 로 5번 까지의 최단거리를 3으로 바꿔준다. 1->2->4 로 4번까지의 최단거리를 10으로 바꿔준다.  

 

 

 

 

인접행렬을 이용한 구현

for(int i=1; i<=n; i++){
	dist[i] = inf;
}
dist[start] = 0;
for(int k=0; k<n-1; k++){
	int m = inf+1;
    int x = -1;
    for(int i=1; i<=n; i++){ // 선택에 되어있지 않으면서
    	if(check[i] == false && m > dist[i]){ // check가 false이고 dist[i]가 최솟값보다 작은
        	m = dist[i];
            x = i;
        }
    }
    check[x] = true; // 해당 정점을 선택
    for(int i=1; i<=n; i++){ 
    	if(dist[i] > dist[x] + a[x][i]){
        	dist[i] = dist[x] + a[x][i];
        }
    }
}
        

인접리스트를 이용한 구현

for(int i=1; i<=n; i++){
	dist[i] = inf;
}
dist[start] = 0;
for(int k=0; k<n-1; k++){
	int m = inf+1;
    int x = -1;
    for(int i=1; i<=n; i++){ // 선택에 되어있지 않으면서
    	if(check[i] == false && m > dist[i]){ // check가 false이고 dist[i]가 최솟값보다 작은
        	m = dist[i];
            x = i;
        }
    }
    check[x] = true; // 해당 정점을 선택
    for(int i=1; i<=a[x].size(); i++){
    	int y = a[x][u].to;  
    	if(dist[y] > dist[x] + a[x][i].cost){
        	dist[y] = dist[x] + a[x][i].cost;
        }
    }
}
        

 

연습문제

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

1916번: 최소비용 구하기