Shortest path, after adding one link?

Topics: algorithm
Nov 12, 2009 at 9:15 AM

Suppose I have a directed weighted graph, where I have used Dijkstra to calculate the shortest path from O to D.

Then I add one link somewhere in the graph. I am sure there is a way to update the shortest-path-tree without having to restart the SP algo?

 

/A

 

Nov 19, 2009 at 12:00 PM

Update on updating the shortest-path-tree without having to restart the SP algo....

I found an algorithm in Figure 4.5 in

http://www.springerlink.com/content/d126702146j65554/fulltext.pdf

So, let's see how to implement this one in QuickGraph....

 

/A

 

Coordinator
Nov 29, 2009 at 4:00 AM

Thanks for the link!