Name:

Incase you are interested in knowing about me,id suggest you read this blog or whatever as often as you can.

Monday, July 11, 2005

All paths between two nodes in a directed graph

To find all possible paths between two nodes in a directed acyclic graph :

'path' is a list or array.

Add source_node to path ;

find_nodes ( source_node , path ) ;

find_nodes ( my_node , path )
{
if ( my_node == destination_node )
{
print path ;
return ;
}
Find all the possible nodes that are reachable directly
from my_node ;
For each such new_node found
{
Add this new_node to path ;
find_nodes ( new_node , path ) ;
Remove this new_node from path ;
}
return ;
}

This uses a technique called recursion. You might have heard that to iterate is human but to recurse, is divine.

5 Comments:

Blogger RAM said...

Thank you very much...........


Due to my lack of knowledge on graphs I have spent around two days trying to develop an algorithm for this.

Ya ur right to use recursion is divine...

11:34 PM  
Blogger Priyanka said...

Thank you so much!

2:33 AM  
Blogger Unknown said...

This comment has been removed by the author.

12:28 PM  
Blogger Unknown said...

It is very helpful for me.

12:28 PM  
Blogger Unknown said...

Thank you! God bless you..so simple, efficient and fast!

12:09 AM  

Post a Comment

<< Home


Mail me at :


whosblog@gmail.com



Websites and blogs:


Arts and Letters Daily

Papillon in Corporate

Dashdot

IIT Bombay

IRFCA

CACM


Kalpana


Killer posts:


Desiderata

Bombay's abbreviations

Home grown heroes

Bombay's deceptive climate

Bombay's nomenclature

Downpour Sunita

Gallows pole

Equality between men and women

Salsette island

Pray for a seat

Lucresia Domenguez

Hammer of the gods

Edsger Wybe Dijkstra

Gents seat in a BEST bus




















Hit Counter
Free Web Site Counter