找到两个给定节点之间的路径?

Say I have nodes connected in the below fashion, how do I arrive at the number of paths that exist between given points, and path details?

假设我的节点以下面的方式连接，我如何到达在给定的点和路径细节之间存在的路径的数量?

1,2 //node 1 and 2 are connected
2,3
2,5
4,2
5,11
11,12
6,7
5,6
3,6
6,8
8,10
8,9

Find the paths from 1 to 7:

找到从1到7的路径:

Answer: 2 paths found and they are

答:找到两条路径，它们是。

1,2,3,6,7
1,2,5,6,7

implementation found here is nice I am going to use the same

这里的实现很好，我将使用相同的方法。

Here is the snippet from the above link in python

下面是python中上述链接的片段。

# a sample graph
graph = {'A': ['B', 'C','E'],
             'B': ['A','C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F','D'],
             'F': ['C']}

class MyQUEUE: # just an implementation of a queue

    def __init__(self):
        self.holder = []

    def enqueue(self,val):
        self.holder.append(val)

    def dequeue(self):
        val = None
        try:
            val = self.holder[0]
            if len(self.holder) == 1:
                self.holder = []
            else:
                self.holder = self.holder[1:]   
        except:
            pass

        return val  

    def IsEmpty(self):
        result = False
        if len(self.holder) == 0:
            result = True
        return result


path_queue = MyQUEUE() # now we make a queue


def BFS(graph,start,end,q):

    temp_path = [start]

    q.enqueue(temp_path)

    while q.IsEmpty() == False:
        tmp_path = q.dequeue()
        last_node = tmp_path[len(tmp_path)-1]
        print tmp_path
        if last_node == end:
            print "VALID_PATH : ",tmp_path
        for link_node in graph[last_node]:
            if link_node not in tmp_path:
                #new_path = []
                new_path = tmp_path + [link_node]
                q.enqueue(new_path)

BFS(graph,"A","D",path_queue)

-------------results-------------------
['A']
['A', 'B']
['A', 'C']
['A', 'E']
['A', 'B', 'C']
['A', 'B', 'D']
VALID_PATH :  ['A', 'B', 'D']
['A', 'C', 'D']
VALID_PATH :  ['A', 'C', 'D']
['A', 'E', 'F']
['A', 'E', 'D']
VALID_PATH :  ['A', 'E', 'D']
['A', 'B', 'C', 'D']
VALID_PATH :  ['A', 'B', 'C', 'D']
['A', 'E', 'F', 'C']
['A', 'E', 'F', 'C', 'D']
VALID_PATH :  ['A', 'E', 'F', 'C', 'D']

8 个解决方案

#1

Breadth-first search traverses a graph and in fact finds all paths from a starting node. Usually, BFS doesn't keep all paths, however. Instead, it updates a prededecessor function π to save the shortest path. You can easily modify the algorithm so that π(n) doesn't only store one predecessor but a list of possible predecessors.

广度优先搜索遍历一个图，实际上从一个起始节点找到所有路径。然而，通常情况下，BFS并不能保持所有的路径。相反，它更新一个预分解函数，以保存最短路径。你可以很容易地修改算法，这样一来，(n)不仅可以存储一个前任，还可以存储一个可能的前辈列表。

Then all possible paths are encoded in this function, and by traversing π recursively you get all possible path combinations.

然后所有可能的路径都被编码在这个函数中，通过递归地遍历，你会得到所有可能的路径组合。

One good pseudocode which uses this notation can be found in Introduction to Algorithms by Cormen et al. and has subsequently been used in many University scripts on the subject. A Google search for “BFS pseudocode predecessor π” uproots this hit on Stack Exchange.

一个好的伪代码使用这种表示法可以在Cormen等人的算法介绍中找到，并随后在许多大学的脚本中被使用。一个谷歌搜索“BFS伪代码的前身”将这一事件连根拔起。

#2

For those who are not PYTHON expert ,the same code in C++

对于那些不是PYTHON专家的人来说，c++中的代码是相同的。

