Prim's Algorithm, Dijkstra's Algorithm

Various Costs for a Graph G = (V, E)

 

 

임의의 정점 u, v 가 존재할 때 u에서 v로 가는 경로를 찾을때,

Adjacency list : O(|V| + |E|), 정점을 전부 탐색하면서 연결된 간선들을 탐색한다.

Adjacency matrix : O(|V|^2), 서로 연결된 경우가 1이므로 1인 경우를 모두 탐색한다.

 

 

Prim's Minimum Spanning Trre Algorithm

 

Idea

– In each step, find and add an edge of the least possible weight that connects the (current) tree

   to a non-tree vertex. 

Algorithm

 

 

 

꼭짓점들의 집합을 partition 하는 방식이다.

먼저 partition 한 다음에 cross 하는 edge들을 일단 다 고려하고 해당하는 모든 edge 중에 가장 작은걸 선택하여

해당 정점으로 이동한다. (한쪽은 항상 뭉쳐있으면서 자라는 형태)

위 방법을 n - 1 개의 edge가 선택될 때까지 반복하면 된다.

 

 

An O(n^2) Implementation : Adjacency Matrix 사용

 

인접 행렬을 이용하여 O(n^2) 에 대한 구현을 해보도록 한다.

 

 

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define MAXV 10
#define MAXWT 1000000000

struct Graph {
	int V;
	int E;
	int adj[MAXV][MAXV];
};

static int fr[MAXV];
#define P G->adj[v][w]

void GRAPHmstV(Graph *G, int st[], int wt[]) {
	int v, w, min, n = G->V;
	for (v = 0; v < n; v++) {
		st[v] = -1, fr[v] = v, wt[v] = MAXWT;
		// st[v] = T로 선택된 vertex v의 부모 노드
		// fr[v] = NT에 있는 vertex v에서 가장 가까운 vertex 번호
		// wt[v] = NT에 있는 vertex v에서 fr[v] 까지의 weight
	}
	
	wt[n] = MAXWT; // dummy node
	for (min = 0; min != n;) {
		v = min, st[min] = fr[min];
		for (w = 0, min = n; w < n; w++) {
			// NT에 속한 vertex w를 탐색한다.
			if (st[w] == -1) {
				// w에서 v까지의 거리가 w에서 fr[w]까지의 거리보다 짧을 경우
				if (P < wt[w]) {
					wt[w] = P, fr[w] = v;
				}
				// 인접한 모든 정점들 중에서 거리가 가장 작도록 하는 정점을 선별
				if (wt[w] < wt[min]) {
					min = w;
				}
			}
		}
	}

	for (v = 0; v < MAXV; v++) {
		if(wt[v] == MAXWT)
			printf("%d(%c) : st[%d] = %d, fr[%d] = %d, wt[%d] = maxWT\n",
				v, ('a' + v), v, st[v], v, fr[v], v);
		else
			printf("%d(%c) : st[%d] = %d, fr[%d] = %d, wt[%d] = %d\n",
				v, ('a' + v), v, st[v], v, fr[v], v, wt[v]);
	}
}

int main() 
{
	Graph* G;
	int i, j;
	int st[MAXV + 1], wt[MAXV + 1];

	G = (Graph*)malloc(sizeof(Graph));
	G->V = 10;
	G->E = 38;
	for (i = 0; i < G->V; i++) {
		for (j = 0; j < G->V; j++) {
			G->adj[i][j] = MAXWT;
		}
	}

	G->adj[0][1] = G->adj[1][0] = 33;
	G->adj[0][2] = G->adj[2][0] = 10;
	G->adj[0][3] = G->adj[3][0] = 56;

	G->adj[1][3] = G->adj[3][1] = 13;
	G->adj[1][4] = G->adj[4][1] = 21;

	G->adj[2][3] = G->adj[3][2] = 23;
	G->adj[2][5] = G->adj[5][2] = 24;
	G->adj[2][6] = G->adj[6][2] = 65;

	G->adj[3][4] = G->adj[4][3] = 51;
	G->adj[3][6] = G->adj[6][3] = 20;

	G->adj[4][6] = G->adj[6][4] = 17;
	G->adj[4][7] = G->adj[7][4] = 35;

	G->adj[5][6] = G->adj[6][5] = 40;
	G->adj[5][8] = G->adj[8][5] = 72;

	G->adj[6][7] = G->adj[7][6] = 99;
	G->adj[6][8] = G->adj[8][6] = 45;
	G->adj[6][9] = G->adj[9][6] = 42;

	G->adj[7][9] = G->adj[9][7] = 38;

	G->adj[8][9] = G->adj[9][8] = 83;

	GRAPHmstV(G, st, wt);

	return 0;
}

 

 

T는 선별된 정점들의 집합이고 NT는 선별되지 않은 정점들의 집합이다.

