다익스트(dijkstra)라 알고리즘으로 최단경로 구하기

#include <stdio.h>

#define M 9999

#define N 5

 

int map[N][N] = {

{0,1,M,1,M},

{0,5,M,1,M},

{7,M,0,4,M},

{M,2,M,0,1},

{5,M,5,M,0}

};

 

int dist[N]; 
int v [N];

 

int* dijkstra(int start);

 

int main()

{

int i,j;

 

for(i=0 ; i<N ; i++)

{

dijkstra(i);

for(j=0 ; j<N ; j++)

{

printf("Start: %d End: %d Distance: %d", i, j, dist[j]);

}

}

}

 

int* dijkstra(int start)
{
 int i, j, mins, back;

 for(i=0 ; i<N ; i++)
 {
  v[i] = 0;
  dist[i] = M;
 }

 dist[start] = 0;

 for(i=0 ; i<N ; i++)
 {
  mins = M;

  for(j=0 ; j<N ; j++)
  {
   if((v[j]==0)&&(dist[j]<mins))
   {
    back = j;
    mins = dist[j];
   }
  }

  v[back] = 1;

  for(j=0 ; j<N ; j++)
  {
   if(dist[back]+map[back][j]<dist[j])
   {
    dist[j] = dist[back] + map[back][j];
   }
  }
 }
 
 return dist;
}