G-35. Print Shortest Path - Dijkstra's Algorithm

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...
---------------------------------------------------------------------------------------------------------------------------

[@takeUforward]

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

[@muskangupta5873]

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

[@user-to3jj8lj8h]

yeah, i was confused where's the error in my code , then did this and passed all tetscases. Thanks!!

[@subhambachar]

Thanks for sharing 👍

[@princenagar1686]

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.

[@harleenkaur7751]

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.

[@Anony.musk01]

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 ^^

[@Roshansingh-fe6oh]

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;

[@wervana]

Solved this without watching the video. Took 2 hours but was worth it.

[@secretvibz6300]

Using that parent array was indeed a smart move 😀 !!

[@malvado8267]

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; }

[@loveyoubts2002]

it's showing tle error in the last test case

[@bhaktisharma9681]

Thank you so much!!! Was struggling to find my mistake!

[@loveyoubts2002]

@@bhaktisharma9681 did u find the solution ?? Then pls share it here 🙏

[@vaisakh5802]

Can you explain the code for graph creation? I'm not able to understand it

[@TON-108]

@@vaisakh5802 Watch initial videos of the series and understand how adjacency list maintains its adjacent nodes and weight

[@anshulsharma3137]

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

[@krishanpratap3286]

same same which year?

[@chethanrao8827]

And I solved it seeing ur hint (print LIS problem in dp)

[@anshulsharma3137]

@@krishanpratap3286 2020 passed out lol

[@shubhamraj25]

So are you looking to switch?

[@tusharbhart7018]

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; }

[@mohakhiphop]

damn nice 🔥

[@anuragbanerjee7516]

Great soln!!

[@vikasbeniwal6825]

same approach but tle on tc 4

[@uncoding-rohit]

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

[@tatipamularaviteja5245]

after line 20 we should push pair {0,1} initially to priority queue

[@aastikofficial6100]

you can but here we push {0,1} as we store in pq and we store in adj list hope you get this

[@cinime]

Understood! Such a wonderful explanation as always, thank you very much!!

[@mayank_rampuriya]

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

[@nagame859]

simple solution again.. thanks Striver. This Graph series feels easier than any other..❤

[@manojraj1332]

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.

[@sharathkumar8338]

one major doubt. How can we come up with these kind of solutions on our own???

[@takeUforward]

Practice, and practice...

[@SatyamEdits]

@@takeUforward and Observation.....

[@SatyamEdits]

because if you just keep practicing with closed eyes it would take an eternity to become a good problem solver.....

[@sharathkumar8338]

@@SatyamEdits Thank you

[@sharathkumar8338]

@@takeUforward Thank you

[@blitzkrieg7453]

GFG Apparantly have updated the testcases and this solution no longer is getting accepted

[@at9443]

you just have to append the shortest path distance at the beginning of the answer array

[@stith_pragya]

Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@aakashbansal6627]

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; } }

[@Vikassharma-rq5bh]

Your Code's output is: 1 46 11 51 It's Correct output is: 1 46 11 51 Output Difference 1 46 11 51

[@visheshkaran7083]

🤣😂

[@techbucks7339]

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} ; }

[@harshitsen5479]

We basically hashing the node for each updatation in the distances[adjNode]. I guess we can use HashMap too in this case.

[@AJ-xc3ks]

Just love ur way of solution Problem ❤️❤️

[@TON-108]

*Problem Solution

[@ng390]

Please use a proper compiler which shows output also so it will be more understandable.

[@kaichang8186]

understood, thanks for the great video

[@skt7088]

What if there are multiple shortest path and we have to print all of them? In that case what should we do?

[@hxveelbadtv]

Litterly saved me, deserves a subscription if you ask me!!!

[@kumarsatyam8527]

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)

[@nilimsankarbora5911]

Masterpiece Explanation

[@muchmunchies43]

Understood!

[@manasranjanmahapatra3729]

Understood! amazing Explanation.

[@ChintuMultiplanetry]

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.

[@dilsedhoni9229]

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]

[@vikasbeniwal6825]

almost same type of solution but got tle on case 4

[@GungunRamchandani]

Understood

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@subhambachar]

Understood ❤

[@UECAshutoshKumar]

Thank you sir 🙏

[@codewithme-ss6zl]

I am unable to find this Question on GFG

[@ooofrg4492]

Same

[@_hulk748]

Understood sir thankyou❤✨🙏🙇‍♂

[@amanasrani6405]

Understood Bhaiya

[@The_Shubham_Soni]

UNDERSTOOD.

[@-VLaharika]

Understood 👍

[@vishnu9134]

Huge effort 🤩

[@kasaiop]

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

[@takeUforward]

Areh pdhai ki channel ki reach hoti v nai h, word of mouth pe hi chalta h

[@smile8510]

@@takeUforward true

[@abdulsakibshekhayyub3498]

@@takeUforward still if u upload 1 or 2 video daily that will make us consistent

