Shortest path with limited number of edges used
in [General Programming]
|
Prev: Info/books on shared libraries in Unix
Next: zero damenbekleidung bestellen damenbekleidung bestellen uebergroesse only damenbekleidung bestellen damenkleidung kaufen grosse
From: Daniel Kraft on 16 Jul 2008 09:30 Hi, I'm looking for an algorithm to find the shortest path between to nodes in a graph *consistig of <= k edges*. If that helps, the graph I'm working with is fully connected, and k will be about 2--10 or so, so nothing really large. I thought about using Dijkstra's and if it is possible to adapt it to my constraint; maybe saving for each node not only the distance from the start during the run, but the distances to the start for 0..k edges or something like that, but couldn't yet figure it out fully. Does already such an algorithm exist? I'm quite sure it does... Thank you very much, Daniel -- Done: Arc-Bar-Sam-Val-Wiz, Dwa-Elf-Gno-Hum-Orc, Law-Neu-Cha, Fem-Mal Underway: Cav-Dwa-Law-Fem To go: Cav-Hea-Kni-Mon-Pri-Ran-Rog-Tou
From: Thad Smith on 17 Jul 2008 08:56
Daniel Kraft wrote: > I'm looking for an algorithm to find the shortest path between to nodes > in a graph *consistig of <= k edges*. If that helps, the graph I'm > working with is fully connected, and k will be about 2--10 or so, so > nothing really large. > > I thought about using Dijkstra's and if it is possible to adapt it to my > constraint; maybe saving for each node not only the distance from the > start during the run, but the distances to the start for 0..k edges or > something like that, but couldn't yet figure it out fully. Your idea should work. Each time you from one node to another you update the minimum distance from start and pointer to previous node for each level of edge count. -- Thad |