st[v] : T로 선택된 v의 부모노드

fr[v] : NT로 선택된 v중에서 T에 있는 vertex 중 가장 가까운 vertex의 번호

wt[v] : NT에 있는 vertex v에 대해 그 vertex에서 fr[v] 까지의 거리

 

 

An O(e log n) Implementation : Adjacency List 사용

 

 n = |V|, e = |E| 일 때, 이번엔 인접 리스트를 활용하여 O(E log V) 에 대한 구현을 해보도록 한다.

 

 

 

P를 t->wt 라고 정의했을때 위 코드를 분석해보도록 한다.

처음에 st[v] = -1, fr[v] = -1 으로 초기화 할 때 인접 행렬과는 다르게 초기화 하는 것을 알 수 있다.

(인접 행렬에서는 fr[v] = v 으로 초기화)

 

먼저 fr[w = t->v] == -1 에 대한 조건문을 만족하지 못한 경우이다.

이는 즉, NT에 속해있는 정점 w가 T에 속해있는 vertex 중에 가장 가까운 경우를 발견하지 못한 것이므로

wt[w] = P : NT에 속한 정점 w에서 T에 속한 정점 v로 거리를 설정

PQinsert(w) : NT에 속한 정점 w를 삽입

fr[w] = v : NT에 속한 정점 w를 T에 속한 정점중 가장 가까운 정점 v로 설정

 

그리고 위 조건을 만족하지 못할 때 (st[w] == -1) && (P < wt[w]) 일 경우

wt[w] = P, PQdec(w), fr[w] = v; 를 하는 과정을 생각해보도록 하자.

해당 조건은 st[w] == - 1 일 경우 정점 w에 NT에 속하는 경우임을 알 수 있다.

그리고 동시에 P < wt[w] 일 경우 v에서 w로의 거리가 기존에 저장된 wt[w] 즉, fr[w] 까지의 거리보다 더 

가까운 경우를 발견하게 될 경우 기존에 있던 wt[w], fr[w] 에 대한 최신화가 필요하다.

따라서 wt, fr에 대한 배열 값을 변경해주고 PQdec(w) 를 호출해준다.

 

 

Dijkstra's Single-Source Shortest Path Algorithm

 

 

 

• A directed graph with nonnegative weight G(V, E) with w: E → [0,∞) and source s

• Two components for each vertex v

– v.d: an upper bound on the weight of a shortest path from s to v (a shortest path estimate)

– v.π: the predecessor of v in the (current) shortest path

 

다익스트라 알고리즘은 방향 그래프로 음수가 아닌 가중치를 가지는 것을 알아두자.

v.d 는 s에서 v까지의 shortest path의 가중치에 대한 상한 값을 나타내고

v.π 는 v의 shortest path 중에서 이전 값을 나타낸다.

먼저 v.d = INF, v.π = NIL 으로 초기화 함으로써 source s에서 destination t 까지의 거리를 미리 INF 으로

초기화 하고 NIL 으로 초기화 해준다.

그리고 s.d = 0 을 함으로써 시작 지점에서의 거리는 반드시 0이여야 하므로 0으로 초기화 해준다.

 

 

• Relaxation

– The process of relaxing an edge (u, v) consists of testing whether we can improve the shortest path

to v found so far by going through u and, if so, updating v.d and v.π.

 

edge (u, v)를 relaxing 하는 프로세스는 u를 통해 지금까지 발견된 v에 대한 최단 경로를 개선할 수 있는지 여부를

테스트하고, 개선 가능할 경우 v.d 및 v.π를 업데이트 해준다.

 

 

기존에 v.d = 106 이였다.

그러나 u.d + w(u, v) = 53 + 45 = 98 으로 v.d 의 값을 relaxing 할 수 있는 경우가 나타난 것이다.

이 경우 v.d 값을 u.d + w(u,v) 값으로 변경해주면서 v.π 값을 u 로 설정해준다.

 

 

• Dijkstra’s algorithm

– Maintains a set S of vertices whose final shortest-path weight from the source s have already

    been determined.

– 1. Select repeatedly the vertex u in V-S with the minimum shortest-path estimate,

   2. adds u to S, and

   3. relaxes all edges leaving u.

 

 

알고리즘을 살펴보도록 하자.

1. 먼저 그래프 G와 source s 에 대한 Initialization 이 이루어 진다.

2. S = empty set, Q = V - S = G.V 으로 Q 가 empty set이 될 때까지 while-loop 를 실행하도록 한다.

3. 집합 Q에 속한 정점 v 중에 source에서 정점 v 까지의 거리 중 최소가 되도록 하는 v를 찾아서 u에 넣어준다.

    즉 Q = {v1, v2, ..., vm} 이라고 할 때, min(d.v1, ..., d.vm) 값을 만족하는 vi 는 u 가 된다.

