Question about graphs and dijkstra

Topics: algorithm, graph
May 31, 2007 at 4:38 PM
Hi I am a new user and have just discovered about this useful library. I have a project at school, it is a route planner for a city. What type of graph should I use. I am trying with an AdjacencyGraph, will it work? How can I add the cost for each edge? How can I implement dijsktra with it?. Thanks.
Coordinator
Jun 2, 2007 at 6:54 AM
The DijkstraShortestPathAlgorithm takes a IVertexListGraph (AdjacencyGraph implements this interface) and a map edge -> double that represent the weights of each edge.

Jun 2, 2007 at 10:06 AM
Thanks so I can use the graph creared from the Adjancency Class. Also can you further explain a map edge -> double that represent the weights of each edge. Thanks :)
Coordinator
Jun 3, 2007 at 4:45 AM
Populate the graph instance.
Create a dictionary with an Edge as key, float as value.
for each edge in the graph, assign a weight (i.e. distance) to the edge in the dictionary.
Jun 5, 2007 at 2:48 PM
Is there a limit to the number of edges? I have tried to declared 25 edges but only 20 edges where seen. Thanks
Jun 5, 2007 at 3:27 PM
Fix. it :) For example

AdjacencyGraph<int, MarkedEdge<int, string>> Ortigas = new AdjacencyGraph<int, MarkedEdge<int, string>>();

I have already added the vertex and edges. How can to i create a dictionary and add the wieght. Sorry but I can't just really understand.
Coordinator
Jun 5, 2007 at 4:29 PM
Edited Jun 5, 2007 at 4:30 PM
Dictionary<MarkedEdge<int, string>, double> weights = 
    new Dictionary<MarkedEdge<int, string>, double>(Ortigas.EdgeCount);
foreach(MarkedEdge<int, string> e in Ortigas)
{
    weights.Add(e, <put the weigth here>);
}
Jun 5, 2007 at 5:56 PM
Thanks. How can i convert the Adjacency Graph so that it can be read by dijkstra algorithm?
Coordinator
Jun 5, 2007 at 11:42 PM
You don't have to convert in any way. Adjacency graph implements the interface that the algorithm consumes
Jun 6, 2007 at 3:35 AM
Thanks.

DijkstraShortestPathAlgorithm<int, Edge<int>> dijkstra = new DijkstraShortestPathAlgorithm<int, Edge<int>>(Ortigas,weights); ?
Coordinator
Jun 6, 2007 at 4:57 AM
Yes
Jun 6, 2007 at 12:16 PM
An error occured is says that it can convert the adjaceny graph to IVertex
Jun 6, 2007 at 1:44 PM
Error 1 The best overloaded method match for 'QuickGraph.Algorithms.ShortestPath.DijkstraShortestPathAlgorithm<int,QuickGraph.Edge<int>>.DijkstraShortestPathAlgorithm(QuickGraph.IVertexListGraph<int,QuickGraph.Edge<int>>, System.Collections.Generic.IDictionary<QuickGraph.Edge<int>,double>)' has some invalid arguments C:\Documents and Settings\Administrator\Desktop\Route Navigator\Route Navigator\Route Navigator\Program.cs 346 70 Route Navigator

Error 2 Argument '1': cannot convert from 'QuickGraph.AdjacencyGraph<int,QuickGraph.MarkedEdge<int,string>>' to 'QuickGraph.IVertexListGraph<int,QuickGraph.Edge<int>>' C:\Documents and Settings\Administrator\Desktop\Route Navigator\Route Navigator\Route Navigator\Program.cs 346 120 Route Navigator

Error 3 Argument '2': cannot convert from 'System.Collections.Generic.Dictionary<QuickGraph.MarkedEdge<int,string>,double>' to 'System.Collections.Generic.IDictionary<QuickGraph.Edge<int>,double>' C:\Documents and Settings\Administrator\Desktop\Route Navigator\Route Navigator\Route Navigator\Program.cs 346 128 Route Navigator

Coordinator
Jun 6, 2007 at 3:44 PM
Using generic, you have to be precise with types:

DijkstraShortestPathAlgorithm<int,QuickGraph.MarkedEdge<int>>
Jun 6, 2007 at 4:30 PM
Sorry but it doesn't work :( Can i send you my codes?
Jun 6, 2007 at 5:01 PM
I got it thank you very much :)
Jun 6, 2007 at 5:34 PM
One last question I hope. Is it possible to compute for the second best path. If it is can you show me how. Thank you very much.
Coordinator
Jun 7, 2007 at 1:05 AM
I let this answer as an 'exercise for the reader'.
Jun 8, 2007 at 4:38 PM
Thank you very much. Without you and Quickgraph I can't complete my project.