相关疑难解决方法(0)

我正致力于实现Dijkstras算法,以检索路由网络上互连节点之间的最短路径.我有实施工作.当我将起始节点传递给算法时,它返回所有节点的所有最短路径.

我的问题:如何检索从节点A到节点G的所有可能路径,甚至从节点A返回到节点A的所有可能路径

请考虑以下图表:

我正在尝试找到一种方法来枚举从源节点到目标节点的所有可能路径.例如,从A到E,我们有以下可能的路径:

A B C D E
A B C E
A C D E
A C E

请注意,对于ACDE,实际上有2条路径,因为其中一条路径使用边缘F3而另一条路径使用边缘F5.此外,由于A和C之间存在循环,因此最终可能会有无限数量的路径,但出于此目的,我只对从源到目标的路径上没有重复节点的路径感兴趣.

我写了一个深度优先搜索(DFS)算法,但问题是当你在2个节点之间有多条边(比如上面的边缘F3和F5)时,我不知道如何处理它.我的算法只带回路径A C D E和A C E,而不是其他的路径.在这种情况下A B C E,我理解原因,因为它从A开始然后转到C并构建这些路径,但是当DFS返回到节点B时,它然后尝试转到C,但是C已经被访问过,所以它停了

无论如何,我只是想知道是否有办法做到这一点,或者这可能是NP完全的.

如果你想看我的DFS,代码在下面(抱歉宏观滥用,我在比赛编程中使用这些,所以这是一个习惯).

#include <algorithm>
#include <numeric>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <cmath>
#include <complex>
#include <stack>
#include "time.h"
using namespace std;
#define SZ(x) (int)x.size()
#define FOR(i,x,y) …

我正在尝试开发一种算法来识别图中两个节点之间的所有可能路径,如下例所示:

.

实际上,我只需要知道哪些节点出现在所有现有路径中.

在网上只有关于DFS,A*或dijkstra的参考,但我认为它们在这种情况下不起作用.

有谁知道如何解决它？