//@Author :Ritesh Kumar Gupta
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<vector<int> >GRAPH(100);
inline void print_path(vector<int>path)
{
    cout<<"[ ";
    for(int i=0;i<path.size();++i)
    {
        cout<<path[i]<<" ";
    }
    cout<<"]"<<endl;
}
bool isadjacency_node_not_present_in_current_path(int node,vector<int>path)
{
    for(int i=0;i<path.size();++i)
    {
        if(path[i]==node)
        return false;
    }
    return true;
}
int findpaths(int source ,int target ,int totalnode,int totaledge )
{
    vector<int>path;
    path.push_back(source);
    queue<vector<int> >q;
    q.push(path);

    while(!q.empty())
    {
        path=q.front();
        q.pop();

        int last_nodeof_path=path[path.size()-1];
        if(last_nodeof_path==target)
        {
            cout<<"The Required path is:: ";
            print_path(path);
        }
        else
        {
            print_path(path);
        }

        for(int i=0;i<GRAPH[last_nodeof_path].size();++i)
        {
            if(isadjacency_node_not_present_in_current_path(GRAPH[last_nodeof_path][i],path))
            {

                vector<int>new_path(path.begin(),path.end());
                new_path.push_back(GRAPH[last_nodeof_path][i]);
                q.push(new_path);
            }
        }




    }
    return 1;
}
int main()
{
    //freopen("out.txt","w",stdout);
    int T,N,M,u,v,source,target;
    scanf("%d",&T);
    while(T--)
    {
        printf("Enter Total Nodes & Total Edges\n");
        scanf("%d%d",&N,&M);
        for(int i=1;i<=M;++i)
        {
            scanf("%d%d",&u,&v);
            GRAPH[u].push_back(v);
        }
        printf("(Source, target)\n");
        scanf("%d%d",&source,&target);
        findpaths(source,target,N,M);
    }
    //system("pause");
    return 0;
}

/*
Input::
1
6 11
1 2 
1 3
1 5
2 1
2 3
2 4
3 4
4 3
5 6
5 4
6 3
1 4

output:
[ 1 ]
[ 1 2 ]
[ 1 3 ]
[ 1 5 ]
[ 1 2 3 ]
The Required path is:: [ 1 2 4 ]
The Required path is:: [ 1 3 4 ]
[ 1 5 6 ]
The Required path is:: [ 1 5 4 ]
The Required path is:: [ 1 2 3 4 ]
[ 1 2 4 3 ]
[ 1 5 6 3 ]
[ 1 5 4 3 ]
The Required path is:: [ 1 5 6 3 4 ]


*/

#3

Dijkstra's algorithm applies more to weighted paths and it sounds like the poster was wanting to find all paths, not just the shortest.

Dijkstra算法更适用于加权路径，它听起来像是海报想要找到所有路径，而不仅仅是最短路径。

For this application, I'd build a graph (your application sounds like it wouldn't need to be directed) and use your favorite search method. It sounds like you want all paths, not just a guess at the shortest one, so use a simple recursive algorithm of your choice.

对于这个应用程序，我将构建一个图形(您的应用程序听起来不需要被引导)，并使用您最喜欢的搜索方法。这听起来像是你想要所有路径，而不仅仅是猜测最短的路径，所以使用一个简单的递归算法来选择。

The only problem with this is if the graph can be cyclic.

唯一的问题是，如果图形是循环的。

With the connections:

连接:

• 1, 2
• 1、2
• 1, 3
• 1、3
• 2, 3
• 2、3
• 2, 4
• 2、4

While looking for a path from 1->4, you could have a cycle of 1 -> 2 -> 3 -> 1.

在寻找从1到>4的路径时，可以有一个1-> 2 -> 3 -> 1的循环。

In that case, then I'd keep a stack as traversing the nodes. Here's a list with the steps for that graph and the resulting stack (sorry for the formatting - no table option):

在这种情况下，我将保留一个堆栈作为遍历节点。下面是该图和结果堆栈的步骤列表(抱歉格式-没有表格选项):

current node (possible next nodes minus where we came from) [stack]

当前节点(可能下一个节点减去我们来自的地方)[堆栈]

