shortest path in weighted undirected graph
| 318 | |
| 319 | //shortest path in weighted undirected graph |
| 320 | void dijkstrasAlgorithm(vector<int,int>arr[],int n,int source){ |
| 321 | vector<int>dis(n,INT_MAX); |
| 322 | vector<int>path(n); |
| 323 | //min priority queue |
| 324 | priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>q; |
| 325 | dis[source]=0; |
| 326 | q.push({0,source}); |
| 327 | while(!q.empty()){ |
| 328 | pair<int,int>top=q.top(); |
| 329 | int prev=top.second; |
| 330 | int weight=top.first; |
| 331 | q.pop(); |
| 332 | for(auto i:arr[prev]){ |
| 333 | if(dis[i.first] > dis[prev]+i.second){ |
| 334 | dis[i]=dis[prev]+i.second; |
| 335 | path[i.first]=prev;// this line is optional and tells you the shortest path elements |
| 336 | q.push({dis[i.first],i.first}); |
| 337 | } |
| 338 | } |
| 339 | } |
| 340 | |
| 341 | for(int i:dis)cout<<i<<" "; |
| 342 | } |
| 343 | |
| 344 | //for minimum spanning tree --> BRUTE FORCE O(n^2); |
| 345 | void primsAlogrithm(vector<int,int>arr[],int n){ |