微客导航 » 文章资讯 » 使用 Set 实现 Dijkstra 算法的 C++ 程序

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

2023-06-20 10:36:02 181

这是一个使用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 
#include 
#include 
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 "<输出结果Vertex Distance from Source
0 0
1 4
2 11
3 20
4 26

返回顶部
3162201930
czq8825@qq.com

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

算法：

示例代码

热门推荐

随机推荐