먼저 다익스트라 알고리즘이란 O(N^2)만에 최단경로를 구하는 알고리즘입니다
이 알고리즘을 사용하시려면 몇개의 배열 정의부터 알아야 하는데요(저 블로그에 있는 배열을 그대로 사용하겟습니다)
s = 입력받는 출발점입니다
e= 입력받는 도착점입니다
data[i][j] = i정점부터 j정점까지의 거리(이건 최단거리가 아닙니다. 하나의 간선을 거쳐서 가야 합니다) 그리고 i정점과 j정점이 직접적으로 연결되어있지 않으면 MAX값을 넣어줍니다
distance[i] = s(출발점)에서 i번째 정점까지의 최단거립니다.
v[i] = i번째 정점이 체크되었는지를 나타냅니다 (1 : 체크)
via[i] =s정점부터 i번째 정점으로 가는 최단경로에서 i번째 경로의 바로 전 정점의 번호입니다(배열 정의가 약간 애매한듯..)
그럼 다익스트라 소스를 잠깐 볼까요
정점의 수만큼 돌면서
{
k=현재 distance배열에 있는 값이 가장 작은 정점(s정점과의 거리가 가장 가까운 정점)
이면서 아직 체크되지 않은 정점
v[k]=1 체크
정점의 수만큼 돌면서(j = 현재 정점)
{
distance[j] 보다 distance[k]+data[k][j]가 작으면 갱신
(s정점부터 j정점까지 가는 현재 확보된 길보다 k정점으로 갔다가 k정점에서 j정점으 로 가는게,돌아가는게 빠르다면 바꿔줍니다)
}
}
이런 구조인데 여기서 잘 생각 해보시면 최단경로에서의 j정점의 바로 전 정점은 k정점이 됩니다 왜냐하면 s->j 보다 s->k->j가 더 빠르단말은 j전에 k가 있단 말이죠
그러므로 via[j]=k가 됩니다 그럼 거의 해결이 되었네요
그럼 최단 경로를 출력하려면 어떻게 하면 될까요?
via[e]는 끝 정점의 바로 전 정점을 담고 있습니다.
a=via[e]에서 a는 끝 정점의 바로 전 정점이겠죠? 물론 최단거리에서말입니다
그러면, via[a]는 뭘까요? 그건 끝 정점의 바로 전 정점의 바로 전 정점입니다.
이렇게 계속 역추적 하다가 시작점인 s가 나오면 멈추면 되겠죠?
#include
#define n 8
#define m 5000
void main()
{
int data[8][8] = {
{0,2,m,m,m,3,m,m},
{2,0,4,1,m,m,m,m},
{m,4,0,m,3,m,m,m},
{m,1,m,0,3,m,2,m},
{m,m,3,3,0,m,m,4},
{3,m,m,m,m,0,6,m},
{m,m,m,2,m,6,0,4},
{m,m,m,m,4,m,4,0}};
int i, j, k, s, e, min;
int v[8], distance[8], via[8];
// 그래프는 사전에 주어진 그래프를 사용한다. 지금은 예를들어 표기를 한 것임.
printf("\n <다익스트라(Dijkstra) 알고리즘> \n");
printf("\n 주어진 그래프에서 출발점과 도착점을 입력하면 최단거리를 알려줍니다.");
printf("\n +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
printf("\n + +");
printf("\n + [3]-------3-------[5] +");
printf("\n + | / ( +");
printf("\n + | / ( +");
printf("\n + 4 3 4 +");
printf("\n + | / ( +");
printf("\n + | / ( +");
printf("\n + [1]-----2-----[2]---1---[4] [8] +");
printf("\n + ( ( / +");
printf("\n + ( ( / +");
printf("\n + 3 2 4 +");
printf("\n + ( ( / +");
printf("\n + ( ( / +");
printf("\n + [6]----------6-----------[7] +");
printf("\n + +");
printf("\n +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
////////////////////////////////////////////////////////////////////////////////////
printf("\n 출발점을 입력하시오. : ");
scanf("%d", &s);
printf(" 도착점을 입력하시오. : ");
scanf("%d", &e);
for(j=0; j<8; j++)
{
v[j] = 0;
distance[j] = m;
}
distance[s-1] = 0;
for(i=0; i<8; i++)
{
min = m;
for(j=0; j<8; j++)
{
if(v[j]==0 && distance[j]
k = j;
min = distance[j];
}
}
v[k] = 1;
if(min==m) break;
for(j=0; j<8; j++)
{
if(distance[j] > distance[k] + data[k][j])
{
distance[j] = distance[k] + data[k][j];
via[j]=k;
}
}
}
printf("\n %d에서 출발하여, %d로 가는 최단 거리는 %d입니다.\n", s, e, distance[e-1]);
int path[8], path_cnt=0;
k=e-1;
while(1)
{
path[path_cnt++]=k;
if(k==s-1)break;
k=via[k];
}
printf(" 경로는 : ");
for(i=path_cnt-1;i>=1;i--)
{
printf("%d -> ",path[i]+1);
}
printf("%d입니다",path[i]+1);
}