查找两个图节点之间的所有路径。

I am working on an implemtation of Dijkstras Algorithm to retrieve the shortest path between interconnected nodes on a network of routes. I have the implentation working. It returns all the shortest paths to all the nodes when I pass the start node into the algorithm.

我正在研究Dijkstras算法的实现，以检索路由网络中互联节点之间的最短路径。我有恳求的工作。当我将开始节点传入算法时，它将返回所有节点的最短路径。

My Question: How does one go about retrieving all possible paths from Node A to say Node G or even all possible paths from Node A and back to Node A

我的问题是:如何从节点A检索所有可能的路径，从节点A返回到节点A的所有可能路径。

10 个解决方案

#1

Finding all possible paths is a hard problem, since there are exponential number of simple paths. Even finding the kth shortest path [or longest path] are NP-Hard.

寻找所有可能的路径是一个困难的问题，因为有指数级的简单路径。即使找到第k条最短路径(或最长路径)也是np困难。

One possible solution to find all paths [or all paths up to a certain length] from s to t is BFS, without keeping a visited set, or for the weighted version - you might want to use uniform cost search

一个可能的解决方案是，从s到t，找到所有路径(或所有路径到一定长度的路径)是BFS，不保留访问集，或者是加权版本——您可能想要使用统一的成本搜索。

Note that also in every graph which has cycles [it is not a DAG] there might be infinite number of paths between s to t.

注意，在每个有周期的图中(它不是DAG)在s到t之间可能有无数条路径。

#2

I'm gonna give you a (somewhat small) version (although comprehensible, I think) of a scientific proof that you cannot do this under a feasible amount of time.

我将给你一个(有点小的)版本(尽管我认为是可以理解的)一个科学证据，证明你不能在可行的时间内做到这一点。

What I'm gonna prove is that the time complexity to enumerate all simple paths between two selected and distinct nodes (say, s and t) in an arbitrary graph G is not polynomial. Notice that, as we only care about the amount of paths between these nodes, the edge costs are unimportant.

我要证明的是，在任意的图G中，枚举两个选定的和不同的节点(例如，s和t)之间的所有简单路径的时间复杂度不是多项式。请注意，由于我们只关心这些节点之间的路径数量，所以边缘成本并不重要。

Sure that, if the graph has some well selected properties, this can be easy. I'm considering the general case though.

当然，如果图中有一些很好的选择的属性，这很容易。不过我考虑的是一般情况。

---

Suppose that we have a polynomial algorithm that lists all simple paths between s and t.

假设我们有一个多项式算法，它列出了s和t之间的所有简单路径。

If G is connected, the list is nonempty. If G is not and s and t are in different components, it's really easy to list all paths between them, because there are none! If they are in the same component, we can pretend that the whole graph consists only of that component. So let's assume G is indeed connected.

如果G是连通的，列表是非空的。如果G不是并且s和t在不同的组件中，那么很容易列出它们之间的所有路径，因为没有!如果它们在同一个组件中，我们可以假设整个图只包含该组件。假设G确实是连通的。

The number of listed paths must then be polynomial, otherwise the algorithm couldn't return me them all. If it enumerates all of them, it must give me the longest one, so it is in there. Having the list of paths, a simple procedure may be applied to point me which is this longest path.

列出的路径数目必须是多项式，否则算法不能全部返回。如果它列举了所有这些，它必须给我最长的一个，所以它在那里。有了路径列表，可以使用一个简单的过程来指出这条最长路径。

