CODEWITHSUNDEEP
graphpathheuristics
ali
ali

Reputation: 21

how to find all random paths between two node in graph to construct initial population in genetic algorithm

I want to create the initial population in a genetic algorithm. a population consists of paths between two nodes ( source and destination). how to find all possible paths between two nodes in an undirected graph? Thanks

Upvotes: 1

Views: 278

Answers (1)

Max
Max

Reputation: 37

You could take a recursive approach to this problem. Do something along the lines of the following. (be warned I have not refined this).

  • Start by selecting a random node from the graph as a start node. And select a random node as the end node.

  • Look at all the connections to other nodes from the start one. Do not return to previous nodes. If there are no possible connections left stop.

  • If the node is the end node then stop and record the path. If not, then look at all the connections to that node, and repeat this step.

  • Repeat this process with every pair of nodes in the graph.

I'm sure you can see the recursive part to this solution. I'm afraid I cannot write up this solution currently but I hope this might point you in the right direction.

Upvotes: 0

Related Questions