algorithm - 枚举加权图中从A到B的所有路径，其中路径长度在C1和C2之间

Question

给定一个加权图中的两点a和b，找出从a到b的所有路径，其中路径的长度在c1和c2之间。
理想情况下，每个顶点只应访问一次，尽管这不是一个硬性要求。我想我可以使用一个启发式的方法来对算法的结果进行排序，以剔除“愚蠢”的路径（例如，一条路径只是一遍又一遍地访问相同的两个节点）
我可以想到简单的蛮力算法，但有没有更复杂的算法，使这更有效？我可以想象，随着图表的增长，这可能会变得昂贵。
在我正在开发的应用程序中，A和B实际上是相同的点（即路径必须返回到起点），如果这有什么不同的话。
请注意，这是一个工程问题，而不是计算机科学问题，所以我可以使用快速但不一定100%准确的算法。也就是说，如果它返回大多数可能的路径，或者如果返回的大多数路径都在给定的长度范围内，则可以。
[更新]
这就是我目前所拥有的我在一个小图上做了这个工作（30个节点有大约100条边）。所需时间<100ms
我用的是有向图。
我先深入搜索所有可能的路径。
在每个新节点
对于每个离开节点的边
如果已包含此边的路径已包含此边，则拒绝该边（换句话说，切勿沿同一方向下两次同一边）
拒绝边缘，如果它导致回到我们刚刚来自的节点（换言之，不要双重返回）这消除了许多“愚蠢”的路径）
拒绝边缘（如果从边缘的末端节点到目标节点B+的距离最小到距离为止）＞最大路径长度（C2）
如果边缘的结束节点是我们的目标节点B：
如果路径符合长度条件，请将其添加到适当路径列表中。
否则拒绝边缘（换句话说，我们只访问路径末端的目标节点b）。它不会是路径上的中间点）
否则，将边添加到我们的路径并递归到它的目标节点
我使用Dijkstra来预计算所有节点到目标节点的最小距离。

Answer 1

我编写了一些java代码来测试我建议的DFS方法：代码不检查范围内的路径，而是打印所有路径修改代码使其仅保持在范围内应该很简单我也做了一些简单的测试它似乎给出了10个顶点和50条边左右的正确结果，尽管我没有时间进行任何彻底的测试。我还运行了100个顶点和1000条边它不会耗尽内存并不断打印新路径，直到我杀死它，其中有很多这对于随机生成的稠密图来说并不奇怪，但对于现实世界的图来说可能并不奇怪，例如顶点度数遵循幂律（特别是在权重范围较窄的情况下）此外，如果您只是对路径长度在一个范围内的分布感兴趣，则可以在生成某个数字后停止。
程序输出如下：
a）随机生成图的邻接表。
b）迄今为止找到的所有路径的集合。

public class AllPaths {

    int numOfVertices;
    int[] status;
    AllPaths(int numOfVertices){
        this.numOfVertices = numOfVertices;
        status = new int[numOfVertices+1];
    }

    HashMap<Integer,ArrayList<Integer>>adjList = new HashMap<Integer,ArrayList<Integer>>(); 
    class FoundSubpath{
          int pathWeight=0;
          int[] vertices;

        }


    // For each vertex, a a list of all subpaths of length less than UB found.
    HashMap<Integer,ArrayList<FoundSubpath>>allSubpathsFromGivenVertex = new HashMap<Integer,ArrayList<FoundSubpath>>();

    public void printInputGraph(){

        System.out.println("Random Graph Adjacency List:");

        for(int i=1;i<=numOfVertices;i++){
            ArrayList<Integer>toVtcs = adjList.get(new Integer(i));
            System.out.print(i+ " ");
            if(toVtcs==null){
                continue;
            }
            for(int j=0;j<toVtcs.size();j++){
                System.out.print(toVtcs.get(j)+ " ");
            }
            System.out.println(" ");
        }

    }

