G-33. Dijkstra's Algorithm - Using Set - Part 2

[@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

[@KiranKumar-sb3ti]

understood

[@U-DAY]

Striver we love you so much... and you r my big motivation and i learn english and expalining skills from u along with the concepts and It became like a habit for me whenever i solve a problem , i start hey striver listen and after explaining to u , i will go for code that much deeply connected i am.. and I was from south so i dont even know hindi that much but after watching no of videos of urs , hindi and english and ur slang i too adopted from u ... Please don't go from u tube we need to daily hear you and see you and take care my Brother...❤

[@ayanangshudasmajumder112]

Bhaiya apne itna accha samjhaya mera chota bhai bhi samajh gya. God Level Explanation!!!

[@shashwatkumar6965]

Bhaiya apne itna acha samjhaya mera chota bhai bada hogaya

[@ManishKumar-dk8hl]

@@shashwatkumar6965 😂😂

[@knowevertythingaboutyou]

kuch bhi🤣🤣🤣

[@nidhinishad7801]

People who are coding in python can use the sortedcontainers and import SortedSet from that. Here is the code: from sortedcontainers import SortedSet class Solution: #Function to find the shortest distance of all the vertices #from the source vertex S. def dijkstra(self, V, adj, S): s = SortedSet() dist = [float('inf') for i in range(V)] # dis,node s.add((0,S)) dist[S]=0 while s: dis,node = s[0] s.remove((dis,node)) for i in adj[node]: adjNode,edgW = i if dis+edgW

[@AshmitIITH]

thanks bro

[@harshitpandey8304]

Comparison b/w PQ and set : Incase of PQ, the maximum heap size can go upto E = number of edges, leading to complexity = O(E*logE). Incase of set, the maximum set size can go upto V =. number of vertices, leading to complexity = O(E*logV). Happy to be corrected :)

[@lakshsinghania]

