Нахождение всех путей между двумя вершинами с пределом веса в ориентированном графе

Не существует алгоритма, позволяющего эффективно запрашивать все непростые пути между парой вершин. Путей может быть экспоненциально много. Представьте себе граф со следующими ребрами: (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 и добавьте ее в очередь открытых меток. Во время каждой итерации алгоритма опрашивайте метку из открытой очереди, пока она не будет исчерпана. Для опрашиваемой метки L, связанной с узлом i и имеющей стоимость c, разверните метку: для каждого соседа j узла i создайте новую метку 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

Улучшение производительности вышеуказанной реализации, например добавив допустимую эвристику, я оставляю в качестве упражнения ОП.