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

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.

我考虑过使用KShortestSimplePathscustom 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] 直到最终达到体重限制。如果这确实是您想要的，我建议实现一个简单的标记算法。标签对部分路径进行编码。标签保存对其前一个标签的引用、对与标签关联的节点的引用，以及等于由标签表示的部分路径的总成本的成本。通过为源节点 s 创建成本为 0 的标签来启动算法，并将其添加到开放标签队列中。在算法的每次迭代期间，从打开队列中轮询标签，直到队列耗尽。对于与节点 i 关联且具有成本 c 的轮询标签 L，扩展标签：对于节点 i 的每个邻居 j，创建一个指向标签 L 的新标签 L' 并将其成本设置为等于 c 加边权重 d_ij。如果新标签 L' 的成本超出可用预算，则丢弃该标签。否则，如果 j 是目标节点，我们找到了一条新路径，因此存储标签以便我们稍后可以恢复该路径。否则，将 L' 添加到打开标签队列中。下面可以找到该算法的简单实现。

笔记：

1. 上述标记算法仅在图相对较小、N 较低或边权重较高时才起作用，因为从 s 到 t 的可能路径数量增长得非常快。
2. 通过包含可允许的启发式来计算完成从给定节点到终端的路径所需的最少预算量，可以稍微改进上述算法的性能。这将允许您修剪一些标签。
3. 所有边的权重都必须大于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。