使用 Set 实现 Dijkstra 算法的 C++ 程序

这是一个使用 Set 实现 Dijkstra 算法的 C++ 程序。这里我们需要有两个集合。我们以给定的源节点为根生成最短路径树。一组包含最短路径树中包含的顶点，另一组包含最短路径树中尚未包含的顶点。在每一步，我们都会找到一个顶点，它在另一个集合中（尚未包含的集合）并且与源的距离最小。

算法：

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[])//计算最小距离
{
   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)//打印解决方案
{
   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