4. 집합 S에 union 해주고 정점 u에 속한 인접한 모든 노드를 탐색하면서 Relaxing 해준다.

5. Q 가 empty set이면 종료하고 아닐 경우 3 번째로 이동한다.   

 

➢ When the algorithm adds a vertex u to the set S, u.d is the final shortest-path weight from s to u.

 

즉, 위 알고리즘의 3번째 단계에서 구한 정점 u는 s에서 u까지의 마지막 최단 경로의 가중치이다.

따라서 S에 union 해줘서 relaxing 하는 과정을 거치는 것을 알아두도록 하자.

 

 

 

• Correctness of Dijkstra's algorithm

 

v.d = δ(s, v) 일 때 source s에서 정점 v로의 최단 경로가 완성 된다는 것을 짐작할 수 있겠다.

 

– Loop invariant

 

– A key in the proof

집합 S에 u를 넣는 순간 u.d = δ(s, u) 가 된다는 것은 위에서 확인하였다.

즉, 집합 S에 속하는 경우가 결국 최단 경로의 가중치라는 것이며 δ(s, u)가 source s에서 정점 u까지의

최단 경로의 가중치 값을 갖는다는 것을 알 수 있다.

 

 

An O(n^2) Implementation : Adjacency Matrix 사용

 

 

인접행렬로 구현한 다익스트라 코드이다.

shortestpath() 함수에 대한 분석을 해보도록 하자.

먼저 parameter 로 받아온 변수들에 대해 알아보도록 한다.

v : source 를 의미한다.

cost[][MAX_VERTICES] : 인접 행렬로 정점들 사이의 거리를 의미한다.

distance[] : source에서 임의의 정점까지의 shortest path의 weight 을 나타낸다.

n : 정점의 갯수를 의미한다.

found[] : 집합 S에 속해있는지에 대한 여부를 판단하는 배열이다.

 

 

먼저 시작지점 v부터 모든 정점들에 대한 weight 값을 distance 배열에 넣어준다.

이때 연결되지 않은 경우 INF 값이 된다.

그리고 시작 지점을 집합 S에 union 하여 distance[v] = 0 으로 시작 지점의 최소 가중치 0을 설정한다.

 

 

일단 집합 S에 시작 지점을 추가하였으므로 마지막 지점을 제외한 모든 지점에서 relaxing 하는 경우의 수는

총 (n - 2) 개이므로 for문을 통해 (n - 2)번 실행하는 것을 짐작할 수 있다.

 

일단 choose 함수를 살펴보도록 하자.

choose 함수는 집합 Q = V - S 의 정점에 대해서 source에서 해당 정점까지의 거리 중 가장 최소가 되도록 하는 정점을

선별하여 반환하는 함수임을 알 수 있겠다.

 

따라서 u = choose(~) 를 통해 집합 Q에서의 정점을 선별하여 해당 정점을 집합 S에 추가하도록 한다.

그리고 for문을 돌려서 Relaxing 하는 과정을 볼 수 있겠다.

즉, 이를 (n - 2)번 실행하여 distance[] 에 대한 모든 설정을 할 수 있다.

 

 

An O(e log n) Implementation: Adjacency List 사용

 

 

이번엔 인접리스트에 대한 다익스트라 구현 코드이다.

먼저 PQ 에 대한 함수들에 대한 분석이다.

PQinsert() : 정점 v를 삽입함으로써 source에서 해당 정점 v로의 거리에 대한 min heap이 이뤄지도록 한다.

PQdec() : wt[w] 값 즉, w.d 에 대한 값을 변경했으므로 해당 정점 w에 대한 heap 조정이 일어나는 것을 알 수 있다.

PQdelmin() : source에서 정점 v로의 거리가 가장 짧은 정점을 반환하는 것을 알 수 있다.

 

while(!PQempty()) 에 대한 부분 :

모든 정점에 대한 shortest path의 가중치 값을 update 한 것으로 판단할 수 있겠다.

즉, S = V, Q = empty set 이 되어 더이상 Q에 속한 vertex의 relaxing 을 할 수 없게 된 상황이다.

 

wt[v = PQdelmin()] != maxWT 에 대한 부분 :

source 에서 v로의 path가 존재하는지에 대한 확인이 일어나는 부분이다.

만약 정점 1에서 정점 v 로의 경로가 차단될 경우 relaxing 에 대한 시도 조차 못하므로 바로 pass 하면 된다.

 

다 끝난 후 각 꼭지점에 대한 st를 어떻게 출력할까? 에 대한 부분 :

shortest path 가 존재할 때 st[w] 는 정점 w 에서 이전의 정점 v 값이 저장되어 있다.

따라서 각 꼭지점마다 이전 정점에 대한 출력이 이뤄지고 path가 연결되지 않을 경우 -1을 출력하게 된다.

그리고 source 정점일 경우 source 그대로 출력하게 된다.