Shortest Path between all Pairs of Vertices | Floyd-Warshall's Algorithm Explained | Geekific

[@V-2427]

it is very very very easy to understand. thank you

[@sjsnnsndxdnendnndd5939]

At 3:19 why don’t we update with 16 as the path from A to E is currently infinity ?

[@manOfPlanetEarth]

Well, as I see it, only the steadiest get here😮 Guess it's the hardest video in playlist😵‍💫

[@alperarslan7458]

so you say it does not work with negative cycles, but when you add negative cycle check it means it works?

[@geekific]

Nope, the checks will only prevent you from returning wrong results back.

[@alperarslan7458]

@@geekific but you can find out a negative cycle by throwing error which means you found it. This is the only thing you can do when there is a negative cycle. There is no solution, isn't it?

[@manOfPlanetEarth]

Thank you, man, for educating.

[@geekific]

[@manOfPlanetEarth]

5:53 Um, shouldn't the path from "D" to itself be "-1" instead of "-2"?🤔

[@geekific]

That's the idea behind cycles we are trying to explain in this part of the video! You can through this cycle as many times as you want, and this -1 can go on infinitely...

[@manOfPlanetEarth]

@@geekific Yeah, that's true) I mean in this example "-1" is the very starting sign of negative cycle presence😉 Like: "0" on diagonal - still no negative cycle, "-1" - whoa, got a neg cycle.

[@manOfPlanetEarth]

7:39 Flankly, so far I couldn't figure out how Successor matrix is filled. I know that it's not a goal of the video but it's eating at me. I drew a few graphs of my own and also cannot create successor matrix for them🤷‍♂️ Sad moments.

[@geekific]

Are you encountering problems in terms of actual logic or in terms of implementation?

[@manOfPlanetEarth]

@@geekific In terms of actual logic:( It's my first tangible stumble for a long time. I already decided to put this question aside. It's not a pivot, get back to it some time. I understand how to figure out first matrix (with costs) through transitional closure but can't turn it into successors matrix.

[@geekific]

Start at 6:50, here are the initial vertices that are directly connected. So, the first row says that in order to go from A to B we need to pass by B directly, there are no intermediate nodes, same goes to (A, C), (B, D) etc. Then at 7:02, we are saying that initially if we wanted to go from A to D we had no way of doing that, but with the help of intermediate nodes we know that we can go through B to reach D starting from A. So, now, if we want to find the path from A to D, we check the cell (A, D), it says B, meaning that in order to reach D from A we first need to go through B, hence we need to find (A, B), okay! lets do that, if we check the cell (A, B) it says B = destination, meaning the full path is A -> B -> D. Hope I could help! Let me know if you're still struggling!

[@manOfPlanetEarth]

Yeah, really, what an algorithm... God, save me.. upd. Well, what to say. This algo is one of those which you have to describe with many-many words long and lengthy and think at the end "how will I put this monster into code?!😱😵‍💫" But then you see result code and you: "Is that how it's done?". The code is brief and simple. This algo is one of those. Very illuminating algorithm. ------ Well, now avl and red-bull trees are waiting for me. Jesus Christ!!🤬 Endless crap.