-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dijkastra.cpp
64 lines (64 loc) · 1.46 KB
/
Dijkastra.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
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
using namespace std;
#define INFINITY 9999
void dijkstra(int arr[5][5],int n,int StartNode) {
int cost[5][5],distance[5],pred[5];
int visited[5],count,MinDistance,NextNode,i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(arr[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=arr[i][j];
}
}
for(i=0;i<n;i++) {
distance[i]=cost[StartNode][i];
pred[i]=StartNode;
visited[i]=0;
}
distance[StartNode]=0;
visited[StartNode]=1;
count=1;
while(count<n-1) {
MinDistance=INFINITY;
for(i=0;i<n;i++)
{
if(distance[i]<MinDistance&&!visited[i]) {
MinDistance=distance[i];
NextNode=i;}
}
visited[NextNode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(MinDistance+cost[NextNode][i]<distance[i]) {
distance[i]=MinDistance+cost[NextNode][i];
pred[i]=NextNode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=StartNode) {
cout<<"\nDistance node"<<i<<" = " <<distance[i];
cout<<"\nPath = "<<i;
j=i;
do {
j=pred[j];
cout<<" <--> "<<j;
}
while(j!=StartNode);
}
}
int main() {
int arr[5][5]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
int n;
int u;
cout<<"Enter number of nodes :-> ";
cin>>n;
cout<<"\nInitial node :-> ";
cin>>u;
dijkstra(arr,n,u);
return 0;
}