|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
|
|
#1
December 15th, 2003, 12:05 PM
|
|||
|
|||
|
Dijkstra Shortest path Algorithm
Suppose an edge in the graph is deleted. How can I go about updating the shortest paths, without running the entire Disjkstra algorithm again?
|
|
#3
May 6th, 2004, 12:04 AM
|
|||
|
|||
|
I'm a new user here. may i know what script do u use to perform the djikstra algorithm? can i use VB.Net?Can i get the script from u instead?
|
|
#4
May 6th, 2004, 04:47 AM
|
|||
|
|||
|
I think it is possible. However this is just off the top of my head, so may be total bollocks.
If a shortest path between A and B does not contain the removed edge, then it will still be the shortest path between those two points. So go through the set of shortest paths and remove those that contain the missing edge. This will leave you with a set of known shortest paths. You can then run the algorithm again with this set as the initial data, instead of the empty set. Dave - The Developers' Coach
|
|
| Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Dijkstra Shortest path Algorithm |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
 |
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
