0

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?

toolic
  • 57,801
  • 17
  • 75
  • 117
Suryansu Dash
  • 95
  • 8

2 Answers2

1

Find all possible paths between two nodes

You could use bruteforce here, but it is possible, that you get a lot of paths, and it will really take years for bigger graphs (>100 nodes, depending on a lot of facotrs).

Arrange the paths in ascending order, based on their path length (as given by the edge weights), say top 5 atleast.

Simply sort them, and take the 5 first. (You could use a combination of a list of edges and an integer/double for the length of the path).

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.

Even finding all possible paths between two nodes is NP-Hard (Source, it's for undirected graphs, but is still valid). You will have to use heuristics.

What do you mean with a larger number of nodes? Do you mean 100 or 100 million? It depends on your context.

JCWasmx86
  • 3,473
  • 2
  • 11
  • 29
  • Is there any other way than bruteforce to approach this problem? And yes, by larger nodes I mean around 100-200 nodes at most. Is there a way to solve this problem in lesser time? Also, what do you mean by factors? I am new to graph theory so I thought in this case only weights of the edges will work out. – Suryansu Dash Aug 06 '20 at 17:14
  • I can't think of another way than bruteforce, I don't think you can solve it in less time. I mean with factors things like the number of edges (If you have 10 nodes and 2 edges, the time will be less than with 10 nodes and 90 edges). – JCWasmx86 Aug 06 '20 at 17:16
  • Oh, I see. Also, another query, by heuristics approach, you mean approaches like A* or best first search like algorithms? – Suryansu Dash Aug 06 '20 at 17:18
  • Something like that. – JCWasmx86 Aug 06 '20 at 17:19
  • Ok great, thanks a lot for the help. I will wait a bit more, else accept your solution for this post. – Suryansu Dash Aug 06 '20 at 17:21
  • @SuryansuDash FishingCode's answer is a bit better, as it shows you Dijkstra's Algorithm, that does exactly what you want, but not using the ways you want (Generating hundreds of millions of paths) – JCWasmx86 Aug 06 '20 at 17:37
  • I checked it now, thanks a lot for your help though :) – Suryansu Dash Aug 06 '20 at 20:02
1

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.

de_classified
  • 1,927
  • 1
  • 15
  • 19