Alex Rivera | Logout

Find the paths between two given nodes?

Asked 2009-04-03T11:09:18.033
49

Say I have nodes connected in the below fashion, how do I arrive at the number of paths that exist between given points, and path details?

1,2 //node 1 and 2 are connected
2,3
2,5
4,2
5,11
11,12
6,7
5,6
3,6
6,8
8,10
8,9

Find the paths from 1 to 7:

Answer: 2 paths found and they are 

1,2,3,6,7
1,2,5,6,7

alt text

implementation found here is nice I am going to use the same

Here is the snippet from the above link in python

# a sample graph
graph = {'A': ['B', 'C','E'],
             'B': ['A','C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F','D'],
             'F': ['C']}

class MyQUEUE: # just an implementation of a queue

    def __init__(self):
        self.holder = []

    def enqueue(self,val):
        self.holder.append(val)

    def dequeue(self):
        val = None
        try:
            val = self.holder[0]
            if len(self.holder) == 1:
                self.holder = []
            else:
                self.holder = self.holder[1:]   
        except:
            pass

        return val  

    def IsEmpty(self):
        result = False
        if len(self.holder) == 0:
            result = True
        return result


path_queue = MyQUEUE() # now we make a queue


def BFS(graph,start,end,q):

    temp_path = [start]

    q.enqueue(temp_path)

    while q.IsEmpty() == False:
        tmp_path = q.dequeue()
        last_node = tmp_path[len(tmp_path)-1]
        print tmp_path
        if last_node == end:
            print "VALID_PATH : ",tmp_path
        for link_node in graph[last_node]:
            if link_node not in tmp_path:
                #new_path = []
                new_path = tmp_path + [link_node]
                q.enqueue(new_path)

BFS(graph,"A",
algorithm path graph-theory pseudocode
Edit
Report

1 Answer

7

Dijkstra's algorithm applies more to weighted paths and it sounds like the poster was wanting to find all paths, not just the shortest.

For this application, I'd build a graph (your application sounds like it wouldn't need to be directed) and use your favorite search method. It sounds like you want all paths, not just a guess at the shortest one, so use a simple recursive algorithm of your choice.

The only problem with this is if the graph can be cyclic.

With the connections:

  • 1, 2
  • 1, 3
  • 2, 3
  • 2, 4

While looking for a path from 1->4, you could have a cycle of 1 -> 2 -> 3 -> 1.

In that case, then I'd keep a stack as traversing the nodes. Here's a list with the steps for that graph and the resulting stack (sorry for the formatting - no table option):

current node (possible next nodes minus where we came from) [stack]

  1. 1 (2, 3) [1]
  2. 2 (3, 4) [1, 2]
  3. 3 (1) [1, 2, 3]
  4. 1 (2, 3) [1, 2, 3, 1] //error - duplicate number on the stack - cycle detected
  5. 3 () [1, 2, 3] // back-stepped to node three and popped 1 off the stack. No more nodes to explore from here
  6. 2 (4) [1, 2] // back-stepped to node 2 and popped 1 off the stack.
  7. 4 () [1, 2, 4] // Target node found - record stack for a path. No more nodes to explore from here
  8. 2 () [1, 2] //back-stepped to node 2 and popped 4 off the stack. No more nodes to explore from here
  9. 1 (3) [1] //back-stepped to node 1 and popped 2 off the stack.
  10. 3 (2) [1, 3]
  11. 2 (1, 4) [1, 3, 2]
  12. 1 (2, 3) [1, 3, 2, 1] //error - duplicate number on the stack - cycle detected
  13. 2 (4) [1, 3, 2] //back-stepped to node 2 and p
answered 2009-04-03T11:52:46.667

Your Answer