md.ashif313's blog

Shortest path in weighted graph with maximum edge limit
By md.ashif313, history, 7 years ago, In English

I'm trying to find efficient algorithm for finding shortest path in weighted(Positive/Negative) graph with maximum edge limit.

For example, in the graph below if we demand the shortest path from A to C with restriction the path can contain at most two edges. It would be A->B->C and total cost 5 (Which is greater than A->D->E->C)

Weighted graph without negative edge.

I think when the graph is (directed or undirected) has no negative edge, we can use Dijkstra with little modification, such that we will keep the number of edges in the currently discovered shortest path from source to currently used vertex for relaxation. Is my idea OK? Or there is much better something?

And how can we solve the similar problem when the graph(directed) consists of negative edges(but no negative cycle)?

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think Bellman-Ford algorithm is exactly what you need

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi Morozov, Thank You for reply :) Can you please give me some more details about your Idea...

    And if you don't mind can you please specify any pitfall to use Dijkstra when the graph does not contain any negative edge.

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Calculate for each node x and nonnegative integer k < n the number dx, k, the length of the shortest path from the starting node to x which uses exactly k edges. The recurrence is similar to what you have in Dijkstra's algorithm, if edge weights are nonnegative, of course. If you have negative edges you can apply the same modification to the Bellman-Ford algorithm.

Maybe there is a faster solution though?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi Ivan, Thank You very much :)

    That's really a great and simple Idea :D

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, I am stuck at the exact same problem now. Were you able to figure out the solution for it?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It's Bellman-Ford's algorithm. Other alternatives include SPFA (Shortest path faster algorithm) and it has significant improvements. They're relatively the same complexity, but SPFA can have a best case O(M).

    → Reply