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

Question

I have a directed weighted graph G = (V, E) that can have loops .

I am trying to determine the optimal effective algorithm for the task: t o find the entire simple path in G between the source and target node with the total weight of the edges in this path less than a certain value (for convenience, we denote this value as PATH_WEIGHT_LIMIT)

All weights are positive and can swim.

So the prototype of my function would be:

def find_paths(G, source, target, path_weight_limit) 

The paths of the result may overlap, its penalty.

Like the ones discussed here, for example:

• to find NUMBER different paths from A to B in a weighted, directional, circular graph
• find a simple path in the UNDERICTED column (NP problem)

But I did not find an algorithm for solving this specific problem, which I set above , to find the whole simple path in G (directional, weighted, cyclic) between the source and target node with a total weight of edges in this path less than a certain value

I think that a modified DFS algorithm should be used with emphasis on the weights of the current part of the path. But I think that this is not effective, and perhaps there are better algorithms for this.

Answer 1

The answer to your question

Theoretically, each node has a weight of 1+, so loops will not be a problem, because the weight increases as the path grows. But ... if any of your nodes has a cost / weight <= 0, then you must specify the maximum time or depth to stop the search for the path.

If you need perfect paths, use the Jikstra algorithm. If you don't care about excellence, use A *. When you create a list of candidate sites, check them before adding them to the search list. Any nodes with 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 the target node, add the target nodes to the list and create the paths when you finish the path search. Most implementations of path finding nodes look like this:

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

Tracing the path is pretty simple: add the target node to the list, then add previous to the list until previous = null . The list is your way.

Pathfinding is a very powerful tool, but most of the algorithms and guides you can find on the Internet are an introduction and even the best reference I found, Amit Patel A * Tutorial , is not very deep.

Many pathfinding systems can only find one path, because they are too specialized, so I generalized the algorithms. Below you will find a detailed guide to finding paths that contains more information than you can find on Google. The reason I enable this is because it allows you to get more powerful path-finding algorithms, such as finding multiple paths and targets, starting from multiple starting locations or even controlling runtimes. This will help you implement your algorithm.

Detailed Path Finder

All you need to create new tracking systems

The essence of the path search is the algorithm:

• Start with a list of _open nodes (usually contains 1 element)
• Choose the most promising ¹ node
• • If node is goal ² add it to _goal list
  • if node is valid, generate contiguous candidate list ³ ( _cand list)
• For each candidate, if it is invalid ⁴ remove it from the _cand list. Then add the _cand list to the _open list.
• Remove the selected node from the _open list and add it to the _closed list
• Repeat step 2 when searching for path ⁵

Notes:

[1]: here most path-finding algorithms diverge; they prioritize nodes in different ways.

• First In, First Out (oldest) - the simplest algorithm; just check the nodes in the order in which they are added to the _open list. Often looks like a BFS.
• First In, Last Out (newest) selects the new nodes added to the list. It can look a lot like DFS depending on your node generator.
• BFS seeks the smallest depth and is usually not the best algorithm to choose.
• DFS prioritizes the node with the greatest depth. He has a tendency to choose a path and continue to follow it, even if it lasts forever.
• The greedy chooses the lowest cost / weight that you want to switch to. Searching can be stuck in a high-cost area and end up with a road that has a very high cost compared to the ideal solution. Typically, A * is the best compromise between speed and optimality.
• Dijkstra chooses the node with the lowest total cost / weight. It is very slow in large areas, but if you want great solutions, this is a good choice.
• Best-first selects the node with the least (estimated) remaining cost to achieve the goal. In many cases, the estimate is the actual distance to the target (Euclidean, Manhattan, etc.), but it is not always possible to know.
• A * - Dijkstra + Best-first. These two heuristics cancel each other, so that in open areas A * moves quickly, but does not get stuck. A * is not perfect, but it is much faster than Dijkstra. You can weigh either a heuristic to make the algorithm more greedy or more optimal, and you can also add other cost functions, such as distances to health packs, covers, or enemy players.
• Custom heuristics usually come into play when your nodes contain a lot of data. Usually this means that you have moved from finding a path to a state search area, for example, predicting the next step that your opponent will take in chess. Resource management issues will use custom heuristics to prioritize each resource to determine the weight of a node.

[2]: Sometimes the target node is not one place. You might want to find any node that has a specific object, such as a health pack, a store, or an enemy player that is easy to kill. By checking the node using the goal() function, it becomes possible to identify several endpoints.

[3]: Candidate nodes should not be next to each other. You use the function f(node) = list(nodes) . When looking for a game to get gold or health for a player, you can create nodes for activities such as JUMP, ATTACK, REST, etc. In some cases, you will need to check the list of generated nodes before adding them.

[4]: Invalid nodes are usually only nodes in the _closed list that were previously found. However, they can be nodes that are too far away, nodes that collide with walls (very common), nodes that reduce your player’s 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 back off (which can create infinite loops).

[5]: You can implement an algorithm to stop when certain conditions are met. It is generally assumed that 1 node goal is found, but you can do a lot with that! You can stop searching for a path after a certain time, which is great for game engines, because you may need to pause frame rendering and prevent a delay. You can also stop searching if the node list becomes too large, which reduces memory consumption. You can even stop if you have a certain number of solutions.

This boolean condition / stop function allows you to interrupt the path search every time the pathfinder takes too long, starts resources, or enters an endless loop. In a single thread, this usually means that you no longer need a scanner. For game engines, clients of online games and graphic applications, I like to run a search scanner in the second thread and wake it up when I need it. If the crawler does not find the path fast enough, the dumb AI makes quick decisions until the return path completes.