After watching the G-34 video and commenting this for the first one: as u said the maximum heap size can go upto E thats V² as considering the extreme case that striver have taken in G-34 for every node its connected to V-1 nodes and there are V nodes in the graph so (V-1)*V = V² thats the max heap size so the while(!pq.empty()) line runs for V²=E or V only ? i think u r correct as the example taken in G-32 video the pq is taking 7 items and there are only 6 nodes so this line cant run for like max V times O(V² * (Pop vertex from pq) + no of edges on each node * Push vertex into pq) O(V² * (log(heap size) + ne * log(heap size)) // taking log(heap size) as common term O(V² * (log(heap size) * (V-1 + 1)) O(V² * (log(heap size) * (V)) O(V²*V * (log(heap size)) O(V²*V x (log(V²)) and V²=E ( total no of edges) therefore its *O(E*V * Log E)* im not getting *O(E*logE)* this for pq

[@lakshsinghania]

could u say whether im wrong or not ? if yes where ?

[@nagame859]

thank you!

[@chillkro25]

Hii bro kis year me ho

[@harshitpandey8304]

Working. Total ~5 YOE Joined Salesforce 4 months back. Was at Amazon before that

[@coding8000]

When Striver gave his google interview, 😂"The Interviewer might be thinking, am I a "INTERVIWER" or a "STUDENT" of him. 😂"

[@vijaykumarbille7727]

😂

[@Ayush37262]

Bery Bery Funny Bro, I can't control my laugh 🤣🤣🤣🤣🤣🤣 Bruhhhhhh 🤡🤡🤡

[@suryanshrastogi1340]

@@Ayush37262 youtube comments trying to be funny turns out to be actually very lame

[@AyushVerma-ui7re]

@@Ayush37262 😂

[@kthamim7552]

i told about you when i attend my zoho interview in HR round and now i am developer at zoho 😇

[@BipinDas-kj2op]

Refer kardo😂

[@rajkumarvb5197]

Your videos are one of a kind man. Thanks a lot for everything you provided to people like us.

[@kopalpareek65]

I don't have words for this kinda EXPLAINATION !!🙇‍♀🙇‍♀🙇‍♀🙇‍♀🙇‍♀🙇‍♀🙇‍♀

[@durgaprasad-gn4dk]

Ofcourse, I can proudly say that I learnt all these DSA concepts from Striver in Take U Forward channel. Thank you

[@techcraving6641]

we are greatful to have someone like you on youtube 🙏

[@abhishekgautam1597]

In Java, I think we can use TreeSet, since it inserts elements in a sorted order so the minimum will always be the first element of the TreeSet. We might need to write a custom comparator for the sorting order based on distances.

[@mrudul5018]

I tried this but I faced a problem. By Using Treeset we will be able to run comparator only on one field of the pair that we are storing. Thus either we can store unique sorted vertices or unique sorted distances. But we want unique vertices with sorted distances.

[@saad5527]

@@mrudul5018 The below code is working fine, you just need to implement compareTo method of Comparable interface static int[] dijkstra(int V, ArrayList adj, int S){ TreeSet set=new TreeSet(); int[] dist=new int[V]; for(int i=0; i0){ Pair p=set.pollFirst(); int currNode=p.node; int currDist=p.dist; for(int i=0; i

[@optCode]

@@mrudul5018 Can't we use a custom comparator like this ? SortedSet set = new TreeSet((Pair a, Pair b) -> { // Compare based on the first element of the Pair if (a.first == b.first) { // If the first elements are equal, compare based on the second element return Integer.compare(a.second, b.second); } // If the first elements are different, directly compare them return Integer.compare(a.first, b.first); });

[@gaurishaaaa]

Grateful to you and ya i'd definately tell the interviewer that i learnt it from you. 😂 Youre so great at what you do. HUGE respect striver.

[@babulalyadav4305]

00:04 Dijkstra's algorithm is implemented using the set data structure. 01:45 Explaining Dijkstra's Algorithm through a dry run on a set data structure 03:21 Using Dijkstra's Algorithm to find the shortest path 04:39 Updating the minimum distance values 06:15 Using a set to erase unnecessary paths in Dijkstra's Algorithm 07:49 Using set data structure can provide better complexity for certain operations 09:18 Implement Dijkstra's algorithm using a set 10:57 Implementing Dijkstra's Algorithm using a set .

[@shivanshkhare2724]

if you just use visited array along with priority queue, then you can skip the extra iterations , and that is more closer to what djikstra algo is than using sets unneccesarily

[@no_name45689]

Understood with good depth, like always. Thanks Striver sir.

[@Lovekush-kx5kz]

Ofcourse striver i am going to tell the interviewer If we have time during interview cuz you are the only one cuz of which I can gain intrest in coding otherwise I am zero in it 🥺💗

[@amanasrani507]

Striver, without you DSA would be so toughhhhh, thank You 🙏

[@studyonline3236]

In python, the set is unordered, unlike in C++ where it is sorted. To get the max use from PQ in python just use a visited list for the vertices. Mark the src node visited and you only push the adj nodes, that are unvisited, into the PQ. (OFC with extra space complexity due to the implementation of set in python)

[@shivanshuagrawal9532]

ANYONE HAVE IDEA ABOUT JAVA

[@dharanyuvi6951]

Thanks bro

[@shashwatkumar6965]

We can even use unordered_set/hashset to get O(1) amortized time. Because we don't need to keep the pairs sorted on distance, because if we get any distance less than already existing distance for a node, we can erase it from our unordered set. Though we have to specifically write a hash function to store pairs in unordered set. struct pair_hash { inline std::size_t operator()(const std::pair & v) const { return v.first*37+v.second; } }; unordered_set ust;

[@abhijitkumarsinha]

i didn't know that we can use pairs in unordered_set , i have to learn this.Thanks

[@chetanraghavv]

@@abhijitkumarsinha yup as far as I remember, anything that can be compared can be type of set as it is internally implemented as red-black tree but in case of unordered set, hash function is used which is by default only defined for primitive types like int, long, float and some non-primitive like string

[@subhranilnandy04]

Understood :) We can apparently use the TreeSet as a sorted set in Java... Below is the code: class Solution { static class Pair { int dist; int node; Pair(int _dist, int _node) { dist = _dist; node = _node; } } //Function to find the shortest distance of all the vertices static int[] dijkstra(int V, ArrayList adj, int S) { // Write your code here TreeSet set = new TreeSet( (p1,p2)-> p1.dist == p2.dist ? p1.node-p2.node : p1.dist-p2.dist ); int dist[] = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[S] = 0; set.add(new Pair(0,S)); while(!set.isEmpty()) { Pair curr = set.pollFirst(); for(ArrayList arr : adj.get(curr.node)) { // (node, wt) int nei = arr.get(0); int wt = arr.get(1); int newDist = curr.dist + wt; if(newDist < dist[nei]) { set.add(new Pair(newDist, nei)); if(dist[nei] < Integer.MAX_VALUE) set.remove(new Pair(dist[nei], nei)); // For removal dist[nei] = newDist; } } } return dist; } }

[@sidhantkumar9281]

amazed by your energy ...

[@Saurabh-lb1uv]

God level explaination! Thanks

[@aryashjain7893]

:) awesome obviously gonna tell the interviewer ,my teacher is RAJ NaaM to suna hi hoga

[@cinime]

Understood! Super amazing explanation as always, thank you very much!!

[@ayushjindal4981]

instead of removing the entry fro the set, just ignore the entry when you encounter it. This would save both removal time and extra iterations time.

[@sajal..saraf...2455]

Understood all lectures till this one Thanks sir

[@sriharsha5867]

The below Java code with TreeSet implementation works for Dijskstra's Algorithm static int[] dijkstra(int V, ArrayList adj, int S) { // Write your code here TreeSet set = new TreeSet((node1, node2) -> { if (node1.value != node2.value && node1.dist == node2.dist){ return 1; } return node1.dist - node2.dist; }); set.add(new Node(S, 0)); int[] dist = new int[V]; for (int i = 0; i < V; i++) { dist[i] = (int)1e9; } dist[S] = 0; while (!set.isEmpty()) { Node node = set.pollFirst(); for (ArrayList adjNodes : adj.get(node.value)) { int adjNode = adjNodes.get(0); int adjNodeDist = adjNodes.get(1); if (dist[node.value] + adjNodeDist < dist[adjNode]) { set.add(new Node(adjNode, dist[node.value] + adjNodeDist)); dist[adjNode] = dist[node.value] + adjNodeDist; } } } return dist; }

[@AyushMishra-b8w]

use visited array in priority queue implementation and whenever you reach a node that is already visited skip that it will work similar to set vector dijkstra(vector adj[],int v,int src){ vector vis(v,false); vector dist(v,INT_MAX); //{x1,x2}=> x1-weight ,x2-edge priority_queue pq; pq.push({0,src}); dist[src]=0; while(!pq.empty()){ int u=pq.top().second; pq.pop(); if(vis[u] == true) continue; vis[u]=true; for(auto x:adj[u]) if(vis[x.first] == false && dist[x.first]>dist[u]+x.second){ dist[x.first]=dist[u]+x.second; pq.push({dist[x.first],x.first}); } }

[@sanyattaneja8551]

Rather than erasing from the set can't we just change the distance stored in the set then least distance one would be stored and we don't have to call erase and there would be no iterations for the same bigger distance nodes Happy to be corrected

[@TheRandomPerson49]

we can't directly change values as we do in array. We have to traverse it. so erasing is the right option

[@simplymaths5487]

Sera bojhao dada 😎

[@parul8334]

I love u so much can't explain in words, thanks for providing so much good content

[@tiktikgoes9]

Understood, Thank you striver!!

[@smile8510]

Understood! awesome explanation Got the concept in one go

[@travellersseek5968]

Hey Striver! If possible, please do include some more videos in DP playlist.

[@jivanmainali1742]

could not understand like even in pq you can delete that node which is already there when we found better option , so how come set makes thing different ?

[@KOTAGIRICHAITHANYAKOTAGIRICHAI]

same doubt

[@ShubhamA_]

Understood . Thanks for the explaination

[@kshithi2864]

Hello Striver!Thank you yor crystal clear explanation .UNDERSTOOD

[@pratimkundu4829]

Hey! just had one doubt will the T.C of the priority queue method be O(ElogE) instead of O(ElogV) as there can be more than one instance of a node in the priority queue whereas in the treeset method it will be O(ElogV) ?

[@takeUforward]

Yes

[@rijumondal6876]

Excellent job

[@yashsomani3042]

Understood Very well explained , Thank you so much!

[@jyothiyadav2595]

Understoood

[@prasenjitsutradhar3368]

This is code for Java guys: In java, we have to implement a custom Pair class that implements comparable interface along with our own implementation of 1. "compareTo" method for comparing two pairs 2. "equals" method for equality of pairs you can implement "hasCode" & "toString", but not needed! // Here is the code: class Pair implements Comparable { int dist; int node; Pair(int dist, int node) { this.dist = dist; this.node = node; } @Override public int compareTo(Pair other) { if(this.dist != other.dist) { return Integer.compare(this.dist, other.dist); } else { return Integer.compare(this.node, other.node); } } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Pair pair = (Pair) o; return this.dist == pair.dist && this.node == pair.node; } } class Solution { //Function to find the shortest distance of all the vertices //from the source vertex S. static int[] dijkstra(int V, ArrayList adj, int S) { TreeSet st = new TreeSet(); int[] dist = new int[V]; for(int i=0; i 0) { Pair curr = st.pollFirst(); int currNode = curr.node; int currDist = curr.dist; for(List adjacent : adj.get(currNode)) { int adjNode = adjacent.get(0); int adjDist = adjacent.get(1); if(dist[currNode] + adjDist < dist[adjNode]) { // erase if it exists if(dist[adjNode] != 1e9) st.remove(new Pair(dist[adjNode], adjNode)); dist[adjNode] = dist[currNode] + adjDist; st.add(new Pair(dist[adjNode], adjNode)); } } } return dist; } }

[@Sp_Global-oc4tf]

better than Bhaiya did's course.

[@CodeMode9313]

quite good explanation

[@hemanthkumar516]

for java use this data structure as alternative to pair in c++ TreeSet ts=new TreeSet(new Comparator(){ @Override public int compare(Map.Entry a,Map.Entry b){ return a.getKey()-b.getKey(); } });

[@sayakbasak587]

can you please tell why set cant be used in java

[@rishitmehrotra3201]

hats off striver

[@lyricallava6014]

In Java, we can remove from the priority queue only. See my implementation below. class Pair{ int d; // distance int n; // node Pair(int d,int n){ this.d=d; this.n=n; } } class Solution { //Function to find the shortest distance of all the vertices //from the source vertex S. static int[] dijkstra(int v, ArrayList adj, int s) { // Write your code here PriorityQueue pq = new PriorityQueue((a,b)->a.d - b.d); int distance[] = new int[v]; for(int i=0;i

[@tasneemayham974]

Dang it! So, Java really can't implement the set huh?? Is it because there is no get method? I tried implementing it, and that's where I got stuck. No way to get the pair out.

[@KOTAGIRICHAITHANYAKOTAGIRICHAI]

in java treesets why are we unable to remove the duplicate pair? is there any method to remove ? or it doesnt work in treesets

[@chiragyadav5467]

great explaination bhaiya :))))))))))

