algorithmgraph-theorypath-findingdirected-graph

Find all simple path from node A to node B in direct weighted graph with the sum of weighs less a certain value?


I have a directed weighted graph G=(V,E), which may have loops.

I am trying to determine the best time efficient algorithm to accomplish task: to find all simple path in G between source and target node with total weight of edges in this path less than certain value (for convenience we denote this value as PATH_WEIGHT_LIMIT)

All weights is positive and can be float.

So, a prototype of my function will be:

def find_paths(G, source, target, path_weight_limit) 

Result paths may overlap, its fine.

Much like those discussed here, e.g.:

  1. algorithm for finding NUMBER of distinct paths from A to B in weighted, directed, cyclic graph
  2. find all simple path in UNDERICTED graph (NP-problem)

But I didn't find an algorithm to solve this specifically task that I posed above to find all simple path in G (directed, weighted, cyclic) between source and target node with total weight of edges in this path less than certain value

I think that should be used modified DFS algorithm with a focus on weights of current part of path. But I think it is not effective and maybe there are better algorithms to solve this.


Solution

  • Theoretically, every node has a weight of 1+, so loops won't be a problem because weight increases as a path grows. But... if any of your nodes have a cost/weight <= 0, then you should include a maximum time or depth in order to stop pathfinding.

    If you want perfect paths, use Djikstra's algorithm. If you don't care about perfection, use A*. When you create a list of candidate nodes, validate them before adding them to the search list. Any nodes that have a higher total weight than your maximum should be removed from the candidate list.

    So something like this:

    Current node -> List of candidate nodes --(are they less?)-> List of next nodes
    merge(list of search nodes, list of next nodes)
    

    Instead of stopping when you find a goal node, add goal nodes to a list and make paths when you finish pathfinding. Most implementations of pathfinding nodes look like this:

    Node
    - Node previous
    - depth, cost
    - misc data (coordinates, hp, gold, terrain, entity)
    

    Tracing the path is pretty easy: add the goal node to a list, then add previous to the list until previous = null. The list is your path.

    Pathfinding is a very powerful tool, but most of the algorithms and guides you can find online are introductions and even the best guide I found, Amit Patel's A* Tutorial, isn't very deep.

    Many pathfinding systems can only find one path because they're too specialized, so I generalized the algorithms. Below, you'll find an in-depth guide to pathfinding that has more information than you can find with google. The reason I include it is because it allows you to derive much more powerful pathfinding algorithms, such as finding multiple paths and goals, beginning from multiple starting locations, or even managing execution time. It will help you implement your algorithm.

    In-depth Pathfinding Guide

    Everything you need to make new pathfinding systems

    The essence of pathfinding is this algorithm:

    1. Start with a listopen of nodes (usually contains 1 item)
    2. Select the most promising1 node
      • If the node is a goal2, add it to a listgoal
      • if the node is valid, generate a list of adjacent3 candidate nodes (listcand)
    3. For each candidate, if it is invalid4, remove it from listcand. Afterwards, add listcand to listopen.
    4. Remove the selected node from listopen and add it to listclosed
    5. Repeat step 2 while pathfinding5

    Notes:

    [1]: This is where most pathfinding algorithms diverge; they prioritize nodes differently.

    [2]: Sometimes the goal node isn't a single location. There may be times that you want to find any node that has a certain object like a health kit, a shop, or an enemy player that's easy to kill. By checking the node with a goal() function, it becomes possible to define multiple end-points.

    [3]: candidate nodes don't need to be beside eachother. What you are doing is using a function f(node) = list(nodes). When searching a gamestate to get gold or health for a player, you can create nodes for actions like JUMP, ATTACK, REST, etc. In some cases, you'll want to validate the list of generated nodes before you add them.

    [4]: Invalid nodes are usually just nodes in listclosed that have been searched before. However, they can be nodes that are too far, nodes that collide with walls (really common), nodes that would reduce your player health to 0, etc. If you decide not to use node isn't in closed list as a condition, then your algorithm is allowed to backtrack (which can create infinite loops).

    [5]: You can implement the algorithm to stop when certain conditions are fulfilled. Normally this is assumed to be that 1 goal node is found, but there's so much you can do with this! You can stop pathfinding after a certain amount of time, which is excellent for game engines because you may need to pause to render frames and prevent lag. You can also stop searching if the node list becomes too big, keeping memory usage low. You can even stop once you have a certain amount of solutions.

    This boolean stop condition/function allows you to abort pathfinding whenever the pathfinder takes too long, hogs resources or falls into an infinite loop. On a single thread, this usually means you no longer need the pathfinder. For game engines, online game clients and GUI applications, I like to run the pathfinder in a second thread and wake it up whenever I need it. If the pathfinder doesn't find a path fast enough, a dumb AI makes quick decisions until pathfinding finishes.