shortest path with specified number of edges

i'm looking for an algorithm that finds the shortest path between two vertices (i and j) in a graph that contains a specified number of edges, n. i have a dynamic program that looks at the shortest path to the destination with 开发者_如何转开发n-1 edges, but how can i be sure that the shortest path being found starts at i?

---

I guess the edges have different costs / lengths and that the constraint is that there are n edges, and among all paths from i to j that have exactly n individual edges, the goal is to find the one that has least total cost / length.

If you do this using dynamic programming, the recurrences are

spath(f, t, n): --- returns shortest path from 'f' to 't' that has 'n' edges

spath(x, x, 0) = [x] --- path that has only one vertex
spath(x, y, 0) = NO PATH --- when x != y

spath(f, t, n) =
  min cost path over (x is any node that is connected to t):
     spath(f, x, n-1) + [t] (x can be appended because there is edge x - t)

---

Your wording is ambiguous. Is n the number of edges in the graph or the number of hops in the path? If the latter, then it's not a shortest path anymore. If you mean the former then any popular shortest-path algorithm such as Dijkstra's will work. If you mean the latter, then do n iterations of BFS starting at i and locate your j in the nth frontier. If it's not there, then there's no path from i to j in n hops. Walk down the BFS frontiers to read your path.