Dijkstra 알고리즘

class 정의 - 정적 생성

class Graph {
private:
   int length[nmax][nmax];	// 가중치
   int dist[nmax];		// 최단 경로 비용
   bool s[nmax];		// 정점이 S에 포함되었는지의 여부
   int n;			// 정점 수
   
public:   
   Graph (const int vertices = 0): n(verticies) {};
   void ShortestPath (const int);
   int choose (const int);
}

 

 

class 정의 - 동적 생성

class Graph {
private:
   int **length;
   int *dist;
   bool *s;
   int n;

public:
   Graph (const int vertices = 0): n(vertices) {  
      lenght = new int* [n];
      for (int i=0; i<n; i++)
         length[i] = new int[n];
         // 초기화
   }
   void ShortestPath (const int);
   int choose (const int);
}

 

 

최단 경로 함수 - O(n(n-2)) = O($n^2$) 소요

void Graph::ShortestPath (const int v) {
   for (int i=0; i<n; i++) {		// 초기화
      s[i] = FALSE;
      dist[i] = length[v][i];
   }
   
   s[v] = TRUE;
   dist[v] = 0;
   
   for (int i=0; i<n-2; i++) {	// 정점 v로부터 n-1개 경로 결정
      int u = choose(n);	// S에 속하지 않은 v 중 dist가 최소인 정점
      
      s[u] = TRUE;
      for (int w=0; w<n; w++) {
         if (!s[w])		// w ∉ S
            if ( dist[u] + length[u][w] < dist [w] )
               dist[w] = dist[u] + length[u][w];
      }
   }     
}