[@many987]

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.

[@DevashishJose]

understood, thank you so much.

[@abdulnisar7716]

My Attempt -> vector shortestPath(int n, int m, vector& edges) { vector adjList(n+1); vector distances(n+1,{INT_MAX,vector{}}); distances[1] = {0,{1}}; for(int i=0;i distances[node].first) continue; vector path = distances[node].second; for(auto pair : adjList[node]){ int adjNode = pair.first; int d = pair.second; if(distances[adjNode].first > d + dist) { distances[adjNode].first = d + dist; vector newPath = path; newPath.push_back(adjNode); distances[adjNode].second = newPath; pq.push({d + dist, adjNode}); } } } vector result; if(distances[n].first == INT_MAX) return {-1}; else { result.push_back(distances[n].first); for(auto node : distances[n].second) result.push_back(node); return result; } }

[@saikrishna872]

UNDERSTOOD

[@after_dark_777]

TLE on the last test case?

[@Sumeet_100]

just amazing !!

[@stranger1967]

how to handle multiple shorest path . This question was asked in my college intership OA of atlassian. PLss tell how to handle ?

[@priyanshvatsal9791]

Understood 😇

[@abdulazeemshaik7112]

understood

[@luckygamers8068]

Very much helpful 😍😍

[@parshchoradia9909]

UnderStood Sir!

[@Learnprogramming-q7f]

Thank you bhaiya

[@gautamsaxena4647]

understood bhaiya

[@sambhavagarwal5871]

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

[@smile8510]

same here

[@takeUforward]

glitch hai, ab working

[@AravinthRavichandran-n1k]

if the weight of both edges is same, we need to handle that based on nodes in Priority Queue

[@saitejaballa6759]

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?

[@yaswanthkosuru]

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.

[@rishabhraj8233]

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

[@p38_amankuldeep75]

understood💙💙💙

[@subodhkasaudhaniitk796]

Golden❤

[@arpitkhanulia7]

we dont have to initialize the whole parent array, just do parent [source] = source ;

[@lineshmalkam224]

understtooooddddd

[@viswanathvuppala4526]

Sir you forgot the case of returning list of -1s if path's not possible

[@shaddyrogue9430]

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.

[@kushaldas1703]

#tuf and take forward for crowdwork...#leetcode more solution needed

[@sypher4735]

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.

[@HONOREDONE-hk7pt]

lol, pair of size n is nothing but two arrays of size n clubbed together.

[@abhireshray8331]

nice:) explanation sir

[@bhavya8608]

understood!!

[@priyanshusrivastava2145]

its 3:54 am and busy creating my future😁😄

[@lokeshroy3944]

amazing

[@sahelidebnath5085]

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

[@azizazmir2159]

Huge love from south❤

[@tusarmundhra5560]

awesome

[@averylazyandweirdhuman]

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?

[@satyareddy8671]

understood sir

[@akshayanagelli5962]

what about no path case (-1)?

[@nisargpatel1443]

Always remember, where you are coming from!

[@NANUVALAADITHYA]

adj[it[0]] is a pair, how can we do a push_back to a pair??

[@tusharkumarroy-tj2qg]

understood and busted

[@raghavendrakalkutaki5175]

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

[@tasneemayham974]

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.

[@isheep9025]

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

[@HONOREDONE-hk7pt]

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.

[@adityaverma4902]

why cant we take max priority queue? its giving tle .

[@pihus3498]

understood :)

[@karthik53r35]

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

[@loveyoubts2002]

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 ?

[@tasneemayham974]

Yes, I solved it alone and got TLE using Java. But when I solved it using C++ it ran well!!

[@RahulGuptaa29]

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 )

[@isheep9025]

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

[@rayyansyed2998]

“understood”

[@abhinavsidharth1421]

can someone share link of question , it seems to be broken

[@brajeshmohanty2558]

Where can we find the java code for this video

[@mohdkhaleeq7468]

i am not able to write code by myself what to do?

[@ankitranjan88]

[@IdiotOfftheInternet]

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

[@umeshkaushik710]

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

[@SP-bx3ql]

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]

[@devabakare357]

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

[@Invincible2203]

showing (SIGABRT) on last 2 test cases, anyone?

[@saagerbabung5652]

am i missing something? since its undirected graph there definitely exists a path right? then y print (-1)

[@gamerversez5372]

What if the Node is Unreachable ?

[@saagerbabung5652]

@@gamerversez5372 undirected graph means it's reachable every where. Also there is only one component

[@thecap7249]

i was not able to solve it after pausing, what should I do. Am i that much incompetent.

[@hassanmehboob9078]

Would you please send me problem link

[@loveyoubts2002]

i can feel u bro, i'm also feeling same but only solution is practice

[@harshalgarg1676]

US

[@aniruddhadas1778]

Please anyone tell me from where could I learn the use of priority queue of min heap in java

[@vijayvardhan2698]

gfg