-
Notifications
You must be signed in to change notification settings - Fork 61
Expand file tree
/
Copy pathImplementing Dijkstra | Set 1 (Adjacency Matrix)
More file actions
46 lines (35 loc) · 1.14 KB
/
Implementing Dijkstra | Set 1 (Adjacency Matrix)
File metadata and controls
46 lines (35 loc) · 1.14 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
void dijkstra(vector<vector<int>> graph, int src, int v)
{
set< pair<int,int> >s;
map<int,int>distance;
for(int i=0;i<v;i++)
distance[i]=INT_MAX;
distance[src]=0;
s.insert(make_pair(0,src));
while(!s.empty())
{
auto p = *s.begin();
int node= p.second;
int node_distance=p.first;
s.erase(s.begin());
for(int i=0;i<graph[node].size();i++)
{
if(distance[i]!=0)
{
if(distance[i]>graph[node][i]+distance[node])
{
int destination = i;
auto f=s.find(make_pair(distance[i],i));
if(f!=s.end())
{
s.erase(f);
}
distance[destination]=graph[node][i]+distance[node];
s.insert(make_pair(distance[destination],destination));
}
}
}
}
for(auto x:distance)
cout<<x.second<<" ";
}