-
Notifications
You must be signed in to change notification settings - Fork 9
/
dijkstra algo using set in cpp
46 lines (46 loc) · 1.07 KB
/
dijkstra algo using set in cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#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
{
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;
}