Dijkstra Algorithm

source node와 다른 node들 사이 최단 경로를 구하는 algorithm
source node ↔ node 의 최단 거리 : COST

1. Initialization

→ Forwarding table initialize

void Initialize(pGraph pG, int s)
{
	int i;

	for (i = 0; i < gGet_N(pG); i++)
	{
		gSet_in_S(pG, i, 0);	//node i is not in the set S
		gSet_cost(pG, i, INF);	//cost of node i = INF
		gSet_prenode(pG,i,-1);	//redecessor of i = nothing
		//prenode가 -1이면 없는것
	}
	gSet_cost(pG, s, 0 );	// cost of source = 0
	gSet_prenode(pG, s, s);	// predecessor of source = source
}

2. All_in_s

→ 모든 최단 거리를 찾았는가?

bool all_in_S(pGraph pG)
{
	int i;
	for (i = 0; i < gGet_N(pG); i++)
		if (!gGet_in_S(pG,i))	//when node i is not in S
			return false;
	return true;
}

3. Extract_min

→ source node와 가장 가까운 node는?

int Extract_Min(pGraph pG)
{
	int i, min;

	// find the first node not in S
	i = 0;
	while (gGet_in_S(pG,i)){
		i++;
	};	//check minimum value in S
	min = gGet_cost(pG,i);

	for (; i < gGet_N(pG); i++)
	{
		// pass for node in S
		if (gGet_in_S(pG,i))
			continue;

		// renew min when node with less cost is found
		if (gGet_cost(pG,i)<min)
			min = i;
	}
	return min;
}

4. Relazation

→ node u로 부터 node v까지의 초단 경로 업데이트

→ v_cost가 u_cost + u와 v 사이 weight보다 크면 업데이트

void Relaxation(pGraph pG, int u, int i)
{
	int cost_u, cost_v, weight_uv;
	double updated_weight;

	cost_u = gGet_cost(pG,u);	// cost of u
	cost_v = gGet_cost(pG,gGet_sink(pG,u,i));	// cost of v (v = sink of i-th edge of u)
	weight_uv = gGet_weight(pG,u,gGet_sink(pG,u,i));	// weight of directed edge from u to v

	if (INF == cost_u)
		return;

	if (cost_v > cost_u + weight_uv)	//update cost from u to i
	{
		gSet_cost(pG,gGet_sink(pG,u,i) , cost_u + weight_uv);	//update cost as new cost
		gSet_prenode(pG, gGet_sink(pG,u,i), u);	//Update predecessor of node u
	}
}