Shortest Path City map

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Shortest Path City map

Jeroen Vanattenhoven
Hello,

I'm just learning and reading about the graph theory and shortest path
algorithms. For graph representation there are 3 possibilities:
adjacency matrix for dense graphs, adjacency lists for sparse graphs and
edge lists. The road network of a city map belongs to which category?

I've also been reading that Dijkstra is applied to a directed graph.
Calculating the shortest route in a city map implies an undirected graph
(am I wrong?). So how can I do shortest path calculation of a city map
the best way?

Jeroen
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: Shortest Path City map

Doug Gregor-2

On Mar 24, 2006, at 4:12 PM, Jeroen Vanattenhoven wrote:

> Hello,
>
> I'm just learning and reading about the graph theory and shortest path
> algorithms. For graph representation there are 3 possibilities:
> adjacency matrix for dense graphs, adjacency lists for sparse  
> graphs and
> edge lists. The road network of a city map belongs to which category?

Use an adjacency list for road networks, because road networks tend  
to be very sparse.

> I've also been reading that Dijkstra is applied to a directed graph.
> Calculating the shortest route in a city map implies an undirected  
> graph
> (am I wrong?). So how can I do shortest path calculation of a city map
> the best way?

Dijkstra's algorithm works on both directed and undirected graphs.

        Doug
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users