algorithm - Finding Path in graph( specific Length)

Question

we are looking for an algorithm, that can find a path in a undirected weighted graph (from 's' to 't' for instance), that the total weights of all it's edges is a fixed number ('m' for instance) ideas.. anyone?

Answer 1

使用诸如 DFS 和回溯之类的东西。如果你超过了体重 m 并且你没有达到你的目标，你就回溯。我不确定你是否允许在两个节点之间来回切换，但如果你这样做了，你就不能在适当的位置构建一棵树，而必须构建一个堆栈。

我有一种直觉，首先搜索最短路径然后让它变长会是一种更快的方法，但同样的感觉告诉我，它可能是错误的，就像贪婪算法对旅行推销员来说是错误的一样。