使用集合实现 Dijkstra 算法的 C++ 程序
c++programmingserver side programming
这是一个使用集合实现 Dijkstra 算法的 C++ 程序。这里我们需要两个集合。我们生成一个以给定源节点为根的最短路径树。一个集合包含最短路径树中包含的顶点，另一个集合包含尚未包含在最短路径树中的顶点。在每一步中，我们都会找到一个位于另一个集合(尚未包含的集合)中并且与源距离最小的顶点。
算法:
开始 函数 dijkstra() 查找最小距离: 1) 创建一个集合 Set，用于跟踪最短路径树中包含的顶点，最初，该集合为空。 2) 为输入图中的所有顶点分配一个距离值。 将所有距离值初始化为 INFINITE。源顶点的距离值被分配为 0，以便首先选择它。 3) 当 Set 不包含所有顶点时 a) 选择一个不在 Set 中且具有最小距离值的顶点 u。 b) 将 u 包含到 Set。 c) 更新 u 所有相邻顶点的距离值。 要更新距离值，请遍历所有相邻的 顶点。如果 u (来自源) 的距离值与每个相邻顶点 v 的边 u-v 的权重之和小于 v 的距离值，则更新 v 的距离值。 结束
示例代码
#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
