All Paths

This option finds all the paths between two nodes in a directed graph

Input

format

The first line specifies the calculation required. It must contain

format allpathscosted for graphs with costed edges

OR

format allpaths for graphs with uncosted edges

graph mode

Column	Description
1	g for graph
2	1 edges are directed
3	1

This must be the second line.

Links

Column	Description
1	l for link
2	src node name
3	dst node name

start

Column	Description
1	s
2	starting node name
3	cost ( if required )

end

Column	Description
1	e
2	node name

Example

format allpathscosted
g 1 1
l c d 3
l d f 4
l c e 2
l d e 1
l e f 2
l e g 3
l f g 2
l g h 2
l f h 2
s c
e h

Algorithm

Yen's Algorithm 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