在有向图中查找具有权重限制的两个顶点之间的所有路径

Question

我试图在一个可能有环但没有自环的有向加权图中找到权重小于 N 的两个顶点之间的所有路径。到目前为止，我只能通过使用 AllDirectedPaths 来完成，然后过滤掉权重大于 N:

的路径

SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> g = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
AllDirectedPaths<String, DefaultWeightedEdge> allPaths = new AllDirectedPaths<>(g);
int maxWeight = 30;
List<GraphPath<String, DefaultWeightedEdge>> pathsLimitedByWeight = allPaths.getAllPaths(startVertex, endVertex, false, maxWeight / minGraphLatency)
    .filter(graphPath -> graphPath.getWeight() < maxWeight)
    .collect(Collectors.toList());

这种方法显然不是最优的，因为对于较大的图它很慢。为了限制输出并使其更快，我将 maxPathLength 提供给 AllDirectedPaths#getAllPaths，我将其设置为路径可以除以图中边的最小权重的最大权重，因为在我的例子中边权重是一个整数，并且总是大于 1。

我考虑过使用 KShortestSimplePaths with a custom PathValidator，但它仅支持简单路径，即不允许循环。

我在 jgrapht 中还有什么其他选项（如果有的话）可用于解决查找所有路径而无需自己遍历图形的问题。

Answer 1

没有一种算法可以让您高效地查询一对顶点之间的所有非简单路径。路径可以呈指数级增长。想象一个具有以下边的图：(s,u),(u,v),(v,u),(u,t)，其中所有边的长度均为 1。现在找到从 s 到 t 的所有非简单路径，重量限制为N。您将获得以下路径：

s,u,t
s,u,v,u,t
s,u,v,u,v,u,t
s,u,v,u,v,u,v,u,t
.....

您可以继续骑行 [u,v,u]，直到您最终达到体重限制。如果这真的是你想要的，我会建议实施一个简单的标签算法。标签编码部分路径。标签保留对其前一个标签的引用，对标签关联的节点的引用，以及等于标签表示的部分路径的总成本的成本。通过为成本为 0 的源节点 s 创建标签来启动算法，并将其添加到开放标签队列中。在算法的每次迭代中，从打开的队列中轮询一个标签，直到队列用完。对于与节点 i 关联且成本为 c 的轮询标签 L，扩展标签：对于节点 i 的每个邻居 j，创建一个新标签 L' 指向标签 L，并将其成本设置为 c 加上边权重 d_ij。如果新标签 L' 的成本超过可用预算，则丢弃该标签。否则，如果 j 是目标节点，我们找到了一条新路径，所以存储标签以便我们以后可以恢复路径。否则，将 L' 添加到开放标签队列中。可以在下面找到该算法的简单实现。

备注：

上述标记算法仅在图相对较小、N 较低或边权重较高时才有效，因为从 s 到 t 的可能路径数量会增长得非常快。
上述算法的性能可以通过包括一个允许的启发式来计算完成从给定节点到终端的路径所需的最少预算量来略微提高。这将允许您修剪一些标签。
要求所有边的权重都大于0。

import org.jgrapht.*;
import org.jgrapht.graph.*;

import java.util.*;

public class NonSimplePaths<V,E> {

    public List<GraphPath<V, E>> computeNoneSimplePaths(Graph<V,E> graph, V source, V target, double budget){
        GraphTests.requireDirected(graph); //Require input graph to be directed
        if(source.equals(target))
            return Collections.emptyList();

        Label start = new Label(null, source, 0);
        Queue<Label> openQueue = new LinkedList<>(); //List of open labels
        List<Label> targetLabels = new LinkedList<>(); //Labels associated with target node
        openQueue.add(start);

        while(!openQueue.isEmpty()){
            Label openLabel = openQueue.poll();
            for(E e : graph.outgoingEdgesOf(openLabel.node)){
                double weight = graph.getEdgeWeight(e);
                V neighbor = Graphs.getOppositeVertex(graph, e, openLabel.node);

                //Check whether extension is possible
                if(openLabel.cost + weight <= budget){
                    Label label = new Label(openLabel, neighbor, openLabel.cost + weight); //Create new label
                    if(neighbor.equals(target)) //Found a new path from source to target
                        targetLabels.add(label);
                    else //Must continue extending the path until a complete path is found
                        openQueue.add(label);
                }
            }
        }

        //Every label in the targetLabels list corresponds to a unique path. Recreate paths by backtracking labels
        List<GraphPath<V,E>> paths = new ArrayList<>(targetLabels.size());
        for(Label label : targetLabels){ //Iterate over every path
            List<V> path = new LinkedList<>();
            double pathWeight = label.cost;
            do{
                path.add(label.node);
                label=label.pred;
            }while(label != null);
            Collections.reverse(path); //By backtracking the labels, we recoved the path in reverse order
            paths.add(new GraphWalk<>(graph, path, pathWeight));
        }

       return paths;
   }

    private final class Label{
        private final Label pred;
        private final V node;
        private final double cost;

        private Label(Label pred, V node, double cost) {
            this.pred = pred;
            this.node = node;
            this.cost = cost;
        }
    }

    public static void main(String[] args){
        Graph<String,DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
        Graphs.addAllVertices(graph, Arrays.asList("s","u","v","t"));
        graph.addEdge("s","u");
        graph.addEdge("u","t");
        graph.addEdge("u","v");
        graph.addEdge("v","u");
        graph.edgeSet().forEach(e -> graph.setEdgeWeight(e,1.0)); //Set weight of all edges to 1

        NonSimplePaths<String,DefaultWeightedEdge> nonSimplePaths = new NonSimplePaths<>();
        List<GraphPath<String,DefaultWeightedEdge>> paths = nonSimplePaths.computeNoneSimplePaths(graph, "s", "t", 10);
        for(GraphPath<String,DefaultWeightedEdge> path : paths)
            System.out.println(path+" cost: "+path.getWeight());
    }
}

以上示例代码的输出：

[s, u, t] cost: 2.0
[s, u, v, u, t] cost: 4.0
[s, u, v, u, v, u, t] cost: 6.0
[s, u, v, u, v, u, v, u, t] cost: 8.0
[s, u, v, u, v, u, v, u, v, u, t] cost: 10.0

改进上述实现的性能，例如通过添加可接受的启发式方法，我将作为练习留给 OP。

在有向图中查找具有权重限制的两个顶点之间的所有路径

Finding all the paths between two vertices with weight limit in a directed graph

java

graph-theory

jgrapht