1. 1 (2, 3) [1]
2. 1(2、3)[1]
3. 2 (3, 4) [1, 2]
4. 2 (3,4)[1,2]
5. 3 (1) [1, 2, 3]
6. 3 (1)[1,2,3]
7. 1 (2, 3) [1, 2, 3, 1] //error - duplicate number on the stack - cycle detected
8. 1(2,3)[1,2,3,1]//错误-重复的数字在堆栈-周期检测。
9. 3 () [1, 2, 3] // back-stepped to node three and popped 1 off the stack. No more nodes to explore from here
10. 3()[1,2,3]//后退到节点3，从堆栈上弹出1。没有更多的节点可以从这里探索。
11. 2 (4) [1, 2] // back-stepped to node 2 and popped 1 off the stack.
12. 2(4)[1,2]//退到节点2，从堆栈上弹出1。
13. 4 () [1, 2, 4] // Target node found - record stack for a path. No more nodes to explore from here
14. 4()[1,2,4]//目标节点找到路径的记录堆栈。没有更多的节点可以从这里探索。
15. 2 () [1, 2] //back-stepped to node 2 and popped 4 off the stack. No more nodes to explore from here
16. 2()[1,2]//后退到节点2，从堆栈中弹出4。没有更多的节点可以从这里探索。
17. 1 (3) [1] //back-stepped to node 1 and popped 2 off the stack.
18. 1(3)[1]//后退到节点1，从堆栈中弹出2。
19. 3 (2) [1, 3]
20. 3(2)[1,3]
21. 2 (1, 4) [1, 3, 2]
22. 2 (1,4)[1,3,2]
23. 1 (2, 3) [1, 3, 2, 1] //error - duplicate number on the stack - cycle detected
24. 1(2,3)[1,3,2,1]//错误-重复检测到堆栈上的重复数字。
25. 2 (4) [1, 3, 2] //back-stepped to node 2 and popped 1 off the stack
26. 2(4)[1,3,2]//向后转到节点2，从堆栈上弹出1。
27. 4 () [1, 3, 2, 4] Target node found - record stack for a path. No more nodes to explore from here
28. 4()[1,3,2,4]目标节点发现-记录堆栈的路径。没有更多的节点可以从这里探索。
29. 2 () [1, 3, 2] //back-stepped to node 2 and popped 4 off the stack. No more nodes
30. 2()[1,3,2]//回退到节点2，从堆栈中弹出4。没有更多的节点
31. 3 () [1, 3] // back-stepped to node 3 and popped 2 off the stack. No more nodes
32. 3()[1,3]//后退到节点3，从堆栈中弹出2。没有更多的节点
33. 1 () [1] // back-stepped to node 1 and popped 3 off the stack. No more nodes
34. 1()[1]//返回到节点1，并从堆栈中弹出3。没有更多的节点
35. Done with 2 recorded paths of [1, 2, 4] and [1, 3, 2, 4]
36. 完成2条记录路径[1,2,4]和[1,3,2,4]

#4

The original code is a bit cumbersome and you might want to use the collections.deque instead if you want to use BFS to find if a path exists between 2 points on the graph. Here is a quick solution I hacked up:

原始代码有点麻烦，您可能想要使用collections.deque，如果您想使用BFS来查找图上两点之间是否存在路径的话。这里有一个快速解决方案:

Note: this method might continue infinitely if there exists no path between the two nodes. I haven't tested all cases, YMMV.

注意:如果两个节点之间没有路径，这个方法可能会持续无限。我还没有测试所有的案例，YMMV。

from collections import deque

# a sample graph
  graph = {'A': ['B', 'C','E'],
           'B': ['A','C', 'D'],
           'C': ['D'],
           'D': ['C'],
           'E': ['F','D'],
           'F': ['C']}

   def BFS(start, end):
    """ Method to determine if a pair of vertices are connected using BFS

    Args:
      start, end: vertices for the traversal.

    Returns:
      [start, v1, v2, ... end]
    """
    path = []
    q = deque()
    q.append(start)
    while len(q):
      tmp_vertex = q.popleft()
      if tmp_vertex not in path:
        path.append(tmp_vertex)

      if tmp_vertex == end:
        return path

      for vertex in graph[tmp_vertex]:
        if vertex not in path:
          q.append(vertex)

#5

In Prolog (specifically, SWI-Prolog)

