-
Notifications
You must be signed in to change notification settings - Fork 0
/
DijkstrasMethod.cpp
51 lines (48 loc) · 1.12 KB
/
DijkstrasMethod.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
47
48
49
50
51
#include<iostream>
using namespace std;
#define V 7
int mindistance(int distance[],bool mstset[]){
int min=INT_MAX,min_index;
for(int v=0;v<V;v++){
if(mstset[v]==false &&distance[v]<min){
min=distance[v];
min_index=v;
}
}
return min_index;
}
void printmst(int distance[],int n){
cout<<"Vertex Distance from Source:"<<endl;
for(int i=0;i<V;i++){
cout<<i<<" - "<<distance[i]<<endl;
}
}
void dijikstamst(int graph[V][V],int source){
int distance[V];
bool mstset[V];
for(int i=0;i<V;i++){
distance[i]=INT_MAX,mstset[i]=false;
}
distance[source]=0;
for(int count=0;count<V-1;count++){
int u=mindistance(distance,mstset);
mstset[u]=true;
for(int v=0;v<V;v++)
if(graph[u][v] && mstset[v]==false && graph[u][v]+distance[u]<distance[v]){
distance[v]=graph[u][v]+distance[u];
}
}
printmst(distance,V);
}
int main(){
int graph[V][V]={{0,28,0,0,0,10,0},
{28,0,16,0,0,0,14},
{0,16,0,12,0,0,0},
{0,0,12,0,22,0,18},
{0,0,0,22,25,0,24},
{10,0,0,25,0,0,0},
{0,14,0,18,24,0,0}
};
dijikstamst(graph,0);
return 0;
}