다익스트라의 최단 경로 알고리즘

주요 문제는 이전 문제와 동일하며 시작 노드에서 다른 노드까지 가장 작은 거리를 찾습니다. 이 문제에서 가장 큰 차이점은 그래프가 인접 행렬을 사용하여 표현된다는 것입니다. (비용 매트릭스와 인접 매트릭스는 이를 위해 유사합니다.)

인접 목록 표현의 경우 시간 복잡도는 O(V^2)입니다. 여기서 V는 그래프 G(V, E)의 노드 수입니다.

입력 및 출력

Input:
The adjacency matrix:

Output:
0 to 1, Using: 0, Cost: 3
0 to 2, Using: 1, Cost: 5
0 to 3, Using: 1, Cost: 4
0 to 4, Using: 3, Cost: 6
0 to 5, Using: 2, Cost: 7
0 to 6, Using: 4, Cost: 7

알고리즘

dijkstraShortestPath(n, dist, next, start)

입력 - 총 노드 수 n, 각 정점에 대한 거리 목록, 다음에 올 노드를 저장할 다음 목록, 시드 또는 시작 정점.

출력 - 시작에서 다른 모든 정점까지의 최단 경로입니다.

Begin
   create a status list to hold the current status of the selected node
   for all vertices u in V do
      status[u] := unconsidered
      dist[u] := distance from source using cost matrix
      next[u] := start
   done

   status[start] := considered, dist[start] := 0 and next[start] := φ
   while take unconsidered vertex u as distance is minimum do
      status[u] := considered
      for all vertex v in V do
         if status[v] = unconsidered then
            if dist[v] > dist[u] + cost[u,v] then
               dist[v] := dist[u] + cost[u,v]
               next[v] := u
      done
   done
End

예

#include<iostream>
#define V 7
#define INF 999
using namespace std;

// Cost matrix of the graph
int costMat[V][V] = {
   {0, 3, 6, INF, INF, INF, INF},
   {3, 0, 2, 1, INF, INF, INF},
   {6, 2, 0, 1, 4, 2, INF},
   {INF, 1, 1, 0, 2, INF, 4},
   {INF, INF, 4, 2, 0, 2, 1},
   {INF, INF, 2, INF, 2, 0, 1},
   {INF, INF, INF, 4, 1, 1, 0}
};

int minimum(int *status, int *dis, int n) {
   int i, min, index;
   min = INF;

   for(i = 0; i<n; i++)
      if(dis[i] < min && status[i] == 1) {
         min = dis[i];
         index = i;
      }

   if(status[index] == 1)
      return index; //minimum unconsidered vertex distance
   else
      return -1;    //when all vertices considered
}

void dijkstra(int n, int *dist,int *next, int s) {
   int status[V];
   int u, v;

   //initialization
   for(u = 0; u<n; u++) {
      status[u] = 1;               //unconsidered vertex
      dist[u] = costMat[u][s];     //distance from source
      next[u] = s;
   }

   //for source vertex
   status[s] = 2; dist[s] = 0; next[s] = -1; //-1 for starting vertex

   while((u = minimum(status, dist, n)) > -1) {
      status[u] = 2;//now considered
      for(v = 0; v<n; v++)
         if(status[v] == 1)
            if(dist[v] > dist[u] + costMat[u][v]) {
               dist[v] = dist[u] + costMat[u][v];   //update distance
               next[v] = u;
            }
   }
}

main() {
   int dis[V], next[V], i, start = 0;
   dijkstra(V, dis, next, start);

   for(i = 0; i<V; i++)
      if(i != start)
         cout << start << " to " << i <<", Using: " << next[i] << ",
   Cost: " << dis[i] << endl;
}

출력

0 to 1, Using: 0, Cost: 3
0 to 2, Using: 1, Cost: 5
0 to 3, Using: 1, Cost: 4
0 to 4, Using: 3, Cost: 6
0 to 5, Using: 2, Cost: 7
0 to 6, Using: 4, Cost: 7