-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdijkstras.cpp
100 lines (81 loc) · 1.48 KB
/
dijkstras.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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
void Dijkstras(int nodes);
void printFunction(int nodes,int d[]);
int findMinValue(int m[],int d[],int nodes);
int graph[9][9] ;
int s = 0;
int main()
{
int numberOfNodes;
cout<<"Enter the number of nodes in the graph : ";
cin>>numberOfNodes;
for(int i=0;i<numberOfNodes;i++){
for (size_t j = 0; j < numberOfNodes; j++) {
cin>>graph[i][j];
}
}
Dijkstras(numberOfNodes);
return 0;
}
void Dijkstras(int nodes)
{
int d[nodes],m[nodes],prev[nodes],u;
for (size_t i = 0; i < nodes; i++)
{
if (graph[s][i]!=0)
{
d[i] = graph[s][i];
}
else
{
d[i] = INT_MAX;
}
m[i] = 0;
prev[i]=-1;
}
m[s] = 1;
d[s] = 0;
for (size_t i = 1; i < nodes; i++) {
u = findMinValue(m,d,nodes);
// find
m[u] = 1;
for (size_t w = 0; w < nodes; w++) {
if (graph[u][w]==0) {
continue;
}
if (m[w] != 0) {
continue;
}
if (d[w]>(d[u] + graph[u][w]))
{
d[w] = d[u] + graph[u][w];
prev[w] = u;
}
}
}
printFunction(nodes,d);
}
void printFunction(int nodes,int d[])
{
for (size_t i = 1; i < nodes; i++) {
cout<<i<<" - "<<d[i]<<endl;
}
}
int findMinValue(int m[],int d[],int nodes)
{
int index,min=INT_MAX;
for (size_t i = 0; i < nodes; i++)
{
if (m[i]==0)
{
if (d[i]<min)
{
min = d[i];
index = i;
}
}
}
return index;
}