    public void randomlyGenerateGraph(int numOfTrials){

        Random rnd = new Random();

        for(int i=1;i < numOfTrials;i++){
            Integer fromVtx = new Integer(rnd.nextInt(numOfVertices)+1);
            Integer toVtx = new Integer(rnd.nextInt(numOfVertices)+1);
            if(fromVtx.equals(toVtx)){
                continue;
            }
            ArrayList<Integer>toVtcs = adjList.get(fromVtx);
            boolean alreadyAdded = false;
            if(toVtcs==null){
                toVtcs = new ArrayList<Integer>();
            }else{
                for(int j=0;j<toVtcs.size();j++){
                    if(toVtcs.get(j).equals(toVtx)){
                        alreadyAdded = true;
                        break;
                    }
                }
            }
            if(!alreadyAdded){
            toVtcs.add(toVtx);
            adjList.put(fromVtx, toVtcs);
            }
        }

    }

    public void addAllViableSubpathsToMap(ArrayList<Integer>VerticesTillNowInPath){
        FoundSubpath foundSpObj;
        ArrayList<FoundSubpath>foundPathsList;
        for(int i=0;i<VerticesTillNowInPath.size()-1;i++){
                Integer startVtx = VerticesTillNowInPath.get(i);
            if(allSubpathsFromGivenVertex.containsKey(startVtx)){
                foundPathsList = allSubpathsFromGivenVertex.get(startVtx);
            }else{
                foundPathsList = new ArrayList<FoundSubpath>(); 
            }

            foundSpObj = new FoundSubpath(); 
            foundSpObj.vertices = new int[VerticesTillNowInPath.size()-i-1];
            int cntr = 0;
            for(int j=i+1;j<VerticesTillNowInPath.size();j++){
                foundSpObj.vertices[cntr++] = VerticesTillNowInPath.get(j);
            }
            foundPathsList.add(foundSpObj);
            allSubpathsFromGivenVertex.put(startVtx,foundPathsList);
        }

    }

    public void printViablePaths(Integer v,ArrayList<Integer>VerticesTillNowInPath){

        ArrayList<FoundSubpath>foundPathsList;
        foundPathsList = allSubpathsFromGivenVertex.get(v);

        if(foundPathsList==null){
            return;
        }

            for(int j=0;j<foundPathsList.size();j++){
                for(int i=0;i<VerticesTillNowInPath.size();i++){
                    System.out.print(VerticesTillNowInPath.get(i)+ " ");
                }
                FoundSubpath fpObj = foundPathsList.get(j) ;
                for(int k=0;k<fpObj.vertices.length;k++){
                    System.out.print(fpObj.vertices[k]+" ");
                }
                System.out.println("");
            }
    }

    boolean DfsModified(Integer v,ArrayList<Integer>VerticesTillNowInPath,Integer source,Integer dest){


        if(v.equals(dest)){
          addAllViableSubpathsToMap(VerticesTillNowInPath);
          status[v] = 2;
          return true;
        }

        // If vertex v is already explored till destination, just print all subpaths that meet criteria, using hashmap.
        if(status[v] == 1 || status[v] == 2){
          printViablePaths(v,VerticesTillNowInPath);
          }

        // Vertex in current path. Return to avoid cycle.
        if(status[v]==1){
          return false;
        }

        if(status[v]==2){
              return true;
            }

        status[v] = 1;
        boolean completed = true;

        ArrayList<Integer>toVtcs = adjList.get(v);

        if(toVtcs==null){
            status[v] = 2;
            return true;
        }

        for(int i=0;i<toVtcs.size();i++){

          Integer vDest = toVtcs.get(i);

           VerticesTillNowInPath.add(vDest);

           boolean explorationComplete =  DfsModified(vDest,VerticesTillNowInPath,source,dest);

           if(explorationComplete==false){
           completed = false;
           }

           VerticesTillNowInPath.remove(VerticesTillNowInPath.size()-1);

        }

        if(completed){
            status[v] = 2;
        }else{
            status[v] = 0;
        }

        return completed;

    }


}