We can show (although I can't think of a cohesive way to say it) that this longest path has to traverse all vertices of G. Thus, we have just found a Hamiltonian Path with a polynomial procedure! But this is a well known NP-hard problem.

我们可以展示(尽管我不能用一种连贯的方式说)这条最长的路径必须遍历g的所有顶点，因此，我们刚刚找到了一个具有多项式过程的哈密顿路径!但这是一个众所周知的np困难问题。

We can then conclude that this polynomial algorithm we thought we had is very unlikely to exist, unless P = NP.

然后我们可以得出结论，我们认为这个多项式算法是不可能存在的，除非P = NP。

#3

I've implemented a version where it basically finds all possible paths from one node to the other, but it doesn't count any possible 'cycles' (the graph I'm using is cyclical). So basically, no one node will appear twice within the same path. And if the graph were acyclical, then I suppose you could say it seems to find all the possible paths between the two nodes. It seems to be working just fine, and for my graph size of ~150, it runs almost instantly on my machine, though I'm sure the running time must be something like exponential and so it'll start to get slow quickly as the graph gets bigger.

我已经实现了一个版本，它从一个节点到另一个节点找到所有可能的路径，但它不计算任何可能的“周期”(我使用的图表是循环的)。所以基本上，没有一个节点会在同一路径中出现两次。如果这个图是acyclical，那么我想你可以说它似乎找到了这两个节点之间的所有可能路径。它看起来运行得很好，在我的图形大小为~150的时候，它几乎可以在我的机器上运行，虽然我确定运行的时间一定是像指数一样的，所以当图形变大时，它会开始变慢。

Here is some Java code that demonstrates what I'd implemented. I'm sure there must be more efficient or elegant ways to do it as well.

下面是一些Java代码，它们演示了我的实现。我相信一定会有更高效或优雅的方法来做这件事。

Stack connectionPath = new Stack();
List<Stack> connectionPaths = new ArrayList<>();
// Push to connectionsPath the object that would be passed as the parameter 'node' into the method below
void findAllPaths(Object node, Object targetNode) {
    for (Object nextNode : nextNodes(node)) {
       if (nextNode.equals(targetNode)) {
           Stack temp = new Stack();
           for (Object node1 : connectionPath)
               temp.add(node1);
           connectionPaths.add(temp);
       } else if (!connectionPath.contains(nextNode)) {
           connectionPath.push(nextNode);
           findAllPaths(nextNode, targetNode);
           connectionPath.pop();
        }
    }
}

#4

Here is an algorithm finding and printing all paths from s to t using modification of DFS. Also dynamic programming can be used to find the count of all possible paths. The pseudo code will look like this:

这是一个算法发现和打印所有路径从s到t使用修改DFS。还可以使用动态编程来查找所有可能路径的计数。伪代码如下所示:

AllPaths(G(V,E),s,t)
 C[1...n]    //array of integers for storing path count from 's' to i
 TopologicallySort(G(V,E))  //here suppose 's' is at i0 and 't' is at i1 index

  for i<-0 to n
      if i<i0
          C[i]<-0  //there is no path from vertex ordered on the left from 's' after the topological sort
      if i==i0
         C[i]<-1
      for j<-0 to Adj(i)
          C[i]<- C[i]+C[j]

 return C[i1]

#5

You usually don't want to, because there is an exponential number of them in nontrivial graphs; if you really want to get all (simple) paths, or all (simple) cycles, you just find one (by walking the graph), then backtrack to another.

你通常不想，因为在非平凡图中有一个指数数;如果您真的想要获得所有(简单的)路径，或者所有(简单的)循环，您只要找到一个(通过图)，然后回溯到另一个。

#6

I think what you want is some form of the Ford–Fulkerson algorithm which is based on BFS. Its used to calculate the max flow of a network, by finding all augmenting paths between two nodes.

我认为你想要的是基于BFS的福特- fulkerson算法的某种形式。它用于计算网络的最大流量，通过在两个节点之间找到所有增加路径。

http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

#7

If you actually care about ordering your paths from shortest path to longest path then it would be far better to use a modified A* or Dijkstra Algorithm. With a slight modification the algorithm will return as many of the possible paths as you want in order of shortest path first. So if what you really want are all possible paths ordered from shortest to longest then this is the way to go.

如果你真的关心从最短路径到最长路径的路径排序，那么最好使用一个修改过的a *或Dijkstra算法。只要稍微修改一下，算法就会以最短路径的顺序返回尽可能多的路径。所以如果你真正想要的是所有可能的路径从最短到最长，那么这就是路径。

If you want an A* based implementation capable of returning all paths ordered from the shortest to the longest, the following will accomplish that. It has several advantages. First off it is efficient at sorting from shortest to longest. Also it computes each additional path only when needed, so if you stop early because you dont need every single path you save some processing time. It also reuses data for subsequent paths each time it calculates the next path so it is more efficient. Finally if you find some desired path you can abort early saving some computation time. Overall this should be the most efficient algorithm if you care about sorting by path length.

如果您想要一个基于*的实现，可以返回从最短到最长的所有路径，下面将实现这一点。它有几个优点。首先，它是高效的排序从最短到最长。此外，它只在需要时计算每个额外的路径，所以如果您不需要每条路径，就可以提前停止，这样可以节省一些处理时间。它还会在每次计算下一条路径时重新使用数据，以便更高效。最后，如果您找到了一些需要的路径，您可以提前终止一些计算时间。总的来说，这应该是最有效的算法如果你关心排序的路径长度。

import java.util.*;

public class AstarSearch {
    private final Map<Integer, Set<Neighbor>> adjacency;
    private final int destination;

    private final NavigableSet<Step> pending = new TreeSet<>();

    public AstarSearch(Map<Integer, Set<Neighbor>> adjacency, int source, int destination) {
        this.adjacency = adjacency;
        this.destination = destination;

        this.pending.add(new Step(source, null, 0));
    }

    public List<Integer> nextShortestPath() {
        Step current = this.pending.pollFirst();
        while( current != null) {
            if( current.getId() == this.destination )
                return current.generatePath();
            for (Neighbor neighbor : this.adjacency.get(current.id)) {
                if(!current.seen(neighbor.getId())) {
                    final Step nextStep = new Step(neighbor.getId(), current, current.cost + neighbor.cost + predictCost(neighbor.id, this.destination));
                    this.pending.add(nextStep);
                }
            }
            current = this.pending.pollFirst();
        }
        return null;
    }

    protected int predictCost(int source, int destination) {
        return 0; //Behaves identical to Dijkstra's algorithm, override to make it A*
    }

    private static class Step implements Comparable<Step> {
        final int id;
        final Step parent;
        final int cost;

        public Step(int id, Step parent, int cost) {
            this.id = id;
            this.parent = parent;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public Step getParent() {
            return parent;
        }

        public int getCost() {
            return cost;
        }

        public boolean seen(int node) {
            if(this.id == node)
                return true;
            else if(parent == null)
                return false;
            else
                return this.parent.seen(node);
        }

        public List<Integer> generatePath() {
            final List<Integer> path;
            if(this.parent != null)
                path = this.parent.generatePath();
            else
                path = new ArrayList<>();
            path.add(this.id);
            return path;
        }

        @Override
        public int compareTo(Step step) {
            if(step == null)
                return 1;
            if( this.cost != step.cost)
                return Integer.compare(this.cost, step.cost);
            if( this.id != step.id )
                return Integer.compare(this.id, step.id);
            if( this.parent != null )
                this.parent.compareTo(step.parent);
            if(step.parent == null)
                return 0;
            return -1;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Step step = (Step) o;
            return id == step.id &&
                cost == step.cost &&
                Objects.equals(parent, step.parent);
        }

        @Override
        public int hashCode() {
            return Objects.hash(id, parent, cost);
        }
    }

   /*******************************************************
   *   Everything below here just sets up your adjacency  *
   *   It will just be helpful for you to be able to test *
   *   It isnt part of the actual A* search algorithm     *
   ********************************************************/

    private static class Neighbor {
        final int id;
        final int cost;

        public Neighbor(int id, int cost) {
            this.id = id;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public int getCost() {
            return cost;
        }
    }

    public static void main(String[] args) {
        final Map<Integer, Set<Neighbor>> adjacency = createAdjacency();
        final AstarSearch search = new AstarSearch(adjacency, 1, 4);
        System.out.println("printing all paths from shortest to longest...");
        List<Integer> path = search.nextShortestPath();
        while(path != null) {
            System.out.println(path);
            path = search.nextShortestPath();
        }
    }

    private static Map<Integer, Set<Neighbor>> createAdjacency() {
        final Map<Integer, Set<Neighbor>> adjacency = new HashMap<>();

        //This sets up the adjacencies. In this case all adjacencies have a cost of 1, but they dont need to.
        addAdjacency(adjacency, 1,2,1,5,1);         //{1 | 2,5}
        addAdjacency(adjacency, 2,1,1,3,1,4,1,5,1); //{2 | 1,3,4,5}
        addAdjacency(adjacency, 3,2,1,5,1);         //{3 | 2,5}
        addAdjacency(adjacency, 4,2,1);             //{4 | 2}
        addAdjacency(adjacency, 5,1,1,2,1,3,1);     //{5 | 1,2,3}

        return Collections.unmodifiableMap(adjacency);
    }

    private static void addAdjacency(Map<Integer, Set<Neighbor>> adjacency, int source, Integer... dests) {
        if( dests.length % 2 != 0)
            throw new IllegalArgumentException("dests must have an equal number of arguments, each pair is the id and cost for that traversal");

        final Set<Neighbor> destinations = new HashSet<>();
        for(int i = 0; i < dests.length; i+=2)
            destinations.add(new Neighbor(dests[i], dests[i+1]));
        adjacency.put(source, Collections.unmodifiableSet(destinations));
    }
}

The output from the above code is the following:

以上代码的输出如下:

[1, 2, 4]
[1, 5, 2, 4]
[1, 5, 3, 2, 4]

Notice that each time you call nextShortestPath() it generates the next shortest path for you on demand. It only calculates the extra steps needed and doesnt traverse any old paths twice. Moreover if you decide you dont need all the paths and end execution early you've saved yourself considerable computation time. You only compute up to the number of paths you need and no more.

请注意，每次调用nextShortestPath()时，它都会根据需要生成下一条最短路径。它只计算所需的额外步骤，并且不会两次遍历任何旧路径。此外，如果您决定不需要所有的路径和结束执行，那么您就节省了大量的计算时间。你只计算你需要的路径的数量。

Finally it should be noted that the A* and Dijkstra algorithms do have some minor limitations, though I dont think it would effect you. Namely it will not work right on a graph that has negative weights.

最后需要指出的是，A*和Dijkstra算法确实有一些小的限制，不过我不认为这会影响到你。也就是说，它不会在有负权值的图上工作。

Here is a link to JDoodle where you can run the code yourself in the browser and see it working. You can also change around the graph to show it works on other graphs as well: http://jdoodle.com/a/ukx

这里有一个链接到JDoodle，您可以在浏览器中运行代码并看到它的工作。您还可以在图上进行更改，以显示它在其他图上的工作:http://jdoodle.com/a/ukx。

#8

I suppose you want to find 'simple' paths (a path is simple if no node appears in it more than once, except maybe the 1st and the last one).

我假设您希望找到“简单”路径(如果没有节点出现不止一次，那么路径很简单，除了可能是第一个节点和最后一个节点)。

Since the problem is NP-hard, you might want to do a variant of depth-first search.

由于问题是np困难的，您可能想要做一个深度优先搜索的变体。

Basically, generate all possible paths from A and check whether they end up in G.

基本上，从A生成所有可能的路径，并检查它们是否以G结束。

#9

There's a nice article which may answer your question /only it prints the paths instead of collecting them/. Please note that you can experiment with the C++/Python samples in the online IDE.

有一篇很好的文章可以回答你的问题/只是它打印了路径而不是收集它们/。请注意，您可以在在线IDE中试用c++ /Python示例。

http://www.geeksforgeeks.org/find-paths-given-source-destination/

http://www.geeksforgeeks.org/find-paths-given-source-destination/

#10

find_paths[s, t, d, k]

This question is now a bit old... but I'll throw my hat into the ring.

这个问题现在有点过时了……但我要把我的帽子扔进戒指。

I personally find an algorithm of the form find_paths[s, t, d, k] useful, where:

我个人找到了一种算法，它是find_paths[s, t, d, k]的算法，其中:

• s is the starting node
• s是起始节点。
• t is the target node
• t是目标节点。
• d is the maximum depth to search
• d是搜索的最大深度。
• k is the number of paths to find
• k是找到的路径数。

Using your programming language's form of infinity for d and k will give you all paths§.

使用编程语言的形式的无穷d和k§将给你所有的路径。

§ obviously if you are using a directed graph and you want all undirected paths between s and t you will have to run this both ways:

§显然如果你是你想要使用一个有向图和无向的路全s和t之间你要运行这两方面:

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]

---

Helper Function

I personally like recursion, although it can difficult some times, anyway first lets define our helper function:

我个人喜欢递归，虽然有时会很困难，但首先我们要定义我们的助手函数:

def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
  current_path.append(current)

  if current_depth > max_depth:
    return

  if current == goal:
    if len(paths_found) <= number_of_paths_to_find:
      paths_found.append(copy(current_path))

    current_path.pop()
    return

  else:
    for successor in graph[current]:
    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)

  current_path.pop()

Main Function

With that out of the way, the core function is trivial:

有了这些，核心功能是微不足道的:

def find_paths[s, t, d, k]:
  paths_found = [] # PASSING THIS BY REFERENCE  
  find_paths_recursion(s, t, 0, d, k, [], paths_found)

---

First, lets notice a few thing:

首先，让我们注意一些事情:

• the above pseudo-code is a mash-up of languages - but most strongly resembling python (since I was just coding in it). A strict copy-paste will not work.
• 上面的伪代码是一种语言的混搭——但最像python(因为我只是在其中编写代码)。一个严格的复制粘贴不会起作用。
• [] is an uninitialized list, replace this with the equivalent for your programming language of choice
• []是一个未初始化的列表，将其替换为与您的编程语言相同的选项。
• paths_found is passed by reference. It is clear that the recursion function doesn't return anything. Handle this appropriately.
• paths_found通过引用传递。很明显，递归函数没有返回任何东西。适当地处理这个问题。
• here graph is assuming some form of hashed structure. There are a plethora of ways to implement a graph. Either way, graph[vertex] gets you a list of adjacent vertices in a directed graph - adjust accordingly.
• 这里的图是假设某种形式的散列结构。有很多方法可以实现一个图形。无论哪种方式，图[顶点]都得到了一个有向图中相邻顶点的列表——相应地进行调整。
• this assumes you have pre-processed to remove "buckles" (self-loops), cycles and multi-edges
• 这假设您已经预先处理了删除“buckles”(自循环)、循环和多边。