forked from sobhanbera/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDijkstra.cpp
More file actions
85 lines (84 loc) · 1.63 KB
/
Dijkstra.cpp
File metadata and controls
85 lines (84 loc) · 1.63 KB
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
#include<bits/stdc++.h>
using namespace std;
int N;
int graph[10][10];
int dist[10];
bool visited[10];
int parent[10];
void createGraph()
{
int i,j,max,u,v,w;
cout<<"Enter the number of nodes : ";
cin>>N;
for(i=0;i<=N;i++)
for(j=0;j<=N;j++)
graph[i][j]=0;
max=N*(N+1);
for(i=0;i<max;i++)
{
cout<<"Enter Edge and Weight : ";
cin>>u>>v>>w;
if(u==-1) break;
else
{
graph[u][v]=w;
graph[v][u]=w;
}
}
}
int minDistance()
{
int min = 10000, minDist;
for (int v = 0; v < N; v++)
if (visited[v] == false && dist[v] <= min)
{
min = dist[v];
minDist = v;
}
return minDist;
}
void printPath(int j)
{
if (parent[j]==-1)
return;
printPath(parent[j]);
cout<<j<<" ";
}
void dijkstra()
{
int src;
cout<<"Enter the Source Node : ";
cin>>src;
for (int i = 0; i < N; i++)
{
parent[0] = -1;
dist[i] = 10000;
visited[i] = false;
}
dist[src] = 0;
for (int count = 0; count < N-1; count++)
{
int u = minDistance();
visited[u] = true;
for (int v = 0; v < N; v++)
if (!visited[v] && graph[u][v] &&
dist[u] + graph[u][v] < dist[v])
{
parent[v] = u;
dist[v] = dist[u] + graph[u][v];
}
}
cout<<"Src->Dest\tDistance\tPath"<<endl;
for (int i = 1; i < N; i++)
{
cout<<src<<"->"<<i<<"\t\t"<<dist[i]<<"\t\t"<<src<<" ";
printPath(i);
cout<<endl;
}
}
int main()
{
createGraph();
dijkstra();
return 0;
}