图中最大路径数的计数

Question

有一个图 - V, E = V^2,

现在，我已经编写了一个 DFS 算法，它访问图中的所有路径，但我无法找到它的时间复杂度，因为我不知道图中最大路径数的计数。请有人告诉我图中的最大路径数或这段代码的时间复杂度 -

unordered_map<int , int> minTime;
vector<vector<pair<int,int>>> adjList;
vector<int> visited;

   void dfs(int v, int currPathLength){

    visited[v] = true;
    
    if(currPathLength < minTime[v])
    {
        minTime[v] = currPathLength;
    }

    for(auto& x : adjList[v])
    {
        
        if(!visited[x.first])
        {
            currPathLength += x.second;
            dfs(x.first, currPathLength);
            currPathLength -= x.second;
            visited[x.first] = false;
        }
    }
}

Answer 1

要查找有向图中指定顶点对之间的所有路径，请应用 Yen 算法https://en.wikipedia.org/wiki/Yen%27s_algorithm

注意：这些是维基百科文章中的一些错误。这是 Yen 算法经过测试的实现的伪代码 https://github.com/JamesBremner/PathFinder/wiki/All-Paths#algorithm

这给出了一对顶点之间不同路径的数量。如果您确实想找到图中的所有路径，则需要多次运行它。

如果您的图是无向的，则必须通过为尚无后边的每条边添加后边将其转换为有向。