Shortest path with limited number of edges used



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
.



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 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. ...
    (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)