如何编写输出所有可能路径的边列表的代码？

Question

我将如何编写Python代码来获取图形的边列表，并根据起始顶点和设置结束顶点将所有可能的路径作为边列表（DFS）返回，如下面的示例输入和输出。 .

输入：

图 = [ [1,2],[2,3],[3,4],[4,2],[3,5] ] ;开始=1；结束 = [4,5]

输出：

路径 = [ [[1,2],[2,3],[3,4]] , [[1,2],[2,3],[3,5]] ]

谢谢！

Answer 1

Yen 算法 https://en.wikipedia.org/wiki/Yen%27s_algorithm

IMPORT graph, source and sink
CLEAR vShortestPaths
calculate shortest path from source to sink, add to vShortestPaths
WHILE TRUE
   CLEAR vPotentialPaths
   SET work = graph
   LOOP PF over vShortestPaths
       LOOP spur over PF
            REMOVE out edge from spur in work used by PF
            calculate spurPath, shortest path from spur to sink in work
            IF spurPath exists
                CONTINUE to next iteration of LOOP spur
            SET newPath to combination of source to spur in PF and spurPath
            IF newPath NOT in vShortestPaths
                ADD newPath to vPotentialPaths
            END LOOP spur
        END LOOP PF
    IF vPotentialPaths NOT empty
        ADD shortest path in vPotentialPaths to vShortestPaths
    END WHILE TRUE