G-35. Print Shortest Path - Dijkstra's Algorithm
Вставка
- Опубліковано 27 сер 2024
- Disclaimer: Please watch Part-1 and Part-2
Part-1: • G-32. Dijkstra's Algor...
Part-2: • G-33. Dijkstra's Algor...
GfG-Problem Link: bit.ly/3SlYvLp
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
This question is updated on GFG , if you look at strivers screen its just asking path but in updated question you need to append the dist[n] also and then reverse
yeah, i was confused where's the error in my code , then did this and passed all tetscases. Thanks!!
Thanks for sharing 👍
Solved this code without watching any approach in this video just when he said try it out first, i go and solved it. Thanks Striver.
Thanks a lot, striver. Ur content is far better than paid courses. U literally explained us everything in such a depth. Thanks again for all your amazing playlists.
I just love the confidence and the clarity with which you code the solution. I have started to recite the solution similar to your style while coding alone ^^
NOTE
Now the question is updated ,we also have to pushback the weight of shortest path.
typedef pair pip;
vector shortestPath(int n, int m, vector& edges) {
vector< pair >adj[n+1];
for(auto &it : edges)
{
adj[it[0]].push_back({it[1],it[2]});
adj[it[1]].push_back({it[0],it[2]});
}
priority_queue< pip, vector , greater< pip > >pq;
pq.push({0,1});
vectordist(n+1,1e9);
dist[1] = 0;
vectorparent(n+1);
for(int i = 1;i 0)
{
auto it = pq.top();
int node = it.second;
int dis = it.first;
pq.pop();
for(auto &it : adj[node])
{
int adjnode = it.first;
int edgeweight = it.second;
if(dis + edgeweight < dist[adjnode])
{
dist[adjnode] = dis + edgeweight;
pq.push({dis+edgeweight , adjnode});
parent[adjnode] = node;
}
}
}
if(dist[n] == 1e9) return {-1};
vectorpath;
int node = n;
while(parent[node] != node)
{
path.push_back(node);
node = parent[node];
}
path.push_back(1);
path.push_back(dist[n]);
reverse(path.begin(),path.end());
return path;
}
it's showing tle error in the last test case
Thank you so much!!! Was struggling to find my mistake!
@@bhaktisharma9681 did u find the solution ?? Then pls share it here 🙏
Can you explain the code for graph creation? I'm not able to understand it
we can print the path with the help of distance array only (no need of parent array)
if(dis[n]==1e9){
return {-1};
}
vectorans;
int curr_node=n;
while(curr_node!=1){
ans.push_back(curr_node);
for(auto it:al[curr_node]){
if(dis[it.first]==dis[curr_node]-it.second){
curr_node=it.first;
}
}
}
ans.push_back(1);
reverse(ans.begin(),ans.end());
return ans;
Using that parent array was indeed a smart move 😀 !!
Another short approach using Dijkstra's Algorithm (in this we will store the path in priority queue itself just like word ladder II)
vector shortestPath(int n, int m, vector& edges) {
vector adj[n + 1];
for(auto e : edges) adj[e[0]].push_back({e[1], e[2]}), adj[e[1]].push_back({e[0], e[2]});
vector d(n + 1, INT_MAX);
d[1] = 0;
priority_queue pq;
pq.push({0, {1}});
int minD = INT_MAX;
vector ans = {-1};
while(pq.size()) {
vector path = pq.top().second;
int dis = pq.top().first; pq.pop();
int node = path.back();
if(node == n && minD > dis) minD = dis, ans = path;
for(auto ad : adj[node]) {
if(d[node] + ad.second < d[ad.first]) {
d[ad.first] = d[node] + ad.second;
path.push_back(ad.first);
pq.push({d[ad.first], path});
path.pop_back();
}
}
}
return ans;
}
damn nice 🔥
Great soln!!
same approach but tle on tc 4
after line 20 we should push pair {0,1} initially to priority queue
you can but here we push {0,1} as we store in pq and we store in adj list hope you get this
My approach similar to WordLadder-2, in set along with dist store currentList too...
vector shortestPath(int n, int m, vector& edges) {
// Code here
vector adj[n+1];
for(int i=0; i
Understood! Such a wonderful explanation as always, thank you very much!!
simple solution again.. thanks Striver. This Graph series feels easier than any other..❤
Hi Striver, With your hint I was able figure out that this algo is same as we used to print LIS/LCS in DP. Can't think of anyone teaching DSA better than you. Well its not wrong to say that you are the Netflix of DSA xD
same same
which year?
And I solved it seeing ur hint (print LIS problem in dp)
@@krishanpratap3286 2020 passed out lol
So are you looking to switch?
Hi sir, I solved this question by own and this is happened because of you. Before your videos graph is like impossible thing for me but now I can solve medium level questions easily
Question is updated in GFG, it is undirected so we need to add u->v and v->u both in the adjacency List.
Also Need to add the dist[n] to the path and need to reverse it as the question is asking the dist and path of src to N node.
GFG Apparantly have updated the testcases and this solution no longer is getting accepted
you just have to append the shortest path distance at the beginning of the answer array
one major doubt. How can we come up with these kind of solutions on our own???
Practice, and practice...
@@takeUforward and Observation.....
because if you just keep practicing with closed eyes it would take an eternity to become a good problem solver.....
@@SatyamEdits Thank you
@@takeUforward Thank you
TreeSet solution in Java (Just need to override compareTo, equals and hashCode methods of the SortedSet interface):
class Pair implements Comparable{
int node, dist;
public Pair(int dist, int node){
this.node = node;
this.dist = dist;
}
@Override
public boolean equals(Object e){
Pair other = (Pair) e;
return node == other.node;
}
@Override
public int hashCode(){
return node;
}
@Override
public int compareTo(Pair p){
if(p.dist == this.dist)
return this.node - p.node;
return this.dist - p.dist;
}
}
class Solution
{
static int[] dijkstra(int V, ArrayList graph, int S)
{
//dist, node -> sort by smaller distance from src. If dist same, then sort by smaller node
TreeSet set = new TreeSet();
set.add(new Pair(0, S));
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[S] = 0;
while(!set.isEmpty()){
Pair cur = set.pollFirst();
int src = cur.node, distToSrc = cur.dist;
for(ArrayList edge : graph.get(src)){
int dest = edge.get(0), curDist = edge.get(1);
if(dist[dest] > distToSrc + curDist){
dist[dest] = distToSrc + curDist;
set.add(new Pair(dist[dest], dest));
}
}
}
return dist;
}
}
Your Code's output is:
1 46 11 51
It's Correct output is:
1 46 11 51
Output Difference
1 46 11 51
🤣😂
Just love ur way of solution Problem ❤️❤️
We can also use pq of dist and the path we have so far to solve it without needing the parent array.
vector shortestPath(int N, int m, vector& edges) {
priority_queue pq ;
vector dist(N+1,INT_MAX) ;
vectoradj[N+1] ;
for (int i =0 ; i< m ;i ++) {
int u = edges[i][0] ;
int v = edges[i][1];
int wt =edges[i][2] ;
adj[u].push_back({v,wt}) ;
adj[v].push_back({u,wt}) ;
}
pq.push({0,{1}}) ;
//bool flag = false ;
while(!pq.empty()) {
auto x = pq.top() ;
pq.pop() ;
vector path = x.second ;
int node = path.back();
int dis = x.first ;
if (node==N) {
// flag = true ;
return path ;
}
for (auto x : adj[node]) {
int adjNode = x.first ;
int adjDis = x.second ;
if (dist[adjNode]>adjDis+dis) {
dist[adjNode] = adjDis + dis ;
path.push_back(adjNode);
pq.push({adjDis + dis, path});
path.pop_back();
}
}
}
return {-1} ;
}
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
What if there are multiple shortest path and we have to print all of them? In that case what should we do?
what if we need to find all the shortest paths from src to destination? (eg if there are 3 paths from src->dest with total wt=5,how to get all three)
We basically hashing the node for each updatation in the distances[adjNode]. I guess we can use HashMap too in this case.
Masterpiece Explanation
Please use a proper compiler which shows output also so it will be more understandable.
hey striver you forget to push the dist[n] in path after line 46 , if i will not push then it gives me one less path(node) in vector.
Understood! amazing Explanation.
Litterly saved me, deserves a subscription if you ask me!!!
TLE on the last test case?
I am unable to find this Question on GFG
Same
Was able to come up with the solution without watching the video. Here's my implementation :
vector shortestPath(int n, int m, vector& edges) {
// Code here
vectoradj[n+1];
for(int i = 0 ; i < edges.size() ; i++){
adj[edges[i][0]].push_back({edges[i][1],edges[i][2]});
adj[edges[i][1]].push_back({edges[i][0],edges[i][2]});
}
priority_queue pq;
pq.push({0,{1,{1}}});
vectordist(n+1,INT_MAX);
dist[1]=0;
while(!pq.empty()){
pair ki=pq.top();
pq.pop();
int dis=ki.first;
int k=ki.second.first;
vectorvec=ki.second.second;
vectorvy=vec;
if(k==n) return vec;
for(int i = 0 ; i < adj[k].size() ; i++){
if(dis+adj[k][i][1]
almost same type of solution but got tle on case 4
hey Striver bhaiya, i have a doubt that instead of storing the parents, can't we do this.
if anyone else can help , then please.
int node = n;
while(node != 1){
for(auto it : adj[node]){
int adj_node = it.first;
int adj_wt = it.second;
if(dist[node] == dist[adj_node] + adj_wt){
ans.push_back(adj_node);
node = adj_node;
}
}
}
intution is simple that whose adjNode's distance + weight gives the node's distance will be the parent node.
Thank you very much. You are a genius.
What if there are two shortest path 1->2->4->5 and 1->3->5 with the same dist value , will it print 1->3->5?
No it's based on graph
If you want smallest path (or) all paths then store parent=list of set of values
Ex:parent=[0,{1, 2}] dist=[0,1]
Again if we get dist 1 of index 1 from other path then simply add that node to parent [1] then apply dfs not while loop.
Understood!
how to handle multiple shorest path . This question was asked in my college intership OA of atlassian. PLss tell how to handle ?
Hey instead of using extra array of parent can't we store a Pair in the dist array itself and do the backtrack from there. This way we can save some space.
#tuf and take forward for crowdwork...#leetcode more solution needed
How can it have a better time complexity?, If observed closely the total number of integers will be equal, so I don't think it's better from any angle.
lol, pair of size n is nothing but two arrays of size n clubbed together.
Thank you sir 🙏
Huge effort 🤩
understood, thank you so much.
Understood Bhaiya
Understood
Suggestion:- ek sath itne sare video mat upload karo channel ke reach Kam hoti hai
Ho sake to ek ek hour ke video schedule kardo
And amazing approach striver Bhai 😀
Edit:- mai galat tha
#keep_striving
Areh pdhai ki channel ki reach hoti v nai h, word of mouth pe hi chalta h
@@takeUforward true
@@takeUforward still if u upload 1 or 2 video daily that will make us consistent
Understood sir thankyou❤✨🙏🙇♂
Hi striver, can the datatype of distance array be a class which stores node distance and parent ? so that we will not take two separate arrays?
we dont have to initialize the whole parent array, just do parent [source] = source ;
if the weight of both edges is same, we need to handle that based on nodes in Priority Queue
hey striver , I solved this problem using a different approach where my pq consists of distance and vector(containing path until now) runs just fine
class Solution {
public:
vector shortestPath(int n, int m, vector& edges) {
// Code here
vectorans;
vectoradj[n+1];
for(int i=0;i
Very much helpful 😍😍
just amazing !!
understood bhaiya
Thank you bhaiya
One doubt! Why we need to initialise parent[ ] with idx themselves? does it help in anyway? my all test cases were passed without doing that (I did on Java )
because if the given graph is a NULL graph then each node is a parent of itself,it doesn't make a diiference here since we only want the path if initial vertex and final vertex is connected,but at the end of the program doing this yields us the correct parent array no matter weather path exists or not
doesn't matter what you store at the parent caue when you will get the path it will automatically get updated with the new parents.
what about no path case (-1)?
Understood
As the note not yet updated.
Just for resource : java code
public static List shortestPath(int n, int m, int edges[][]) {
ArrayList adj = new ArrayList();
for(int i = 0;i
Understood ❤
why we need to push 5 at the end to run this code on gfg
vector shortestPath(int n, int m, vector& edges) {
vector adj[n+1];
for(auto it:edges){
adj[it[0]].push_back({it[1],it[2]});
adj[it[1]].push_back({it[0],it[2]});
}
priority_queue pq;
vector dist(n+1,1e9);
vector parent(n+1);
for(int i=1;i
Because they asked for the shortest distance value as well. So, they want you to first give them the shortest distance as the first index then the graph path.
UNDERSTOOD.
adj[it[0]] is a pair, how can we do a push_back to a pair??
I've understood the algo and the code but it's showing TLE error in gfg for last 2 cases, both with priority_queue and set...anyone else having same problem as me ?
Yes, I solved it alone and got TLE using Java. But when I solved it using C++ it ran well!!
One doubt! Why we need to initialise parent[ ] with idx themselves? does it help in anyway? my all test cases were passed without doing that (I did on Java )
because if the given graph is a NULL graph then each node is a parent of itself,it doesn't make a diiference here since we only want the path if initial vertex and final vertex is connected,but at the end of the program doing this yields us the correct parent array no matter weather path exists or not
Sir you forgot the case of returning list of -1s if path's not possible
understood
Understood 👍
why cant we take max priority queue? its giving tle .
UNDERSTOOD
Understood❤
Understood 😇
nice:) explanation sir
am i missing something?
since its undirected graph there definitely exists a path right?
then y print (-1)
What if the Node is Unreachable ?
@@gamerversez5372 undirected graph means it's reachable every where.
Also there is only one component
Huge love from south❤
UnderStood Sir!
its 3:54 am and busy creating my future😁😄
thanku striver
understood💙💙💙
Understood!!
Where can we find the java code for this video
i am not able to write code by myself what to do?
can someone share link of question , it seems to be broken
Golden❤
amazing
Always remember, where you are coming from!
understtooooddddd
what if path doesn’t exist?
understood!!
In Java code, you have added new Pair(edges[i][1], edges[i][2]) which I am not able to understand. Because we are storing data in PQ as {dist, node} then it should be something like Pair(edges[i][2], edges[i][1]). Can someone please help me understand this
You can refer to this code, passing all the test cases (Java Correct Solution)
class Solution {
public static List shortestPath(int n, int m, int edges[][]) {
ArrayList adj = new ArrayList();
for(int i=0;i
that time he stores value in adjacency list to make it graph. so edges([i][0]).add(edges[i][1],edges[i][2]);
it means from [i][0] to [i][1] there is a edge and weight is [i][2]
class Pair implements Comparable{
int src;
int wt;
public Pair(int src, int wt){
this.src = src;
this.wt = wt;
}
public int compareTo(Pair pair){
return this.wt - pair.wt;
}
}
class Node{
int dest;
int cost;
public Node(int dest, int cost){
this.dest = dest;
this.cost = cost;
}
}
class Solution {
public static List shortestPath(int n, int m, int edges[][]) {
int memo[] = new int[n+1];
int distance[] = new int[n+1];
PriorityQueue pq = new PriorityQueue();
ArrayList graph = new ArrayList();
for(int i = 0; i
understood
Even if my result and expected result is same its not passing test case. Test case number - 63
pin this comment so everyone can save their time
Your Code's output is:
1 46 11 51
It's Correct output is:
1 46 11 51
Output Difference
1 46 11 51
same here
glitch hai, ab working
i was not able to solve it after pausing, what should I do. Am i that much incompetent.
Would you please send me problem link
i can feel u bro, i'm also feeling same but only solution is practice
awesome
Please anyone tell me from where could I learn the use of priority queue of min heap in java
gfg
For same code but using unordered map insted of vector for getting path is giving me tle on 7th testcase itself😮!! Can anyone tell me the reason
showing (SIGABRT) on last 2 test cases, anyone?
understood
sir
Can anyone explain Line 19: Initializing parent array equal to the index value ?? @16:06
this is done because we need to stop after node 1 is reached . The condition used inside while(parent[node]!=node) will become false for node 1.
class Solution {
static class Node {
int node, distance;
public Node(int node, int distance) {
this.node = node;
this.distance = distance;
}
}
static class Pair implements Comparable{
int distance, node;
public Pair(int distance, int node) {
this.distance = distance;
this.node = node;
}
public int compareTo(Pair o) {
return this.distance - o.distance;
}
}
public static List shortestPath(int n, int m, int edges[][]) {
// code here
ArrayList adjList = new ArrayList();
for(int i=0;i
same
“understood”