找到两个图节点之间的所有路径
Pau*_*aul 60 algorithm graph-theory
我正致力于实现Dijkstras算法,以检索路由网络上互连节点之间的最短路径.我有实施工作.当我将起始节点传递给算法时,它返回所有节点的所有最短路径.
我的问题:如何检索从节点A到节点G的所有可能路径,甚至从节点A返回到节点A的所有可能路径
ami*_*mit 50
找到所有可能的路径是一个难题,因为存在指数的简单路径.即使找到第k个最短路径[或最长路径]也是NP-Hard.
一个可能的解决方案,从找到的所有路径[或所有路径达到一定长度] s来t为BFS,没有保持visited一套,或加权版本-你可能想使用统一的搜索成本
注意,同样在具有周期每图表[它不是一个DAG ]可能存在的路径之间无限多s到t.
- @VShreyas这是一个古老的线程,答案明确地说"所有路径达到一定长度",这可以通过没有访问集的BFS完成.如果您想要在两个节点之间使用所有*simple*路径,则可以使用带有"本地"访问集的DFS(在访问跟踪时删除访问集中的节点). (2认同)
ara*_*una 10
我会给你一个(有点小)的版本(尽管可以理解,但我认为)是一个科学的证明,你不能在可行的时间内做到这一点.
我该怎么证明的是,时间复杂度来列举两个选定和不同的节点(比如,之间的所有简单路径s,并t在任意图)G是不是多项式.请注意,由于我们只关心这些节点之间的路径数量,因此边缘成本并不重要.
当然,如果图表具有一些选择良好的属性,这可能很容易.我考虑的是一般情况.
假设我们有一个多项式算法,列出s和之间的所有简单路径t.
如果G已连接,则列表为非空.如果G不是和s并且t在不同的组件中,列出它们之间的所有路径真的很容易,因为没有!如果它们在同一个组件中,我们可以假装整个图形仅包含该组件.所以我们假设G确实是连通的.
所列出的路径数必须是多项式的,否则算法不能全部返回.如果它列举了所有这些,它必须给我最长的一个,所以它就在那里.拥有路径列表,可以应用一个简单的过程指向我这是最长的路径.
我们可以证明(尽管我不能想出一种有说服力的方式来表达它),这条最长的路径必须遍历所有的顶点G.因此,我们刚刚找到了一个带有多项式过程的哈密顿路径!但这是一个众所周知的NP难题.
然后我们可以得出结论,我们认为我们所拥有的这种多项式算法不太可能存在,除非P = NP.
Ome*_*san 10
我已经实现了一个版本,它基本上找到了从一个节点到另一个节点的所有可能路径,但它没有计算任何可能的"周期"(我正在使用的图形是循环的).所以基本上,没有一个节点会在同一路径中出现两次.如果图是非周期性的,那么我想你可以说它似乎找到了两个节点之间的所有可能路径.它似乎工作得很好,并且对于我的图形大小~150,它几乎立即在我的机器上运行,虽然我确定运行时间必须是指数的,所以它会开始变得很慢,因为图变大了.
这是一些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();
}
}
}
- 我没有，不，但我认为理论上，任何递归程序都可以转换为非递归程序，我认为通过使用类似堆栈对象的东西，重点是模拟递归程序实际在做什么我相信使用程序的堆栈空间。你可以查一下递归程序转非递归的原理。 (2认同)
以下函数（修改后的BFS，具有两个节点之间的递归路径查找函数）将完成非循环图的工作：
from collections import defaultdict
# modified BFS
def find_all_parents(G, s):
Q = [s]
parents = defaultdict(set)
while len(Q) != 0:
v = Q[0]
Q.pop(0)
for w in G.get(v, []):
parents[w].add(v)
Q.append(w)
return parents
# recursive path-finding function (assumes that there exists a path in G from a to b)
def find_all_paths(parents, a, b):
return [a] if a == b else [y + b for x in list(parents[b]) for y in find_all_paths(parents, a, x)]
例如，下面的图（DAG）G由下式给出：
G = {'A':['B','C'], 'B':['D'], 'C':['D', 'F'], 'D':['E', 'F'], 'E':['F']}
如果我们想找到节点和之间的所有路径（使用上面定义的函数作为），它将返回以下路径：'A''F'find_all_paths(find_all_parents(G, 'A'), 'A', 'F')
这是一个使用 DFS 修改来查找并打印从 s 到 t 的所有路径的算法。动态规划也可用于查找所有可能路径的计数。伪代码如下所示：
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]
如果您确实关心从最短路径到最长路径对路径进行排序，那么使用修改后的 A* 或 Dijkstra 算法会更好。通过稍加修改，该算法将按照最短路径优先的顺序返回尽可能多的可能路径。因此，如果您真正想要的是从最短到最长排序的所有可能路径，那么这就是要走的路。
如果您想要一个基于 A* 的实现能够返回从最短到最长排序的所有路径，则以下内容将实现这一点。它有几个优点。首先，它能够有效地从最短到最长进行排序。此外，它仅在需要时才计算每个附加路径，因此，如果您因为不需要每个路径而提前停止，则可以节省一些处理时间。每次计算下一条路径时，它还会重用后续路径的数据，因此效率更高。最后，如果您找到一些所需的路径，您可以提前中止，从而节省一些计算时间。总的来说，如果您关心按路径长度排序，这应该是最有效的算法。
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));
}
}
上述代码的输出如下：
[1, 2, 4]
[1, 5, 2, 4]
[1, 5, 3, 2, 4]
请注意，每次您调用时，nextShortestPath()它都会根据需要为您生成下一条最短路径。它只计算所需的额外步骤，并且不会两次遍历任何旧路径。此外，如果您决定不需要所有路径并提前结束执行，您就可以节省大量的计算时间。您只需计算所需的路径数量，不再计算更多。
最后应该指出的是，A* 和 Dijkstra 算法确实有一些小的限制，尽管我认为这不会影响您。也就是说，它不能在具有负权重的图表上正常工作。
这是 JDoodle 的链接，您可以在浏览器中自己运行代码并查看其工作情况。您还可以更改图表以显示它也适用于其他图表：http ://jdoodle.com/a/ukx