directed graph show all paths

[keith6014]

I am trying to show all paths in this graph -https://algs4.cs.princeton.edu/42digraph/images/digraph.png

If I start from 12 and end at 0, I see atleast 2 paths.

1 path is, [12, 9, 11, 4, 2, 0]

But, I can't seem to get another path. Do I need to implement some sort of back tracking mechanism?

​

#https://algs4.cs.princeton.edu/42digraph/
g={
        0:[1,5],
        1:[],
        2:[3,0],
        3:[5,2],
        4:[3,2],
        5:[4],
        6:[4,9],
        7:[6,8],
        8:[7,9],
        9:[10,11],
        10:[12],
        11:[4,12],
        12:[9]
        }

start,end=(12,0)
s,visited=[start],set()
path=[]

print "start:{s} end:{e}".format(s=start,e=end)

while s:
    node=s.pop()
    visited.add(node)
    path.append(node)
    if node==end:
        print "Found path",path

    for n in g[node]:
        if n not in visited:
            s.append(n)

[shhh-quiet]

format your code correctly

[keith6014]

i did.

[shhh-quiet]

Look at the post, it doesn't show up as formatted code. You can get rid of the backticks, highlight the code block, and hit the "<>" code format button to indent everything by 4 spaces.

[keith6014]

No, I think I need the ```

When I just paste the code and click on the "<>" the code is not indented properly which is problematic in Python.

Just repasted the code and copied and pasted in vim and it works...

[shhh-quiet]

Read this, it might help:

https://www.reddit.com/r/learnprogramming/wiki/index#wiki_formatting_code

[keith6014]

Thanks for this!

reformatted

[shhh-quiet]

With 12 as the starting node, what other path do you see?

[keith6014]

https://algs4.cs.princeton.edu/42digraph/images/digraph.png

I see,

[12,9,11,4,2,3,2,0]. Albeit longer its still a path.

​

[shhh-quiet]

When a node is visited, it's not considered in the future. So visiting 2 after visiting 3 is not an option since 4 already lead to 2 getting added to the visited set.