My friend has the following idea to get an algorithm for finding a shortest path tree on a graph whose edges may have negative length (but with no negative cycle):
(i) Examine the edges and find the edge e with the most negative length. (ii) Add |ℓ(e)|, the absolute value of the length of e, to the length of every edge. (iii) Run Dijkstra’s algorithm on the modified graph to find the shortest path tree and return it as the solution of the original graph. Do you think his idea works? I do not think so. However, I cannot raise any counter example yet. Can you help me to think one? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
