3 ms·
A sibling comment linking to Johnson's algorithm shows a way to do it. To me, adding a constant to all edges seems like an obvious idea to try-- but one issue
by shoo 3y ago
A sibling comment linking to Johnson's algorithm shows a way to do it.
To me, adding a constant to all edges seems like an obvious idea to try-- but one issue is that it will distort the ranking for paths that have different numbers of edges. Ideally a normalisation would preserve the ranking of paths so that a path with minimal unnormalised weight would also be a path of minimal normalised weight. But ranking won't be preserved by adding a constant C to all edge weights, now paths with more edges will be unfairly penalised.
- pedrosorio 3y ago> To me, adding a constant to all edges seems like an obvious idea to try Yeah, as you explained that is not useful because it does not preserve the shortest-path of the original graph (which is the reason we are making all edges non-negative in the first place). That is why Johnson's algorithm adds an edge-dependent weight to each of the edges.
- thomasahle 3y agoJohnson's algorithm appears to run Bellman–Ford as a sub-routine. At that point you are already spending |V||E| time, so you are not getting anywhere close to the performance of Dijkstra and the new algorithm. But I guess you are saying that this preprocessing is OK if you need to run many single-source-shortest-path queries on the graph.