public class AllPathsCaller {

    public static void main(String[] args){

        int numOfVertices = 20;
        /* This is the number of attempts made to create an edge. The edge is usually created but may not be ( eg, if an edge already exists between randomly attempted source and destination.*/
        int numOfEdges = 200;
        int src = 1;
        int dest = 10;
        AllPaths allPaths = new AllPaths(numOfVertices);

        allPaths.randomlyGenerateGraph(numOfEdges);
        allPaths.printInputGraph();

        ArrayList<Integer>VerticesTillNowInPath = new ArrayList<Integer>();
        VerticesTillNowInPath.add(new Integer(src));
        System.out.println("List of Paths");
        allPaths.DfsModified(new Integer(src),VerticesTillNowInPath,new Integer(src),new Integer(dest));

        System.out.println("done");




    }



}

我想你和朋友们走对了路。我为一个使用bfs的解决方案提出了一些粗糙的、类似java的伪代码。其思想是存储在先前遍历期间找到的子路径及其长度，以供重用。当我找到时间的时候，我会试着改进代码，但希望它能给我一个线索，告诉我该怎么做。复杂性，我猜，应该是O（E）。
我是说，
进一步评论：
这似乎是一个合理的方法，虽然我不确定我是否完全理解我已经构造了一个简单的例子来确保我做到了。让我们考虑一个所有边加权为1的简单图，其邻接列表表示如下：
甲->乙，丙
B->C类
C->D、F
F->D类
假设我们希望找到从A到F的所有路径，而不仅仅是范围内的路径，并且源顶点的目标顶点是按字母顺序搜索的然后，该算法将按如下方式工作：
首先从B开始：
abcdf
ABCF公司
然后从C开始：
ACDF公司
活性炭纤维
是这样吗？
在这种情况下，一个简单的改进是为每个访问的顶点存储第一次访问该节点后找到的路径例如，在本例中，一旦您从B访问C，就会发现从C到F有两条路径：CF和CDF您可以保存这些信息，在下一次迭代中，一旦您到达c，您只需将cf和cdf附加到您找到的路径，就不需要进一步探索了。
若要查找范围内的边，可以使用已描述的用于如上所述生成的路径的条件。
再想想：也许你根本不需要运行Dijkstra来找到最短的路径第一次遍历子路径时，将找到子路径的长度。因此，在这个例子中，当你第一次通过B访问C时，CDF和CF的长度。这个信息可以用于下次直接通过A访问C时的修剪。这个长度比Dijkstra的发现的更准确，因为它是准确的值，而不是下限。
进一步评论：
经过一些思考，该算法可能会得到改进。例如，每次在Dijkstra算法中执行松弛步骤（在 wikipedia description中的步骤16-19），如果旧路径是可信的候选路径（小于上限），则可以使用某些数据结构记住被拒绝的旧/新子路径最后，应该可以重建所有被拒绝的路径，并将其保持在范围内。
这个算法应该是O（V^2）。
我认为每次只访问一个顶点可能过于乐观：算法如Djk斯特拉最短路径对于寻找单一路径、最短路径具有复杂性V^ 2。寻找所有路径（包括最短路径）是一个更难的问题，所以至少应该有复杂的V^ 2。
我对解决这个问题的第一个想法是改变djikstra的最短路径算法。应用此算法一次将给出最短路径的长度这将为两个顶点之间的路径长度提供一个下限从这个最短路径中一次删除一条边，然后重新计算最短路径，应该会使路径稍微长一些。
反过来，可以从这些稍长的路径中移除边以生成更多路径，依此类推。一旦有足够数量的路径，或者生成的路径超过上限，就可以停止。
这是我的第一个猜测。我是StackOverflow的新手：欢迎任何反馈。