[@aditya_raj7827]

understood bhaiya❤❤

[@parvathivanapilli8572]

Understood great explanation ❤

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@KUMARSAURABH-s5i]

godly explaination!!

[@UECAshutoshKumar]

Thank you sir 😁

[@somsk56]

You teach us well striver and You want from me to tell the interviewer "I have learned all this from striver" If , Interviewer hates you then ? you know nah... some people hates some people with out any reason thats like " ise toh dekhke hi gussa hoga he"... Just kidding I will dfnly tell the interviewer :)

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@parthh3963]

i watched this whole video then realised i code in java :)

[@AkashRaj-vj6br]

great explanation

[@DevashishJose]

Understood, Thank you so much.

[@Saurabh-fe2bg]

why am i forgetting the previously visited videos 😪

[@gautamsaxena4647]

understood bhaiya

[@harshsoni4812]

nice beard striver ,thanks for video i understood the assignment

[@Learnprogramming-q7f]

Thank you forward

[@sudhadevi6692]

Thx bhaiya for all this❤

[@vishwajeet_singh__]

You are amzing

[@googleit2490]

Understood :) Sep'2, 2023 11:14 am

[@b_01_aditidonode43]

understood sir, thanks a lot

[@Aniketyadav-b6s]

In priority queue, we can use visited array to remove the multiple occurrence like {10,5} after executing {8,5}. I do not understand why need of set, hope get to know in future.

