"jackyy 写道：
"
> So you mean my friend's algorithm works? As the modified graph can find
> the shotest path 1->3 instead of 1->2->3.
No, Atamyrat Hezretguliyew means that doesn't work. As the edge's
number along the path also influence the choice of edge. I mean, the
shortest-path should be determined by the sum of the weight of edges
but not the sum of the weight the edges and the number of edges
multiples the absolute value of the most negative length.
>
> 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 [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
-~----------~----~----~----~------~----~------~--~---
