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

Question

假设我以下面的方式连接节点,我如何得出给定点之间存在的路径数量和路径详细信息？

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

找到1到7的路径:

答案:找到2条路径,它们是

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

在这里找到的实现很好,我将使用相同的

这是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']

Answer 1

广度优先搜索遍历图形,实际上从起始节点查找所有路径.但是,通常,BFS不会保留所有路径.相反,它更新前驱函数π以保存最短路径.您可以轻松修改算法,?(n)这样不仅可以存储一个前任,还可以存储可能的前任列表.

然后在此函数中编码所有可能的路径,并通过递归遍历π,获得所有可能的路径组合.

使用这种表示法的一个好的伪代码可以在Cormen 等人的Introduction to Algorithms中找到.并随后在许多大学的剧本中使用过这个主题.谷歌搜索"BFS伪代码前身π" 在Stack Exchange上取消了这一打击.

Answer 2

对于那些不是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 ]


*/

Answer 3

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

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

唯一的问题是图形是否可以是循环的.

通过连接:

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

在寻找1-> 4的路径时,您可以使用1 - > 2 - > 3 - > 1的循环.

在那种情况下,然后我将堆栈作为遍历节点.这是一个列表,其中包含该图表的步骤和生成的堆栈(抱歉格式化 - 没有表格选项):

当前节点(可能的下一个节点减去我们来自哪里)[stack]

1. 1(2,3)[1]
2. 2(3,4)[1,2]
3. 3(1)[1,2,3]
4. 1(2,3)[1,2,3,1] //错误 - 堆栈上的重复数字 - 检测到循环
5. 3()[1,2,3] //后退到节点3并从堆栈中弹出1.没有更多的节点可以从这里探索
6. 2(4)[1,2] //后退到节点2并从堆栈中弹出1.
7. 4()[1,2,4] //找到目标节点 - 记录路径的堆栈.没有更多的节点可以从这里探索
8. 2()[1,2] //后退到节点2并从堆栈中弹出4.没有更多的节点可以从这里探索
9. 1(3)[1] //后退到节点1并从堆栈中弹出2.
10. 3(2)[1,3]
11. 2(1,4)[1,3,2]
12. 1(2,3)[1,3,2,1] //错误 - 堆栈上的重复数字 - 检测到循环
13. 2(4)[1,3,2] //后退到节点2并从堆栈弹出1
14. 4()[1,3,2,4]找到目标节点 - 记录路径的堆栈.没有更多的节点可以从这里探索
15. 2()[1,3,2] //后退到节点2并从堆栈中弹出4.没有更多的节点
16. 3()[1,3] //后退到节点3并从堆栈中弹出2.没有更多的节点
17. 1()[1] //后退到节点1并从堆栈中弹出3.没有更多的节点
18. 完成了[1,2,4]和[1,3,2,4]的2条记录路径