Just some thoughts, in industry when we solve problems, most of time, we do things in the simplest way, just like applying Bellman-Ford |V| times for ASAP problems. Because it is easy to implement, and we can save a lot of times from engineers. However when we look the problem thoroughly, there could be a much faster implementation if you preprocess the input (data) and transform them to reduce the problem to some existing solutions. And sometimes the pattern is not intuitive to be observed (who would think of re-weighting by telescope sum?), or it may cost more in implementation, since you need to prove its correctness. I think it's an engineer's duty to decide which way to go, and it's the essence of their job. This lecture reminds me of that..
doesn't connecting all vertices in V to a supernode s with 0 weight edges makes all delta(s, v) to 0, (and makes all h(v) = 0)? Or is the s in the Johnson's algorithm another s different from the supernode
Look at the case of a negative weight cycle in G. Then d(s,v) for any v in that cycle would still be -inf. Example path: s -> v - > follow cycle -> follow cycle …
I would like to point out an error in lecture note associated with this one. In the lecture, Jason mentioned that if there exists a minus inifinity shortest path between s and any vertices, there will be negative weight cycle in the original graph and so we can abort. But in the lecture note that is mirroring this part of the lecture, "So if reweighted graph has a negative-weight cycle, so does the original graph" -> it is actually not the reweighted graph that we are considering, this operation of adding s and checking if there is negative weight cycle is prior to the reweighing part. Hence "reweighted graph" should be rewritten into something like "modified graph Gs with a vertex s".
The telescope sum guarantees any path of "a pair of vertices" can be reweighted by the same value. But it doesn't maintain them in a global equally way to an entire graph. In other words, in a reweighted graph, the equality relation of edges could be changed. For example, A~D = 500 & B~Z = 300 may reweighted to A~D = 600 & B~Z = 700. So we cannot tell the edge relations rely on telescope-sum-reweighted graphs. This is the opposite of the intuitive add-weight-to-every-edge-till-non-negative method as at 22:22. That doesn't satisfying the reweighting requirement but it preserves the equality relation between edges. This is my blind spot, I was originally try to understand how it reweights while maintain the global relations.
It is "global" in the sense that ALL paths from u to v are reweighted with EQUAL bias h(u) - h(v). It is "local" in the sense that for any two pairs of vertices (u1, v1) and (u2, v2), there paths are reweighted with possibly UNEQUAL biases: h(u1) - h(v1) vs h(u2) - h(v2).
There really was not a very good pre-context given in this lecture for Johnsons algorithm. Now I've gone through it I have realised that essentially for the APSP problem at least in this course we are saying repeatedly doing SSP algorithms for each vertex is not too bad and we can accept this. However for the specific case of APSP with negative weights but no negative-weight cycle we can slightly optimise this with 'Johnson's algorithm. This algorithm does some tricks to make the graph into another graph which has positive weights but preserves shortest paths between each vertex. To do this it first uses Bellman-Ford. And then afterwards it repeatedly uses Dijkstra again from each vertex. This is still more optimal than doing Bellman-Ford from each vertex as we only have to do it once, rather than V times and instead do Dijkstra V times which saves some asymptotic complexity.
What should we do if for instance, the incoming edge is -10 and the outgoing edge is 1? It seems impossible to modify the graph in this way to make both edges positive.
Dijkstra is such an algorithm which is the SPF has extensive usage hence,is that possible to take the OR silent operation in the case of all Edge and Vertex processing an additive way. Logv is a portion we can neglect thus the common v and v additive e gives rise to a solution to the traversal. So,there is a normal situation wherein we can process the Dijkstra as SPF but not the Bellmans ford as the multiplicative but less efficient than Dikstra. A complex bit of Statistics as well as the total comparison is getting lessened.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
Just some thoughts, in industry when we solve problems, most of time, we do things in the simplest way, just like applying Bellman-Ford |V| times for ASAP problems. Because it is easy to implement, and we can save a lot of times from engineers.
However when we look the problem thoroughly, there could be a much faster implementation if you preprocess the input (data) and transform them to reduce the problem to some existing solutions.
And sometimes the pattern is not intuitive to be observed (who would think of re-weighting by telescope sum?), or it may cost more in implementation, since you need to prove its correctness.
I think it's an engineer's duty to decide which way to go, and it's the essence of their job.
This lecture reminds me of that..
doesn't connecting all vertices in V to a supernode s with 0 weight edges makes all delta(s, v) to 0, (and makes all h(v) = 0)? Or is the s in the Johnson's algorithm another s different from the supernode
Look at the case of a negative weight cycle in G. Then d(s,v) for any v in that cycle would still be -inf. Example path: s -> v - > follow cycle -> follow cycle …
I would like to point out an error in lecture note associated with this one. In the lecture, Jason mentioned that if there exists a minus inifinity shortest path between s and any vertices, there will be negative weight cycle in the original graph and so we can abort. But in the lecture note that is mirroring this part of the lecture, "So if reweighted graph has a negative-weight cycle, so does the original graph" -> it is actually not the reweighted graph that we are considering, this operation of adding s and checking if there is negative weight cycle is prior to the reweighing part. Hence "reweighted graph" should be rewritten into something like "modified graph Gs with a vertex s".
The telescope sum guarantees any path of "a pair of vertices" can be reweighted by the same value.
But it doesn't maintain them in a global equally way to an entire graph.
In other words, in a reweighted graph, the equality relation of edges could be changed.
For example,
A~D = 500 & B~Z = 300 may reweighted to A~D = 600 & B~Z = 700.
So we cannot tell the edge relations rely on telescope-sum-reweighted graphs.
This is the opposite of the intuitive add-weight-to-every-edge-till-non-negative method as at 22:22.
That doesn't satisfying the reweighting requirement but it preserves the equality relation between edges.
This is my blind spot, I was originally try to understand how it reweights while maintain the global relations.
It is "global" in the sense that ALL paths from u to v are reweighted with EQUAL bias h(u) - h(v).
It is "local" in the sense that for any two pairs of vertices (u1, v1) and (u2, v2), there paths are reweighted with possibly UNEQUAL biases: h(u1) - h(v1) vs h(u2) - h(v2).
There really was not a very good pre-context given in this lecture for Johnsons algorithm. Now I've gone through it I have realised that essentially for the APSP problem at least in this course we are saying repeatedly doing SSP algorithms for each vertex is not too bad and we can accept this. However for the specific case of APSP with negative weights but no negative-weight cycle we can slightly optimise this with 'Johnson's algorithm. This algorithm does some tricks to make the graph into another graph which has positive weights but preserves shortest paths between each vertex. To do this it first uses Bellman-Ford. And then afterwards it repeatedly uses Dijkstra again from each vertex. This is still more optimal than doing Bellman-Ford from each vertex as we only have to do it once, rather than V times and instead do Dijkstra V times which saves some asymptotic complexity.
What should we do if for instance, the incoming edge is -10 and the outgoing edge is 1? It seems impossible to modify the graph in this way to make both edges positive.
ok i see
Dijkstra is such an algorithm which is the SPF has extensive usage hence,is that possible to take the OR silent operation in the case of all Edge and Vertex
processing an additive way.
Logv is a portion we can neglect thus the common v and v additive e gives rise to a solution to the traversal.
So,there is a normal situation wherein we can process the Dijkstra as SPF but not the Bellmans ford as the multiplicative but less efficient than Dikstra.
A complex bit of Statistics as well as the total comparison is getting lessened.
Just achieved 9000 views !