How to make a weighted graph of the London Underground

Question

I was wondering if anyone had any advice on how to go about making a weighted graph of the London underground. It is for a project so that it can be used within Dijkstra's algorithm for the shortest path.

The Dijkstra algorithm part is fine and simple graphs I can do. But the underground is very large with all the 250ish nodes that I would need.

So wondering if any simple ways to approach it?

Below is a picture of the time between the stations on the underground (the edge weights) in this scenario.

Any advice or help would be greatly appreciated.

Answer 1

A fairly simple representation would be to use a MultiValueDictionary, i.e. a dictionary that maps a single value to a collection of values. You can make your own wrapper around a Dictionary<TKey, List<T>>, or use one from Microsoft.Experimental.Collections. For example:

MultiValueDictionary<Station, (Station station, double time)) edges;

void AddConnection(Station from, Station to, double time){
   edges.Add(from, (to, time));
   edges.Add(to, (from, time));
}

Other possible representations include

• Table, just a large 2D matrix where each cell defines the time to traverse between the row and column-station, or a invalid value if a connection does not exist. Downside is that this will be unnecessary large, since most stations are only connected to two other stations.
• Objects, Create a station object with a list of connections to other stations.

You should probably take a file defining your stations, and define a function to parse this file and construct your graph. Hopefully you already have such a file, so you don't have to enter each edge by hand

Once you have a basic implementation in place I would suggest trying to make your algorithm work with kind of graph representations. You might also try to make your implementation generic, to work with any kind of node. The signature I use look something like this:

    public class Djikstra<T>  where T : IEquatable<T>
    {
        public (T FoundNode, double TotalCost) Search(
            IEnumerable<T> from,
            IEnumerable<T> to,
            Func<T, IReadOnlyCollection<(T Node, double Cost)>> graphIterator)
}

When used with a multivalueDictionary this would be called something like this

djikstra.Search(new []{fromStation}, new []{toStation}, n => edges[n]);