資料結構
網路
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 次瀏覽
廣告