-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dijkstra.cpp
80 lines (75 loc) · 1.63 KB
/
Dijkstra.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
#include<iostream>
#include<climits>
using namespace std;
int findMinVertex(int* distance, bool* visited, int n)
{
int minVertex = -1;
for(int i=0;i<n;i++)
{
if(!visited[i] && (minVertex == -1 || distance[i]<distance[minVertex]))
{
minVertex = i;
}
}
return minVertex;
}
void dijkstra(int **edges, int n)
{
int* distance = new int[n];
bool* visited = new bool[n];
for(int i=0;i<n;i++)
{
distance[i] = INT_MAX;
visited[i] = false;
}
distance[0] = 0;
for(int i=0;i<n-1;i++)
{
int minVertex = findMinVertex(distance,visited,n);
for(int j=0;j<n;j++)
{
if(edges[minVertex][j] != 0 && !visited[j])
{
int dist = distance[minVertex] + edges[minVertex][j];
if(dist<distance[j])
{
distance[j] = dist;
}
}
}
}
for(int i=0;i<n;i++)
{
cout<<i<<" "<<distance[i]<<endl;
}
delete [] visited;
delete [] distance;
}
int main()
{
int n,e;
cin>>n>>e;
int** edges = new int*[n];
for(int i=0;i<n;i++)
{
edges[i] = new int[n];
for(int j=0;j<n;j++)
{
edges[i][j] = 0;
}
}
for(int i=0;i<e;i++)
{
int f,s,weight;
cin>>f>>s>>weight;
edges[f][s] = weight;
edges[s][f] = weight;
}
cout<<endl;
dijkstra(edges,n);
for(int i=0;i<n;i++)
{
delete [] edges[i];
}
delete [] edges;
}