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

In case you are thinking to buy courses, please check below:

---------------------------------------------------------------------------------------------------------------------------

[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

[coding]

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

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

[ayanangshudasmajumder]

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

[kthamim]

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

[rajkumarvb]

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

[harshitpandey]

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 :)

[babulalyadav]

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
.

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

[kopalpareek]

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

[nidhinishad]

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<dist[adjNode]:
#erase if existed in set
if dist[adjNode]!=float('inf'):
# means it has been visited and has more weight
# so we will remove it from the set before inserting
s.remove((dist[adjNode], adjNode))
dist[adjNode]=dis+edgW
s.add((dist[adjNode], adjNode))
return dist

[prasenjitsutradhar]

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<Pair> {
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, adj, int S)
{
TreeSet<Pair> st = new TreeSet<>();

int[] dist = new int[V];
for(int i=0; i<V; i++) {
dist[i] = (int) 1e9;
}


dist[S] = 0;
st.add(new Pair(0, S));

while(st.size() > 0) {
Pair curr = st.pollFirst();
int currNode = curr.node;
int currDist = curr.dist;

for(List<Integer> 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;
}
}

[techcraving]

we are greatful to have someone like you on youtube 🙏

[durgaprasad-gndk]

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

[cinime]

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

[abhishekgautam]

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.

[amanasrani]

Striver, without you DSA would be so thank You 🙏

[jivanmainali]

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 ?

[Lovekush-kxkz]

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 🥺💗

[studyonline]

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)