Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: path
I need help in enumerating all available simple paths in a directed graph. I am using quickgraph library. Is there a specific algorithm that would enumerate all paths in a digraph? I will use it to create a decoder for a machine translation and have tried DFS and BFS but it seems it only generates one path.
 
I am thinking of using DFS in beam search exploration but i cant grasp the idea and the algorithm to enumerate all simple paths.
 
Using C# programming language..
Posted 7-Jan-13 4:21am
Edited 7-Jan-13 4:22am
v2
Comments
Sergey Alexandrovich Kryukov at 7-Jan-13 18:37pm
   
You will improve you chances for a good advice if you tag language and platform. Your tag "path" is not informative.
And provide a link to "quickgraph". What is it? why using it? Ever considered writing code by yourself..?
—SA

1 solution

Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

One of the answers to this questions describes the algorithm: http://stackoverflow.com/questions/1830607/complexity-of-finding-all-simple-paths-using-depth-first-search[^].
 
You can find a lot more, just Google for it. This topic is quite popular.
 
—SA
  Permalink  

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 Maciej Los 372
1 ridoy 313
2 DamithSL 305
3 OriginalGriff 209
4 George Jonsson 140
0 OriginalGriff 7,968
1 DamithSL 6,179
2 Sergey Alexandrovich Kryukov 5,524
3 Maciej Los 5,438
4 Kornfeld Eliyahu Peter 4,539


Advertise | Privacy | Mobile
Web01 | 2.8.141223.1 | Last Updated 7 Jan 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100