Search code examples
algorithmgraphshortest-path

What algorithm should I use to get all possible paths in a directed weighted graph, with positive weights?

I have a directed weighted graph, with positive weights, which looks something like this :- enter image description here

What I am trying to do is:-

  1. Find all possible paths between two nodes.
  2. Arrange the paths in ascending order, based on their path length (as given by the edge weights), say top 5 atleast.
  3. Use an optimal way to do so, so that even in cases of larger number of nodes, the program won't take much time computing.

E.g.:- Say my initial node is d, and final node is c. So the output should be something like

d to c = 11
d to e to c = 17
d to b to c = 25
d to b to a to c = 31
d to b to a to f to c = 38

How can I achieve this?

Solution

  • The best approach would be to take the Dijkstra’s shortest path algorithm, we can get a shortest path in O(E + VLogV) time.

    Take this basic approach to help you find the shortest path possible:

    Look at all nodes directly adjacent to the starting node. The values carried by the edges connecting the start and these adjacent nodes are the shortest distances to each respective node.

    Record these distances on the node - overwriting infinity - and also cross off the nodes, meaning that their shortest path has been found.

    Select one of the nodes which has had its shortest path calculated, we’ll call this our pivot. Look at the nodes adjacent to it (we’ll call these our destination nodes) and the distances separating them.

    For every ending (destination node): If the value in the pivot plus the edge value connecting it totals less than the destination node’s value, then update its value, as a new shorter path has been found. If all routes to this destination node have been explored, it can be crossed off.

    Repeat step 2 until all nodes have been crossed off. We now have a graph where the values held in any node will be the shortest distance to it from the start node.