数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社科
服装研究
法律研究使用集合实现 Dijkstra 算法的 C++ 程序
这是一个使用集合实现 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[])//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
更新时间:30-7 月-2019
517 次浏览
广告