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
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...❤
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 :)
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
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
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.
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.
@@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
@@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); });
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)
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 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
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
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) ?
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 .
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
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 🥺💗
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; } }
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.
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}); } }
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 : )
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
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 ?
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(); } });
can't we just skip the element if the previous distance of reaching the node dist[node] is less than the distance covered to reach the node in the current path node[0] in the priority queue method itself that way we can implement the same logic without using stack
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?
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?
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; } }
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
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 :)
Please tell me that how are u so sure that set will definitely contain the already visited element. I mean it can also be possible that we have already erased it as well.
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.
Can anyone confirm my understanding that we can use a simple BFS also to find the shortest find only advantage using Dijkstra is that it will make less number of calculations to find the shortest path ???
