Shortest path with limited number of edges used
 From: Daniel Kraft <d@xxxxxxxx>
 Date: Wed, 16 Jul 2008 15:30:40 +0200
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 210 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: ArcBarSamValWiz, DwaElfGnoHumOrc, LawNeuCha, FemMal
Underway: CavDwaLawFem
To go: CavHeaKniMonPriRanRogTou
.
Relevant Pages
 Re: Distance normalized TSP algorithm
... Unless you are aiming for a probabilistic algorithm, ... graph, a perfect one. ... I call a graph where costs match well with distance a well correlated ... do not gives the degree of correlation. ... (comp.lang.java.programmer)  Re: Distance normalized TSP algorithm
... Make a larger graph containing two of these ... Define "match well with distance," please. ... tend to cost more, so it costs more to fly to a distant city than to ... which lead me to the distance normalized algorithm where all ... (comp.lang.java.programmer)  Re: Finding all paths between two vertices in a graph
... "connectedness" of any two given vertices A and B in an unweighted ... graph, where A and B are not directly connected, but have several ... distance) between each pair of vertices reasonably efficiently. ... altering the BFS algorithm, but I was wondering if anybody had further ... (sci.math)  Re: Shortest path with limited number of edges used
... Daniel Kraft wrote: ... in a graph *consistig of <= k edges*. ... If that helps, the graph I'm working with is fully connected, and k will be about 210 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. ... (comp.programming)  Re: Finding all paths between two vertices in a graph
... "connectedness" of any two given vertices A and B in an unweighted ... graph, where A and B are not directly connected, but have several ... an existing algorithm that is able to find all paths (up to a certain ... distance) between each pair of vertices reasonably efficiently. ... (sci.math) 
