Re: n edges shortest path

From: rusolis@xxxxxxxxx (Michal Brzozowski)
Date: 27 Apr 2005 13:14:13 -0700

samipate@xxxxxxxxx wrote in message news:<1114550264.734142.128090@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>...
> Hello list
>
> Is there a well known algorithm that determines in an oriented graph
> the shortest path using exactly n edges ?

hello

One algorithm I can think of would be adding another axis to
the vertices, so instead of 1..k they would be:
(1,1) ... (k,1)
(1,2) ... (k,2)
..
..
..
(1,n) ... (k,n)

the second number in the pair would of course represent the number of edges
that you took to given vertex.
If you run the shortest-path algorithm on that graph, you would get
the anwser at (k,n) (assuming that you are looking for a path between 1 and k)

For big n, I don't know
.

Follow-Ups:
- Re: n edges shortest path
  - From: Per Vognsen

References:
- n edges shortest path
  - From: samipate

Prev by Date: Re: optimized string storage for phrases/dictionary
Next by Date: Re: P=NP: Linear Programming Formulation of the TSP
Previous by thread: Re: n edges shortest path
Next by thread: Re: n edges shortest path
Index(es):
- Date
- Thread

Relevant Pages

Re: Shortish paths
... For how many nodes and how many edges will the actual algorithm run ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
(comp.theory)
Re: which algorithm fits...
... >> for example, the 60th shortest path, that makes finding the right path ... >The most important thing that is still not known is how much memory you can ... >you can either do a depth first search, ... the algorithm appears to need some way to ...
(comp.programming)
Re: Shortish paths
... Remember I'm not asking for an algorithm, just for advice on what to ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
(comp.theory)
Re: Shortish paths
... original graph. ... The functionality of Dijkstra's original algorithm can be extended ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
(comp.theory)
Re: Shortish paths
... The functionality of Dijkstra's original algorithm can be extended ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
(comp.theory)