加权图算法
我有一个加权有向图，具有从同一节点的结尾开始的多个边。 前任。 从节点 A 到节点 B 的多条边。
获取到某个节点的所有路径以及这些路径的相关成本的最佳搜索算法是什么？
I have a weighted, directed graph with multiples edges starting from the ending at the same nodes.
Ex.
Multiple edges going from node A to node B.
What would be the best search algorithm to get all of the paths to a certain node and the associated costs of these paths?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
由于您想要所有路径，因此我将使用简单的广度优先搜索。但是，我还建议您将所有平行边折叠成具有权重列表的单个边。
一旦获得了所有不同的路径（即访问的节点都不同的所有路径），对于每条路径，您都可以计算出所有可能的替代并行路线。
因此，如果您有以下边：
第一步将其转换为：
该图上的广度优先搜索将产生 A 和 B 之间的以下路径：
因此，对于第二条路径，您将获得以下成本
：它本身并不比在原始图上进行 BFS 更快，但更简单的图更容易处理。
Since you want all the paths, I'd use a simple breadth-first search. However, I also suggest that you collapse all the parallel edges into a single edge that has a list of weights.
Once you get all the different paths (that is, all the paths in which the nodes visited are different), for each path you can calculate all the possible alternative parallel routes.
So if you've got the following edges:
The first step transforms it into:
The breadth-first search on this graph will yield the following paths between A and B:
So for the second path, you'll get the following costs:
This isn't going to be any faster in itself than just doing a BFS on the original graph, but a simpler graph is easier to handle.
如果必须输出每条路径的成本，没有什么比普通的 DFS（或 BFS）更好的了。由于问题是输出敏感的，并且您可能只有 O(E + V) 路径，因此就大 O 表示法而言，您无法完成任何更好的事情。
If you have to output the cost of each path, there is nothing better than a plain DFS (or BFS). Since the problem is output sensitive and you might just have O(E + V) paths, you cannot accomplish anything better in terms of big-O notation.
如前所述，您可以使用深度优先搜索等进行暴力/回溯。
不要指望为此找到任何捷径 - 如果您的图形足够密集，则可能有很多路径，甚至只是找出其中有多少是#P-完整的（即：难以处理）。
（如果您的问题不同 - 也许允许重复的节点，或者您只想找到最短路径或类似的东西，那么可能有易于处理的解决方案）
As already stated, you can do bruteforce/backtracking using Depth First Search, etc.
Don't expect to find any shortcuts for this - if your graph is dense enough there can be lots of paths and even just finding how many of them there are is #P-complete (ie.: untractable).
(If your problem is different - maybe repeated nodes are allowed or you only want to find the shortest path or something like that then there could be tractable solution)
您是否允许循环，即您有从 a->b bxx-->a 的定向链接/路径？在这种情况下，您最终将获得无限的路径。
do you allow the cycling, that is you have directed link/path from a->b b-x-x-->a? for which case you will end up with unlimited paths.