[알골90제] 80번 - 다익스트라 알고리즘

 

1. 노드 배열을 만들어서 1번 정점은 0으로 초기화하고 나머지는 무한대값(아주큰값)으로 최대한 해놓음

2. 돌면서 최솟값을 찾음

3. 1번정점 체크

 

4. 1번 정점에서 갈 수 있는 방향으로 다 간다.

5. dist 배열을 relax해준다. => 값이 더 좋으면 바꿔준다.

6. dist[2] 를 보면 무한대로 되어 있기 때문에 가중치값 12는 좋은 값이기에 바꿔준다 dist[2] = 12

7. 1번에서 3으로 갈 수 있다. => dist[3] = 4 로 바꿔준다.

 

8. 1번은 한번 사용했기 때문에 다시 사용 못함

9. 2, 3번 중 작은 값인 3번이 선택됨 => dist[3]은 체크 걸어둠. 그리고 이제 dist[3] 인 3번 정점에서 다시 감

10 .1에서 3번 정점으로 가는 최솟값인 4는 선택되었기에, 더는 바뀔수없다.

11. 2번 정점은 확정값이 아님 왜냐면 dist 배열에서 아직 dist[3] 의 4가 제일 적은 수 이기 때문에 3번 정점만 확정

 

=>> 3번 정점에서 갈 수 있는 곳 똑같이 보기

 

1. 3에서 4로 가는 정점은 5이기 때문에 기존 dist에 있는 무한대 값보다 좋은 값이 기에 4+5인 9를 dist[4] 에 넣어준다.

 

 

//80번 - 다익스트라 알고리즘
//출발정점에서 다른 모든 정점으로 가는 최소비용을 알려줌

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<pair<int, int> > map[30];
int ch[30], dist[30];

int main() {

	freopen("input.txt", "rt", stdin);
	
	int n, m, a, b, c, min;
	scanf("%d %d", &n, &m);

	//방향그래프 인접리스트 만들기
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		map[a].push_back(make_pair(b, c));
	}

	//첫번째 배열 0 나머지 무한대값으로 초기화
	for (int i = 0; i <= n; i++) dist[i] = 999999999;
	dist[1] = 0;

	for (int i = 1; i <= n; i++) {
		min = 0;

		//dist배열중 제일 작은 원소값 찾기
		for (int j = 1; j <= n; j++) {
			if (ch[j] == 0 && dist[j] < dist[min])
				min = j; //j는 정점
		}
		ch[min] = 1; //제일 작은 값은 체크

		for (int j = 0; j < map[min].size(); j++) {
			//min정점에서 갈 수 있는 모든값 탐색
			int v = map[min][j].first;
			//비용
			int cost = map[min][j].second;

			//기존보다 작으면 바꿔줘라
			if (dist[v] > dist[min] + cost) { //1번정점에 min까지 가는 비용 + min에서 v라는 정점까지 가는 비용
				dist[v] = dist[min] + cost;
			}
		}
	}
	
	for (int i = 2; i <= n; i++) {
		if (dist[i] != 999999999) printf("%d : %d\n", i, dist[i]);
		else printf("%d : impossible\n", i);
	}
	return 0;
}