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.

Do you have the picture's data in a structured form (Else you have to OCR it )? Then you can "easily" set up a matrix data structure in some form. — Youp Bernoulli, Aug 23 '22 at 14:50
The graph is just a mesh of nodes and connections, right? I'm assuming the weights change with traffic information or closure events. I guess you would cache the order of trees with nominal weights to allow quick guesses at best routes in different consditions. — Jodrell, Aug 23 '22 at 15:27

score 1 · Accepted Answer · answered Aug 23 '22 at 15:15

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]);

How to make a weighted graph of the London Underground

1 Answers1