[Data Structure] Prim VS Dijkstra

Prim VS Dijkstra

- 전체적인 틀은 BFS와 유사

 

Prim

• 각 정점의 distance는 집합 S에 존재하는 정점과 연결하는데 발생하는 weight → 각 정점의 weight는 여러 번 바뀐다 → 시작 정점 v ~ 모든 정점에 도달하는 최소비용 계산

Dijkstra

• 시작 정점 v ~ 모든 정점까지의 최단 거리 계산

 

• Prim : 집합 S에서 해당 정점까지의 거리 (S ~ v)
• DIjkstra : 집합 S의 시작정점 r에서 해당 정점까지의 가장 짧은 거리 (S(r) ~ v)

 

 

알고리즘 비교

Prim

void prim_mst(graph* g, int v) {
	// v = 시작 정점
	init_distance(distance);
	init_selected(selected);

	distance[v] = 0; // 시작 정점 ~ 시작 정점은 당연히 distance = 0
	int cost = 0; // 비용 -> vertex가 추가될 때마다 누적

	for (int i = 0; i < g->n; i++) {
		int w = get_min_weight(g->n); // 선택된 정점( weight minimum )
		selected[w] = TRUE;
		cost += distance[w];
		printf("\n");
		printf(">> 정점 %d 추가 -> 현재 비용 : %d\n\n", w, cost);

		for (int s = 0; s < g->n; s++) {
			// w = 선택된 s의 인접 정점
			if (g->weight[w][s] != INF) {
				if (selected[s] == FALSE && g->weight[w][s] < distance[s]) {
					distance[s] = g->weight[w][s];
				}
			}
		}
	}
}

 

Dijkstra

void dijkstra(graph* g, int v) {
	init_distance(distance);
	init_selected(selected);

	int w, s; // w = v의 인접 정점, s = w의 인접 정점

	distance[v] = 0;
	g->weight[v][v] = 0;

	for (int i = 0; i < g->n; i++) {
		distance[i] = g->weight[v][i];
	}

	for (int i = 0; i < g->n; i++) {
		w = select_min(g->n);
		selected[w] = TRUE;
		printf("\n");
		printf("Step %d : 정점 %d 선택\n", i + 1, w);

		for (s = 0; s < g->n; s++) {
			if (g->weight[w][s] != INF && selected[s] == FALSE) {
				distance[s] = min(distance[s], distance[w] + g->weight[w][s]);
			}
		}
	}
}

---

Prim Code 18~22

for (int s = 0; s < g->n; s++) {
			// w = 선택된 s의 인접 정점
			if (g->weight[w][s] != INF) {
				if (selected[s] == FALSE && g->weight[w][s] < distance[s]) {
					distance[s] = g->weight[w][s];
				}
			}
		}

- 시작 정점 v, 정점 w에 대한 모든 인접 정점 s들에 대해

• s의 distance를 v~w~s가 v~s보다 작으면 v~w~s로 설정

>> distance[s] = g->weight[w][s];

 

Dijkstra Code 20~24

for (s = 0; s < g->n; s++) {
			if (g->weight[w][s] != INF && selected[s] == FALSE) {
				distance[s] = min(distance[s], distance[w] + g->weight[w][s]);
			}
		}

- 정점 w에 대한 모든 인접 정점 s들에 대해

• s의 distance를 (v~s, v~w~s) 중, 더 짧은 weight로 설정

>> distance[s] = min(distance[s], distance[w] + g->weight[w][s]);