smart and get things done

2008. 11. 7. 12:08

Dijkstra Algorithm(최단거리찾기)

2008. 11. 7. 12:08 in programming

여기에서 소스 참조

** 최단경로 : 방향그래프(Directed Graph)의 간선이 양수의 Weight를 가질 때 임의의 출발 정점에서 도착 정점까지의 경로 중 경로의 길이가 최소인 경로

Dijkstra Algorithm

1. 인접행렬 상태로 각 간선의 가중치(Weight)가 존재하도록 한다.
정점 i에서 i까지의 가중치는 0이고 정점 i에서 j까지의 간선 E(i, j)가 존재치 않으면 가중치는 무한대(∞)가 된다.
2. 집합 S와 T를 정하는데 S는 출발 정점을 초기값으로 하고 집합 T는 출발 정점을 제외한 모든 정점을 포함하도록 초기화한다.
3. 출발 정점을 제외한 모든 정점으로부터의 거리의 초기값(dist[i], 2<=i<=n)을 [1]의 인접행렬에서 취한다.
4. 집합 T의 원소 중 출발점으로부터의 거리가 최소인 정점 v를 택하여 T에서 제거하고 집합 S에 추가한다.
5. T집합내의 모든 정점 w에 대해 출발점으로부터의 거리(dist[w])와 간선 E(v, w)의 길이에 v정점의 거리(dist[v])를 합한 값 중 작은 것을 선택하여 정점 w의 거리(disw[w])로 한다.
6. 4, 5의 과정을 T집합이 공집합이 될 때까지 반복한다

수행시간은 빅오(n^2)
예제.

class Dijkstra
{
public:
void print()
{
  printf("\n                   <다익스트라(Dijkstra) 알고리즘>                  \n");
  printf("\n 주어진그래프에서출발점과도착점을입력하면최단거리를알려줍니다.");
  printf("\n +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
  printf("\n +                                                                 +");
  printf("\n +                         [2]-------3-------[4]                   +");
  printf("\n +                          |                / (                   +");
  printf("\n +                          |               /   (                  +");
  printf("\n +                          4             3      4                 +");
  printf("\n +                          |           /         (                +");
  printf("\n +                          |          /           (               +");
  printf("\n +           [0]-----2-----[1]---1---[3]            [7]            +");
  printf("\n +            (                       (            /               +");
  printf("\n +              (                       (         /                +");
  printf("\n +                3                       2      4                 +");
  printf("\n +                 (                       (    /                  +");
  printf("\n +                  (                       ( /                   +");
  printf("\n +                  [5]----------6-----------[6]                   +");
  printf("\n +                                                                 +");
  printf("\n +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
}

void test()
{
  const int U=static_cast<unsigned int>(-1)/2;
  int data[8][8] = {
   {0,2,U,U,U,3,U,U},
   {2,0,4,1,U,U,U,U},
   {U,4,0,U,3,U,U,U},
   {U,1,U,0,3,U,2,U},
   {U,U,3,3,0,U,U,4},
   {3,U,U,U,U,0,6,U},
   {U,U,U,2,U,6,0,4},
   {U,U,U,U,4,U,4,0}};

  while(1)
  {
   int i,j,k,s,e,min,n=8;
   int path[8],path_cnt=0;
   bool v[8];
   int distance[8],via[8];

print();

   printf("\n 출발점을입력하시오. : ");
   scanf("%d", &s);
   printf(" 도착점을입력하시오. : ");
   scanf("%d", &e);

   // 초기화
   for(i=0;i<n;i++)
   {
    v[i]=false;
    distance[i]=U;
   }
   distance[s]=0;

   // 찾기
   for(i=0;i<n;i++)
   {
    min=U;
    for(j=0;j<n;j++)
    {
     if(v[j]==false && distance[j]<min)
     {
      k=j;
      min=distance[j];
     }
    }
    v[k]=true;
    if(min==U)
     break;
    for(j=0;j<n;j++)
    {
     if(distance[k]==U || data[k][j]==U)
      continue;
     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]);
   // 최단경로
   k=e;
   while(true)
   {
    path[path_cnt++]=k;
    if(k==s)
     break;
    k=via[k];
   }
   for(i=path_cnt-1;i>=1;i--)
    cout << path[i] << " -> ";
   cout << path[i] << endl;
  }
}
};