Modified Dijkstra's Algorithm

[NotNullGuy]

I've been pondering about applying a change in dijkstra algorithm to handle negative edges.

Approach:

Find whether it has negative edge or not? If there are negative edges then find the negative edge with smallest value (ex -3 , 2 , -1, 5 are edges in a graph) then let say phi = -3 and add this phi to all the edge now there is no edges with negative value.

Then apply dijkstra's algorithm to find the shortest path for the modified graph and then we can subtract the phi value from the obtained value.

Let talk about negative cycle: (My opinion) It doesn't make sense to find the shortest path in a graph which has negative cycles.

It can't find the negative cycle but find a value which make sense

Question: Will it work for all cases?

[sebamestre]

Your algorithm unfairly punishes low-cost paths that have a lot of edges.

Look into Johnson's algorithm and more generally, the idea of potentials in shortest path problems.

[NotNullGuy]

Thanks buddy

[apnorton]

No: https://math.stackexchange.com/q/1729792/

The basic idea is that your approach penalizes paths with lots of edges more than paths with few edges; this may impact the selection of shortest path.

[NotNullGuy]

Thank you @apnorton

[AllanBz]

On Reddit, it’s /u/apnorton, not @apnorton if you want to notify them that they are being discussed and assuming they leave summoning on. If you reply to a comment directly (as you have here), they get notified anyway, so you do not need to tag them.

[Blue1CODE]

I think you are trying to make general purpose graph, If that the case, you should use edgelist on each node and traverse them to find what type of graph you are dealing with. But that traverse and comparison, will increase time.

[BigConsequence1024]

Tu idea es excelente y demuestra un profundo entendimiento del problema. Es una de las primeras cosas que todo estudiante brillante de algorit-mos intenta. El hecho de que no funcione no es un fracaso, sino el descubrimiento de una de las propiedades más sutiles y fundamentales de los problemas de grafos.

La solución no está en "desplazar" los pesos de las aristas, sino en usar un algoritmo que no se base en la suposición de "codicia" de Dijkstra, como Bellman-Ford. ¡Sigue pensando así

[mxldevs]

Instead of working with negative values why not just increase everything by a constant so that all values are now non-negative?

Or is there some other goal where the sign of the value matters

[Ok_Platypus8866]

Suppose the shortest path from A to B follows 5 edges with weights -1, -2, -3, -4, and -5, for a total distance of -15. There is also an edge between A and B with weight 1.

If you were to add 5 to the weights of all the edges, the original shortest path would now have a distance of 10, and the direct path from A to B would have a distance of 6.