Hello everyone,I hope you all are in good health. So, i was recently studying graphs and started with the Floyd-Warshall algorithm. I am pretty new to this, and this would be my first implementation of the respective algorithm.
I came across problems on codeforces and uva online judge, with the implementation of the algorithm.
links -
Greg and Graph, codeforces.
Geonosis, UVA online judge.
Can anyone please help me with the solution? Why do we add all the vertices backwards and not remove them in the order given to us . Is it because of the time complexity will reach O(n^4)?
please forgive me if I said something wrong, I'm just trying to learn my way through.
thanks in advance ^-^
Fun fact is that I was thinking about this problem today because I met an other one who seemed similar to it, but eventually it was not.
What amazes me in these problems is how complexity can be different if you are "building" (adding vertices) a solution rather than "destroying" (removing vertices) it. Idea of floyd is to build a solution. Order of foor loops matters. It is very important the outer-most loop to be related to the "middle" vertex. Now in the cf problem you are referring to, each time we are adding a vertex (v), we consider it as a middle point. An interesting thing here is that we have already calculated shortest path between (v) and (w) using only middle vertices from the ones we have processed. This means that, if shortest path of (a)-(b) now pass from the new (v), we have already calculated d(a, v) and d(b, v) in the current graph. This kind of calculation which let us calculate yet unused vertices is not causing us problem because using a "boolean visited" array we can know what to include in our sum and what no.
So, I think here "building" logic works better because even if we calculate more things than we currently need we can easily know which are important and which are not. On the other hand if we would try to build a logic which removes vertices, we should in some way to re-calculate all shortest paths and maybe that would mean to call floyd again naively, giving us O(n^4).
A very related subject is with union-find. If for example problems ask us to remove vertices and find connected components maybe it would be better to do the reverse. Because union-find can easily merge components, but removing a vertex can create multiple subgraphs which would lead us to bigger complexity.
could you also post the link of other problem if possible.
There is no actual link. I just remember that I had faced something related to it in the past and just referred it !
oh, thanks a lot! the picture of the algorithm is a lot clear now ^^
You are welcome :)
The key point is understanding how Floyd Warshall works. You can check it here.
I've solved Greg and Graph some days ago link to my submission.
Adding a node to a graph and updating distances is trivial. Deleting a node means whole recalculation.
It happens not only with Floyd-Warshall, but with a lot other algorithms as well.
Consider graph component calculation. Adding an edge is the simplest thing, it either joins two nodes in the same component or not, so you do nothing or you merge two components. Now try to remove one edge...
Thinking the problem backwards helps in a lot of scenarios.