在序言(特别是SWI-Prolog)

:- use_module(library(tabling)).

% path(+Graph,?Source,?Target,?Path)
:- table path/4.

path(_,N,N,[N]).
path(G,S,T,[S|Path]) :-
    dif(S,T),
    member(S-I, G), % directed graph
    path(G,I,T,Path).

test:

测试:

paths :- Graph =
    [ 1- 2  % node 1 and 2 are connected
    , 2- 3 
    , 2- 5 
    , 4- 2 
    , 5-11
    ,11-12
    , 6- 7 
    , 5- 6 
    , 3- 6 
    , 6- 8 
    , 8-10
    , 8- 9
    ],
    findall(Path, path(Graph,1,7,Path), Paths),
    maplist(writeln, Paths).

?- paths.
[1,2,3,6,7]
[1,2,5,6,7]
true.

#6

given the adjacency matrix:

考虑到邻接矩阵:

{0, 1, 3, 4, 0, 0}

{0,1,3,4,0,0}

{0, 0, 2, 1, 2, 0}

{0,0,2,1,2,0}

{0, 1, 0, 3, 0, 0}

{0,1,0,3,0,0}

{0, 1, 1, 0, 0, 1}

{0,1,1,0,0,1}

{0, 0, 0, 0, 0, 6}

{0 0 0 0 0 6}

{0, 1, 0, 1, 0, 0}

{0,1,0,1,0,0}

the following Wolfram Mathematica code solve the problem to find all the simple paths between two nodes of a graph. I used simple recursion, and two global var to keep track of cycles and to store the desired output. the code hasn't been optimized just for the sake of code clarity. the "print" should be helpful to clarify how it works.

下面的Wolfram Mathematica代码解决了在图的两个节点之间找到所有简单路径的问题。我使用简单的递归和两个全局var来跟踪周期并存储所需的输出。代码没有经过优化，只是为了代码的清晰性。“打印”应该有助于阐明它是如何工作的。

cycleQ[l_]:=If[Length[DeleteDuplicates[l]] == Length[l], False, True];
getNode[matrix_, node_]:=Complement[Range[Length[matrix]],Flatten[Position[matrix[[node]], 0]]];

