Re: [Boost-users] Shortest Path City map

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-04-10 16:02:05

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