[@Manmohanshukla420]

same question, did you figured it out?

[@datastructuresandalgorithm9370]

I think,tehre is no such diffenrce.There are mutiple ways to choose Data structures.So,we can use both set and Priority queue.

[@-VLaharika]

Understood 👍

[@The_Shubham_Soni]

UNDERSTOOD.

[@kozukioden1177]

How about use the PQ and then whenever you pop out the top element just do a simple check. Is the distance for this node in the array better than what I got in the PQ? if yes you can simply skip exploring this path. This takes care of redundantly exploring sub optimal paths and gives us the benefit of faster retrievals of a min heap : )

[@bhavyabansal7145]

Why we are not able to erase from PQ?? Amazing Explanation btw. Understood..

[@pratikshadhole6694]

understood..always

[@sanchitasingh4248]

Understood!! yayyyy!!

[@mugambo5505]

nice explanation brother 😍

[@anushkachauhan110]

Understood!

[@priyanshvatsal9791]

Understood 😇

[@shambhavikhare9850]

amazing video

[@sysfailureexe6038]

Understood !!

[@suryakiran2970]

Understood❤

[@sarthakkabra8156]

gazab explanation

[@gnes04]

Striver your content is very helpful but one suggestion... Please make the videos shorter and more concise. I feel most of us can understand still, and we won't get bored. Plus it's easier to watch to revise if the vids are shorter.

