자료구조] 다익스트라 + 스택을 이용한 경로추적

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define INT_MAX 1000000000 // 최대 정수
#define TRUE 1
#define FALSE 0
#define MAX_EDGES 100000000 //일억개 정점
#define MAX_VERTICES 10000

int stack[MAX_VERTICES];
int uarray[MAX_VERTICES];
int num=0;
int top = -1;

int numVertices;
int numEdges;

int IsEmpty() {
if (top < 0)
return TRUE;
else
return FALSE;
}
int IsFull() {
if (top >= MAX_VERTICES - 1)
return TRUE;
else
return FALSE;
}

void push(int value) {
if (IsFull() == TRUE)
printf("스택이 가득 찼습니다.");
else
stack[++top] = value;
}

int pop() {
if (IsEmpty() == TRUE)
printf("스택이 비었습니다.");
else
return stack[top--];
}

int seek()
{
return stack[top];
}

int choose(int distance[], int n, int found[])
{

int i, min, minpos;
min = INT_MAX;
minpos = -1;

for (i = 0; i < n; i++)
{

if (distance[i] < min && found[i] == FALSE)
{

min = distance[i];

minpos = i;
// printf("minpos: %d\n", distance[i]);
}
}

return minpos;
}

void shortest_path(int start, int n, int **weight,
int*distance, int*found)

{
int i, u, w;
//
for (i = 0; i < n; i++)
{

distance[i] = weight[start][i];

found[i] = FALSE;
}

found[start] = TRUE;
distance[start] = 0;
uarray[num] = start;
num++;

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

u = choose(distance, n, found);
if (u == -1)
{
uarray[num] = INT_MAX;
num++;
continue;
}

found[u] = TRUE;

for (w = 0; w < n; w++)
{
if (found[w] == FALSE)
{
if (distance[u] + weight[u][w] < distance[w])
{
distance[w] = distance[u] + weight[u][w];
}
}
}
uarray[num] = u;
num++;;
}
}

 

 

void track(int start, int findtrack, int **weight, int *distance,
int *found)
{
push(findtrack);

if (findtrack == start)
{

return;
}

int i = 0;
int temp = INT_MAX;
int tempfar = INT_MAX;
for (int j = 0; j < numVertices; j++)
{
if (uarray[j] == findtrack)
{
continue;
}

if (uarray[j] >= INT_MAX)
{
break;
}

if (weight[uarray[j]][findtrack] != INT_MAX)
{
if(tempfar > distance[uarray[j]]
+ weight[uarray[j]][findtrack])
{
temp = uarray[j];
tempfar = distance[uarray[j]] + 
weight[uarray[j]][findtrack];
}
}
}
track(start, temp, weight, distance, found);
}

 

////////////////////////////////////

평범한 다익스트라는 다른 곳에서도 구할 수 있는데, C로 되어 있는 경로추적은 찾기가 힘들어서 직접 구현했다.

중점적으로 봐야 할 부분은 TRACK이다.

 

알고리즘은 간단하게, 총 A부터 Z까지의 정점 중 Z에서 A로 향하는 길을 찾고자 할 때, A로 향하는 정점이 오직 B와 C뿐일 때, B까지의 거리와 C까지의 거리를 구한 다음, 여기에서 각각 B에서 A, C에서 A로 향하는 거리를 더해 가장 짧은 길을 택하는 것이다. 이 때, A를 PUSH한다.

 

다음으로, B로 향하는 정점이 무엇이 있는지 파악한다. 오직 D와 E뿐일 때, 또 Z에서 D까지와 E까지의 거리를 구한 다음, 여기에서 D에서 B, E에서 B로 향하는 거리를 계산한다. 이 때, E에서 가는 것이 더 짧다면 E를 택한 다음, B를 PUSH한다.

 

이를 반복해서, 언젠가 시작점과 도착점이 Z가 될 때까지 구한다. 이 때 리턴한다.

 

최종적으로 스택에는 A부터 차례로 Z까지 그 경로가 들어가있을 것이다. 이를 ISEMPTY가 참일 때까지 POP하면 된다.

 

단점은, 정점이 워낙 많다면 간헐적으로 SEGMANT FAULT가 뜬다.... 정점이 1만개만 되어도 재귀를 통해 호출해야 하는 함수가 기하급수적으로 늘어난다. 원래대로라면 한 정점을 노드로 구성한 다음, 특정 노드와 연결될 때 LINK시켜서 이 LINK를 따라가면서 추적을 하면 되는데, 막상 노드가 아닌 그냥 INT로 구현해놓고 나니 그냥 바꾸기 귀찮았다.