Using DFS for all paths in conjunction with DijkstraShortestPathAlgorithm

Topics: algorithm, graph
Dec 5, 2008 at 10:23 AM
Hi all,
  I'm working on a small project to learn .NET 3.5 after transitioning from Java.  I'm using the QuickGraph API to write a simple traveling management program. 

I'm using an AdjacencyGraph and a Dictionary for weighted edges for my graphs and distances.  I can easily find the shortest path from x to y with the DijkstraShortestPathAlgorithm. 

I also want to give users the ability to pick a path even if its not the most efficient.  I'm attempting to do this with the DepthFirstSearch and specifying the starting node.  However, I'm having trouble with the callbacks and correctly determining all possible paths.  I've taken a look at the DepthFirstSearchAlgorithmTest.cs file for some guidance, but its not helping.  Is there an existing algorithm to do this?  If not, any help would be greatly appreciated.

Thanks,
Todd
Coordinator
Dec 6, 2008 at 6:03 AM
What you want to do is to create a VertexPredecessorRecorderObserver, attach it to the DFS algorithm and 'Compute'. The recorder will store the map of precessor and provides API to extract paths.

 

var predecessors = new VertexPredecessorRecorderObserver<TVertex, TEdge>();
using (ObserverScope.Create(dfs, predecessors))
    dfs.Compute();

IEnumerable<TEdge> edges;
if(predecessors.TryGetPath(v, out edges))
    ...

You can also use the CyclePoppingRandomTree to efficiently cover a graph with a tree.

Dec 10, 2008 at 4:34 PM
Hi Boys,

please help me. How can I have all possible paths between two vertices using DFS algorithm?

How can I find them using CyclePoppingRandomTree.


Thanks.
Dec 10, 2008 at 8:08 PM
Edited Dec 10, 2008 at 8:24 PM
Hi,

I need to find all shortest paths between two vertices, now to find them I iterate Dijkstra n-times deleting the prevoius path founded. 
It' s too slow, can you say me if there'is something faster.

Thanks.


P.S.

Searching I found this Algo: K Shortest Paths
Do you know?
Dec 11, 2008 at 1:48 AM
I used recursion and lists to build my paths. If my current vertex equals my starting vertex, I push the list of verticies into my results, the remove the last vertex from my current path and return. Eventually this covers all verticies from Vertex A to B, and it avoids duplicates.



On Thu, Dec 11, 2008 at 9:09 AM, giomuti <notifications@codeplex.com> wrote:

From: giomuti

Hi,

I need to find all shortest paths between two vertices, now to find them I iterate Dijkstra n-times deleting the prevoius path founded.
It' s too slow, can you say me if there'is something faster.

Thanks.

Read the full discussion online.

To add a post to this discussion, reply to this email (quickgraph@discussions.codeplex.com)

To start a new discussion for this project, email quickgraph@discussions.codeplex.com

You are receiving this email because you subscribed to this discussion on CodePlex. You can unsubscribe on codePlex.com.

Please note: Images and attachments will be removed from emails. Any posts to this discussion will also be available online at codeplex.com


Dec 11, 2008 at 6:55 AM
Edited Dec 11, 2008 at 7:34 AM
Can you post the code?Thanks..
Dec 11, 2008 at 8:13 AM
Sorry, its code for work. Do some searching of the forums. You'll find an an algorithm that helped me, you'll just need to modify it to use the results from the Graph search.

On Thu, Dec 11, 2008 at 7:55 PM, giomuti <notifications@codeplex.com> wrote:

From: giomuti

Can tou post the code?Thanks..

Read the full discussion online.

To add a post to this discussion, reply to this email (quickgraph@discussions.codeplex.com)

To start a new discussion for this project, email quickgraph@discussions.codeplex.com

You are receiving this email because you subscribed to this discussion on CodePlex. You can unsubscribe on codePlex.com.

Please note: Images and attachments will be removed from emails. Any posts to this discussion will also be available online at codeplex.com


Dec 11, 2008 at 8:27 AM
Is this the algorithm:

public void FindPath(int S, int E, ArrayList Path)
{
if (S == E)
{
Path.Add(S);
AllPath.Add(new ArrayList(Path));
Path.RemoveAt(Path.Count - 1);
return;
}
if (Path.Contains(S))
return;

Path.Add(S);

var K = g.OutEdges(S).GetEnumerator();

while (K.MoveNext())
{
FindPath(K.Current.Target, E, Path);
}
Path.RemoveAt(Path.Count - 1);
}

I' ve posted that. It's too slow for my adjacency graph.

Someone knows k Shortest paths algo?

Coordinator
Dec 11, 2008 at 8:38 AM
K-shortest path are not implemented in QuickGraph. There are numerous papers describing various algorithms. All of them are non-trivial to implement.
Dec 12, 2008 at 3:49 AM
Correct.

On Thu, Dec 11, 2008 at 9:27 PM, giomuti <notifications@codeplex.com> wrote:

From: giomuti

Is this the algorithm:

public void FindPath(int S, int E, ArrayList Path)
{
if (S == E)
{
Path.Add(S);
AllPath.Add(new ArrayList(Path));
Path.RemoveAt(Path.Count - 1);
return;
}
if (Path.Contains(S))
return;

Path.Add(S);

var K = g.OutEdges(S).GetEnumerator();

while (K.MoveNext())
{
FindPath(K.Current.Target, E, Path);
}
Path.RemoveAt(Path.Count - 1);
}

I' ve posted that. It's too slow for my adjacency graph.

Someone knows k Shortest paths algo?

Read the full discussion online.

To add a post to this discussion, reply to this email (quickgraph@discussions.codeplex.com)

To start a new discussion for this project, email quickgraph@discussions.codeplex.com

You are receiving this email because you subscribed to this discussion on CodePlex. You can unsubscribe on codePlex.com.

Please note: Images and attachments will be removed from emails. Any posts to this discussion will also be available online at codeplex.com


Dec 13, 2008 at 10:44 PM
Hi,

something new about k-th shortest paths?

Thanks you for your patience.

Bye.
Coordinator
Dec 14, 2008 at 1:06 AM
k-th shortest path is a hard problem. It's not clear when I will have the time to implement something for it.
Dec 14, 2008 at 10:00 AM
ok, thanks.


Coordinator
Jan 5, 2009 at 9:52 PM
k-shortest path have been implemented in quickgraph. See HoffmanPavley algorithm.