[@abhishekanand9430]

thanks

[@pratip475]

I think we can use TreeMap here in java

[@Manmohanshukla420]

In the priority queue implementation, we will first receive (8,5) from the top and process the neighbors of Node 5. The distance of Node 5 would have also updated to 8 while making that entry in the priority queue. So later when we receive (10,5) we can simply check if the already updated distance of Node 5 (which will be 8) is lesser than the new distance (10). If so, we simply continue the loop and not process Node 5. OR We can also use a vector to keep track of visited nodes, and if the node is already visited (via (8,5)) we ignore the current entry (10, 5). Any suggestions whether that will be a better approach than deleting elements in the set?

[@akuma_168]

I guess yeah we could just simply avoid processing (10,5) if we have already stored a smaller dist.

[@LBK3]

understood ❤

[@parshchoradia9909]

UnderStood Sir!

[@akashsahu2571]

yes

[@KuchBhi-bs7sc]

better than paid ones

[@TrendyGamer007]

11:55 if in future ...when I appear for interview ... and my interviewer asks me this ... I will proudly say him ... that i learned this from @striver @takeUforward

[@keertilata20]

thank you so much

[@mriduljain6809]

Thanks😀😀

[@uknowme69420]

pls add this video in graph series, also there are many videos not added in the playlist

[@akashsingh9301]

thnku

[@rayyansyed2998]

"understood"

[@Deepanshupal-fx9db]

Nice way of explaining complex thing .But I have a doubt ,why to erase in set ,won't it be automatically done while using set ,we can just update ,it will update at that existing node only,I might be wrong. please confirm

[@princenagar1686]

This was not for Java people but yeah " Understood "

[@maneetgupta6749]

Understood

[@abinashbiswal3511]

can't we just use a visited array with the PQ to achieve the same functionality...?

[@abhisheknag1929]

yes please anyone answer

[@arnabbanik6403]

if we keep a boolean visited array to check if we have computed other distances from a particular node or not then can we not reduce the no. of iterations that you were talking about and also not have to use a log(n) time complexity for removing anything?

[@lokeshnaidu9324]

Yes same doubt