
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

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
participants (2)
-
Doug Gregor
-
Jeroen Vanattenhoven