セットを使用してダイクストラのアルゴリズムを実装するC++プログラム

これは、Setを使用してダイクストラのアルゴリズムを実装するためのC++プログラムです。ここでは2つのセットが必要です。ルートとして指定されたソースノードを使用して最短パスツリーを生成します。 1つのセットには最短経路ツリーに含まれる頂点が含まれ、もう1つのセットにはまだ最短経路ツリーに含まれていない頂点が含まれます。すべてのステップで、他のセット（まだ含まれていないセット）にあり、ソースからの距離が最小である頂点を見つけます。

アルゴリズム：

Begin
   function dijkstra() to find minimum distance:
   1) Create a set Set that keeps track of vertices included in shortest
   path tree, Initially, the set is empty.
   2) A distance value is assigned to all vertices in the input graph.
   Initialize all distance values as INFINITE. Distance value is assigned as
   0 for the source vertex so that it is picked first.
   3) While Set doesn’t include all vertices
      a) Pick a vertex u which is not there in the Set and has minimum distance value.
      b) Include u to Set.
      c) Distance value is updated of all adjacent vertices of u.
      For updating the distance values, iterate through all adjacent
      vertices. if sum of distance value of u (from source) and weight of
      edge u-v for every adjacent vertex v, is less than the distance value
      of v, then update the distance value of v.
End

サンプルコード

#include <iostream>
#include <climits>
#include <set>
using namespace std;
#define N 5
int minDist(int dist[], bool Set[])//calculate minimum distance
{
   int min = INT_MAX, min_index;
   for (int v = 0; v < N; v++)
   if (Set[v] == false && dist[v] <= min)
   min = dist[v], min_index = v;
   return min_index;
}
int printSol(int dist[], int n)//print the solution
{
   cout<<"Vertex Distance from Source\n";
   for (int i = 0; i < N; i++)
   cout<<" \t\t \n"<< i<<" \t\t "<<dist[i];
}
void dijkstra(int g[N][N], int src)
{
   int dist[N];
   bool Set[N];
   for (int i = 0; i < N; i++)
   dist[i] = INT_MAX, Set[i] = false;
   dist[src] = 0;
   for (int c = 0; c < N- 1; c++)
   {
      int u = minDist(dist, Set);
      Set[u] = true;
      for (int v = 0; v < N; v++)
      if (!Set[v] && g[u][v] && dist[u] != INT_MAX && dist[u]
         + g[u][v] < dist[v])
         dist[v] = dist[u] + g[u][v];
   }
   printSol(dist, N);
}
int main()
{
   int g[N][N] = { { 0, 4, 0, 0, 0 },
      { 4, 0, 7, 0, 0 },
      { 0, 8, 0, 9, 0 },
      { 0, 0, 7, 0, 6 },
      { 0, 2, 0, 9, 0 }};
   dijkstra(g, 0);
   return 0;
}

出力

Vertex Distance from Source
0 0
1 4
2 11
3 20
4 26