Dijkstra algo giving wrong ans

sajalagrawal14 · August 31, 2019, 6:43pm

why my code is giving wrong ans:

Robin_rst · August 31, 2019, 8:08pm

You are assigning distance as 1e18 but when you are checking whether the distance from source to destination has changed or not, at that time you are using INT_MAX , INT_MAX is not equal to 1e18 , that’s why your code does not work.
And also no need to insert every element in set , and if you are using set you also don’t require visited array as the distance has been already updated.

Your working code

sajalagrawal14 · August 31, 2019, 8:57pm

thanks for ans , got the ans. and i have one more doubt , i the implementation of this algorithm using priority queue , when we are updataing priority queue why we are only inserting elemnts not removing the previous , like we did using set implementation link:-https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/

Robin_rst · August 31, 2019, 9:01pm

because we take visited array while implementing dijkstra using priority_queue . Removing element will cost complexity that’s why for sake we use visited.

apaarkamal · September 2, 2019, 3:30am

github.com

apaarkamal/launchpad_summer_2k19/blob/master/21. graph/dijstra algoritm(single source shortest path).cpp

#include<bits/stdc++.h>
#define F first
#define S second


using namespace std;

int main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	int i,j,n,m;
	cin>>n>>m;
	vector<pair<int,int>> gr[n+1];
	for(i=0;i<m;i++){
		int x,y,w;
		cin>>x>>y>>w;
		gr[x].push_back({y,w});
		gr[y].push_back({x,w});

This file has been truncated. show original

Amit-Gupta-1847343222026709 · September 7, 2019, 12:49pm

@apaarkamal your code is not working

apaarkamal · September 8, 2019, 4:23am

because you havent understood the code , you have just copy pasted

apaarkamal · September 8, 2019, 4:24am

see what the question demands, print only that

Amit-Gupta-1847343222026709 · September 8, 2019, 5:30am

@apaarkamal how can u accuse me of copying. Just to hide your incompetence. Good then. And if it is so dont take doubts, just sit and relax

apaarkamal · September 9, 2019, 10:38am

incompetence of what?
this code works fine whenever and wherever i used it.

apaarkamal · December 13, 2019, 10:46am

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.