builtTree[node_, matrix_]:=Block[{nodes, posAndNodes, root, pos},
    If[{node} != {} && node != endNode ,
        root = node;
        nodes = getNode[matrix, node];
        (*Print["root:",root,"---nodes:",nodes];*)

        AppendTo[lcycle, Flatten[{root, nodes}]];
        If[cycleQ[lcycle] == True,
            lcycle = Most[lcycle]; appendToTree[root, nodes];,
            Print["paths: ", tree, "\n", "root:", root, "---nodes:",nodes];
            appendToTree[root, nodes];

        ];
    ];

appendToTree[root_, nodes_] := Block[{pos, toAdd},
    pos = Flatten[Position[tree[[All, -1]], root]];
    For[i = 1, i <= Length[pos], i++,
        toAdd = Flatten[Thread[{tree[[pos[[i]]]], {#}}]] & /@ nodes;
        (* check cycles!*)            
        If[cycleQ[#] != True, AppendTo[tree, #]] & /@ toAdd;
    ];
    tree = Delete[tree, {#} & /@ pos];
    builtTree[#, matrix] & /@ Union[tree[[All, -1]]];
    ];
];

to call the code: initNode = 1; endNode = 6; lcycle = {}; tree = {{initNode}}; builtTree[initNode, matrix];

调用代码:initNode = 1;endNode = 6;lcycle = { };树= { { initNode } };builtTree[initNode,矩阵);

paths: {{1}} root:1---nodes:{2,3,4}

路径:{ { 1 } }根:1——节点:{ 2、3、4 }

paths: {{1,2},{1,3},{1,4}} root:2---nodes:{3,4,5}

道路:{ { 1,2 },{ 1,3 },{ 1,4 } }根:2——节点:{ 3、4、5 }

paths: {{1,3},{1,4},{1,2,3},{1,2,4},{1,2,5}} root:3---nodes:{2,4}

道路:{ { 1,3 },{ 1,4 },{ 1,2,3 },{ 1,2,4 },{ 1、2、5 } }根:3——节点:{ 2,4 }

paths: {{1,4},{1,2,4},{1,2,5},{1,3,4},{1,2,3,4},{1,3,2,4},{1,3,2,5}} root:4---nodes:{2,3,6}

道路:{ { 1,4 },{ 1,2,4 },{ 1、2、5 },{ 1,3,4 },{ 1,2,3,4 },{ 1、3、2、4 },{ 1、3、2、5 } }根:4——节点:{ 2、3、6 }

paths: {{1,2,5},{1,3,2,5},{1,4,6},{1,2,4,6},{1,3,4,6},{1,2,3,4,6},{1,3,2,4,6},{1,4,2,5},{1,3,4,2,5},{1,4,3,2,5}} root:5---nodes:{6}

道路:{ { 1、2、5 },{ 1、3、2、5 },{ 1,4,6 },{ 1,2,4,6 },{ 1、3、4、6 },{ 1、2、3、4、6 },{ 1、3、2、4、6 },{ 1、4、2、5 },{ 1、3、4、2、5 },{ 1、4、3、2、5 } }根:5——节点:{ 6 }

RESULTS:{{1, 4, 6}, {1, 2, 4, 6}, {1, 2, 5, 6}, {1, 3, 4, 6}, {1, 2, 3, 4, 6}, {1, 3, 2, 4, 6}, {1, 3, 2, 5, 6}, {1, 4, 2, 5, 6}, {1, 3, 4, 2, 5, 6}, {1, 4, 3, 2, 5, 6}}

结果:{ { 1,4,6 },{ 1,2,4,6 },{ 1、2、5、6 },{ 1、3、4、6 },{ 1、2、3、4、6 },{ 1、3、2、4、6 },{ 1、3、2、5、6 },{ 1、4、2、5、6 },{ 1、3、4、2、5、6 },{ 1、4、3、2、5、6 } }

...Unfortunately I cannot upload images to show the results in a better way :(

…不幸的是，我不能上传图片以更好的显示结果:

http://textanddatamining.blogspot.com

http://textanddatamining.blogspot.com

#7

If you want all the paths, use recursion.

如果您想要所有路径，请使用递归。

Using an adjacency list, preferably, create a function f() that attempts to fill in a current list of visited vertices. Like so:

使用邻接表，最好创建一个函数f()，它试图填充当前访问的顶点列表。像这样:

void allPaths(vector<int> previous, int current, int destination)
{
    previous.push_back(current);

    if (current == destination)
        //output all elements of previous, and return

    for (int i = 0; i < neighbors[current].size(); i++)
        allPaths(previous, neighbors[current][i], destination);
}

int main()
{
    //...input
    allPaths(vector<int>(), start, end);
}

Due to the fact that the vector is passed by value (and thus any changes made further down in the recursive procedure aren't permanent), all possible combinations are enumerated.

由于这个向量是通过值传递的(因此在递归过程中所做的任何更改都不是永久的)，所有可能的组合都被枚举了。

You can gain a bit of efficiency by passing the previous vector by reference (and thus not needing to copy the vector over and over again) but you'll have to make sure that things get popped_back() manually.

通过引用以前的vector，您可以获得一点效率(因此不需要重复地复制vector)，但是您必须确保您手动地得到popped_back()。

One more thing: if the graph has cycles, this won't work. (I assume in this case you'll want to find all simple paths, then) Before adding something into the previous vector, first check if it's already in there.

还有一件事:如果图形有循环，这将不起作用。(在本例中，我假定您将希望找到所有简单的路径)，然后在前一个向量中添加一些内容，首先检查它是否已经存在。

If you want all shortest paths, use Konrad's suggestion with this algorithm.

如果您想要所有最短路径，请使用Konrad的建议。

#8

What you're trying to do is essentially to find a path between two vertices in a (directed?) graph check out Dijkstra's algorithm if you need shortest path or write a simple recursive function if you need whatever paths exist.

你要做的是找到一个路径，在一个(有向的?)图中两个顶点之间的路径，如果你需要最短路径，或者写一个简单的递归函数，如果你需要任何路径，那么你就可以找到一条路径。