What's faster? Searching for shortest path in a matrix or a list?

I have to store some cities and the distances between some of them and then search for the shortest path. The cities and the distances are read from a file. I started with doing a matrix but saw that it took too much space(more than double) so I changed to a list. Each list item stores 3 things: point1, point2 and the distance between them.

So for example I have this file:

Athens Stockholm 34

Stockholm Prague 23

which when I read is stored in the array as this:

          _____0______ ______1______
point1   | Athens     | Stockholm   |
point2   | Stockholm  | Prague      |
distance | 34         | 23          |
          ------------ -------------

Then I got some doubts.. This sur开发者_开发问答ely saves space but is it going to take more time to go through? The list is an array but the connections(edges) are placed in an arbitrary way and that's why I started thinking that it may take more time than if I used a matrix.

You might want to look into the adjacency-list representation of graphs, which is a modified version of your second idea that's best suited for shortest path problems. The idea is to have a table of nodes where for each node you store a list of outgoing edges from that node. This allows you to iterate over all the edges leaving a node in time proportional to the number of edges you have leaving a node, not the total number of edges in the graph (as you have in both the matrix and list versions suggested above). For this reason, most fast algorithms for doing graph searches use adjacency lists.

Hope his helps!

Separate the names from the distances. Create a list that just contains city names.

          _____0______ ______1______ ______2______ 
city     | Athens     | Stockholm   | Prague      |
          ------------ ------------- -------------

Then create the matrix separately

     __0__ __1__ __2__ 
 0  | 0   | 34  | 0   |
     ----- ----- -----
 1  | 34  | 0   | 23  |
     ----- ----- -----
 2  | 0   | 23  | 0   |
     ----- ----- -----

If you want to search, say, a route from Prague to Athens, then you start by finding where Prague and Athens are in the list...

• Prague: 2
• Athens: 0

Then you search through the matrix for your path.

• (2,1,23) -> (1,0,34)

Finally, you translate to cities using your list

• (Prague, Stockholm, 23) -> (Stockholm, Athens, 34)

I think that adjecency lists here are surely the best option here. The're later very useful when it comes to algorithms like D/BFS or Dijkstra.

If you don't know how to keep both towns and distances just use some structure to keep them both together. If you could use numbered indexed towns you would use just a simple pair structure (also the easiest implementation would be n STL vectors of pair.

Of course if you don't want to use STL you should try implementing own lists of structures with pointers you would want to use.

Your approach looks just fine.

To relax your mind, remember that parsing a single list/array will always be be faster and more resource friendly than working with two (or more) lists when you practically just need to look up a single line/entry of predefined data.

I tend to disagree with some of the other answers here, since I do not see any need to complicate things. Looking up several data-cells and the additional need to be combine those data-cells to produce a resulting data set (as some answers proposed), takes more steps than doing a simple one-time run over a list to fetch a line of data. You would merely risk losing CPU cycles and memory resources for functions that lookup and combine distributed data-cells across several lists, while the data you currently use already is combined as a collection of perfect results.

Simpler said: doing a simple run-down on the list/array you currently have is hard to beat when it comes to speed.