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

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());

这种方法显然是次优的，因为对于更大的图形它会变得很慢。为了限制输出并使其更快，我在 AllDirectedPaths#getAllPaths 中提供了maxPathLength ，我将其设置为路径可以拥有的最大权重除以图中边缘的最小权重，因为在我的情况下，边缘权重是整数且始终大于1。

我考虑使用KShortestSimplePaths 和自定义的PathValidator，但它仅支持简单路径，即不允许循环。

如果有其他选择，在jgrapht中可用于解决查找所有路径而无需自己遍历图形，请告诉我。

- ouid

---

这个问题正在meta上讨论。 - Sinatr

我认为需要考虑的一件事是，无论你如何做，如果你真的想要获取所有路径的列表，那么它将是指数时间。考虑节点s_i、u_i和d_i。对于每个s_i，我们在E中有(s_i, u_i)和(s_i, d_i)，以及(u_(i), s_(i+1))和(d_(i), s_(i+1))。如果你画出这个图，应该很清楚地看到有指数多的路径，因此不可能有一个有效的算法。 - Hive7

@Hive7，我知道一个高效的算法是不可能的，获取所有路径的时间将呈指数级增长。在AllDirectedPaths的文档中，它实现了检索两个顶点之间所有路径列表的功能，并且说“如果考虑所有路径（即没有最大路径长度限制），由于输出可能非常巨大，因此速度可能会非常慢”，我意识到，由于允许非简单路径，因此输出会更大，速度会更慢。我正在寻找类似于AllDirectedPaths#getAllPaths(Graph, s, t, maxPathWeight)的jgrapht API。 - ouid

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

优化上述实现的性能（例如添加可接受的启发式算法），我留给原帖作者自行练习。

- Joris Kinable

---

感谢您的回答。我确实意识到，没有一种算法可以有效地查询两个顶点之间的所有非简单路径。我的问题不是关于这样的算法是否存在，而更多地涉及特定库（jgrapht）中（低效算法的）实现，该库已经提供了类似的功能AllDirectedPaths，它返回两个顶点之间的所有路径，可能受最大路径长度的限制。因此，我考虑的是允许按权重而不是长度进行限制的实现。 - ouid

@ouid，使用JGraphT现有的库无法完成您所要求的操作。我已经更新了我的答案，通过使用JGraphT作为支持图形库，在Java中添加了完整的算法实现。 - Joris Kinable