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