On 12/6/06, jackyy <[EMAIL PROTECTED]> wrote:
>
> 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?
>
Here it is:
n=3
V = {1,2,3}
E = { (1,2,10), (1,3,7), (2,3,-4) }
source = 1
We add 4 to each edge and our modified graph becomes:
E2 = { (1,2,14), (1,3,11), (2,3,0) }
Now lets find shortest path from 1 to 3.
On our original graph, shortest path is 1->2->3, 10+(-4)=6
(Dijkstra will calculate it as 7, which is wrong)
On modified graph, 1->3 (11) is shorter than 1->2->3.(14+0)
atamyrat
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
