questions about AlgorithmExtensions.ShortestPathsAStar

May 2, 2009 at 12:28 PM
I have two questions about using AlgorithmExtensions.ShortestPathsAStar:

1) it only accepts a graph of type IVertexAndEdgeListGraph which is a directed graph. Why does it not accept an undirected graph?

2) the heuristic cost function is of type Func<TVertex, double>. How do I set up a heuristic cost function that is the straight line distance from the current node to the target node? Surely I need two arguments in the function?

Thanks in advance

May 2, 2009 at 2:13 PM
Edited May 2, 2009 at 2:14 PM
One other question:

- if I want to calculate just one shortest path (using Dijkstra or AStar) from node X to node Y can I do this ? At the moment the system only seems to provide the facility to calculate either all shortest paths or all shortest paths from node X.

Thanks again.
May 14, 2009 at 3:45 PM

Please split question in different posts. It's easier to track.

(1) use the BidirectionalUndirectedGraph to turn your undirected graph into a directed graph.
(2) you can use a closure to encapsulate the target node in the delegate:

    TVertex target = ...
    Func<TVertex, double> cost = (v, d) => d + GetDistance(d, target);

(3) that's correct. I should  probably add a way to shortcut the search.

May 15, 2009 at 1:37 PM

thanks for your reply. However I am still stuck on point 2. In a* the heuristic distance is the distance from the current vertex to the target vertex. For the heuristic cost delegate I would need to know the current node and the target node. Since neither of these seem to be passed in as arguments I am stuck.

Sorry if I'm missing something obvious.


May 15, 2009 at 3:14 PM

the reason I asked point (3) (calculate just one shortest path) is that for an undirected graph the shortest path from (a to b) should be the same as (b to a) I think? I am trying to optimise my code...