0

I need to find the count and enumerate ALL the shortest paths from a source node to a destination node. The edges may contain negative weights. I am unable to come up with an algorithm to do this.

Can someone help figure out how to go about this.

user3482434
  • 11
  • 3

1 Answers1

0

There are well known algorithms for finding the shortest path. Most notably Dijkstra's algorithm. Only Dijkstra's algorithm doesn't like negative edges (actually negative cycles). But Bellman-Ford doesn't mind them and it fairly simple to implement.

Malt
  • 28,965
  • 9
  • 65
  • 105
  • Counter-example: A-10->B-10->C. A-25->C. Now add 10 to all edges. Direct route is suddenly less expensive. Use Bellman-Ford instead: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm – Stefan Haustein Nov 04 '17 at 23:39
  • @StefanHaustein You're right. I was thinking about minimum spanning trees. – Malt Nov 05 '17 at 00:04
  • 1
    But I need to find all the shortest paths not just one shortest path. How do i do that? – user3482434 Nov 05 '17 at 03:32