查找两个图节点之间的所有路径 [英] Find all paths between two graph nodes
问题描述
我正在研究 Dijkstras 算法的实现,以检索路由网络上互连节点之间的最短路径.我有实施工作.当我将起始节点传递给算法时,它返回所有节点的所有最短路径.
I am working on an implemtation of Dijkstras Algorithm to retrieve the shortest path between interconnected nodes on a network of routes. I have the implentation working. It returns all the shortest paths to all the nodes when I pass the start node into the algorithm.
我的问题:如何检索从节点 A 到节点 G 的所有可能路径,甚至从节点 A 返回到节点 A 的所有可能路径
My Question: How does one go about retrieving all possible paths from Node A to say Node G or even all possible paths from Node A and back to Node A
推荐答案
寻找所有可能的路径是一个难题,因为简单路径的数量是指数级的.即使找到第 k 个最短路径 [或最长路径] 也是 NP-Hard.
Finding all possible paths is a hard problem, since there are exponential number of simple paths. Even finding the kth shortest path [or longest path] are NP-Hard.
找到从 s
到 t
的所有路径 [或所有路径达到特定长度的所有路径] 的一种可能解决方案是 BFS,不保留 visited
集,或者对于加权版本 - 您可能想要使用 统一成本搜索
One possible solution to find all paths [or all paths up to a certain length] from s
to t
is BFS, without keeping a visited
set, or for the weighted version - you might want to use uniform cost search
请注意,在每个具有循环的图中 [它不是 DAG]是 s
到 t
之间的无限路径.
Note that also in every graph which has cycles [it is not a DAG] there might be infinite number of paths between s
to t
.
这篇关于查找两个图节点之间的所有路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!