So you mean my friend's algorithm works? As the modified graph can find
the shotest path 1->3 instead of 1->2->3.
jackyy
Atamyrat Hezretguliyew 寫道：
> 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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
