I would like to see a variance of this video adding removing snow on each house and man power on each not being necesarily the same and comencing from a particular house.
They are quite different. Kruskal's algorithm is used to find the minimum cost spanning tree, as depicted in the video, but Dijkstra is used in path finding from a given node in a graph, such that the result you get from dijkstra is the minimum distance and path required to reach all other nodes from a particular node.
They are similar in that the greedy or locally optimum solution ends up yielding the globally optimum solution. They are also similar in that they add/follow the cheapest edge of all valid choices in each iteration.
Wouldn't a way to ensure maximum efficiency be first to check if any nodes only have one edge and if so connect those edges first thefore removing that edge from any future comparisons and lowering the number of connections needed to reach n-1 nodes once you start the algorithm?
Not from an algorithmical standpoint. Since you'll need to account for those specific roads either way the only difference you introduce is when you account for them. And since you need to look them up separatly in your version you will need to look at all houses first to check if they have one connection. So you'll check houses which don't have only one connection in this step and then once again when you check them for the minimal weight path there.
Excuse me broher, but I didn't get the cut property. If you take the 3-weight road and then the 6-weigth road, you will end up needing 19 volunteers rather than 18. But you mention that according to this property, you will end up still with a subset of a minimal spannin tree. Could you explain me further please?
You go with both! Unless one of them creates a loop, then you skip it. If one would create a loop if the other is chosen, either is fine A loop is a path that starts and ends from the same place, ie the path 4-2-1 in the diagram in the video
@@ferusskywalker9167 oh, makes sense, going with both is kind of the same as going with one and then the other, in no specific order, and if taking both makes a loop, than taking either has the same effect on the total connections. Thanks.
Channel name checks out, I have never imagined I would say that in UA-cam.
Really great explanation.
Wow! Using real life example is the best teaching strategy.
Thank you very much.
You are a very good teacher, thank you for the video!
The best explanation I have ever seen. Thank you!
OMG the explanation is sooooo clear!
Great explanation video! Thank you!
Thank you Brian!
this is like when the main protagonist says the name of the movie
Greatest 4th wall break
My favorite part of the video is where he says "It's minimal spanning time" and spans all over the place.
This explanation is just too cool 😎😎😎😎
I would like to see a variance of this video adding removing snow on each house and man power on each not being necesarily the same and comencing from a particular house.
tnx now i got the proof
This guy is fr trying to convince me that 6
Look at min 9:00 to 9:31
fire vid keep posting, spanning tree!
This sounds so much like a variation of Dijkstra... am I wrong?
yes, you are wrong.
@@xiangli9588 thanks for the clarity and info packed response.
@@qwarlockz8017 but prim's algorithm is very similar to dijkstra
They are quite different. Kruskal's algorithm is used to find the minimum cost spanning tree, as depicted in the video, but Dijkstra is used in path finding from a given node in a graph, such that the result you get from dijkstra is the minimum distance and path required to reach all other nodes from a particular node.
They are similar in that the greedy or locally optimum solution ends up yielding the globally optimum solution. They are also similar in that they add/follow the cheapest edge of all valid choices in each iteration.
Thanks great video
Wouldn't a way to ensure maximum efficiency be first to check if any nodes only have one edge and if so connect those edges first thefore removing that edge from any future comparisons and lowering the number of connections needed to reach n-1 nodes once you start the algorithm?
Not from an algorithmical standpoint. Since you'll need to account for those specific roads either way the only difference you introduce is when you account for them. And since you need to look them up separatly in your version you will need to look at all houses first to check if they have one connection. So you'll check houses which don't have only one connection in this step and then once again when you check them for the minimal weight path there.
Greatest video ever
Thanks!
Excuse me broher, but I didn't get the cut property. If you take the 3-weight road and then the 6-weigth road, you will end up needing 19 volunteers rather than 18. But you mention that according to this property, you will end up still with a subset of a minimal spannin tree. Could you explain me further please?
Look at minute 9:00 to 9:32
The more interesting example would be when some non-direct roads are optimal, instead of point-to-point connections.
Wait, do the roads need to be cleared for people to travel to the blocked roads?
Yes.
They start clearing the road they can get to before getting to the others.
How to practice?
1. Connect a house to the other.
2. Take any two houses and connect them if one and only one has not connected.
3. Repeat 2.
what if two edges have the same weight?
You go with both! Unless one of them creates a loop, then you skip it. If one would create a loop if the other is chosen, either is fine
A loop is a path that starts and ends from the same place, ie the path 4-2-1 in the diagram in the video
@@ferusskywalker9167 oh, makes sense, going with both is kind of the same as going with one and then the other, in no specific order, and if taking both makes a loop, than taking either has the same effect on the total connections. Thanks.
Yoooo
Got lost
This explanation is just too cool 😎😎😎😎