Dijkstra for underground ?

[Franck22]

Hello Andrew,

I would like to use your dijkstra algorithm for the underground but I face some problems :

• how can I add cost when you make a transfer ?
• how can I add the line and direction you have to take ?

Could you give me a simple sample ?

I looked for weeks but didn't find anything.

Many thanks

[andrewhayward]

I'd suggest creating a node for every platform at every station on every line, and costing them appropriately. So, for example, Green Park would have six nodes...

{
  "Victoria: Green Park -> Oxford Circus": {
    // Transit
    "Victoria: Oxford Circus -> Warren Street": 5

    // Transfers
    "Victoria: Green Park -> Victoria": 1,
    "Picadilly: Green Park -> Picadilly Circus": 3,
    "Picadilly: Green Park -> Hyde Park Corner": 2,
    "Jubilee: Green Park -> Bond Street": 3,
    "Jubilee: Green Park -> Westminster": 2
  },
  "Victoria: Green Park -> Victoria": {
    "Victoria: Victoria -> Pimlico": 4,
    ...
  },
  "Picadilly: Green Park -> Picadilly Circus": {
    "Picadilly: Picadilly Circus -> Leicester Square": 5,
    ...
  },
  "Picadilly: Green Park -> Hyde Park Corner": {
    "Picadilly: Hyde Park Corner -> Knightsbridge": 4,
    ...
  },
  "Jubilee: Green Park -> Bond Street": {
    "Jubilee: Bond Street -> Baker Street": 4,
    ...
  },
  "Jubilee: Green Park -> Westminster": {
    "Jubilee: Westminster -> Waterloo": 3,
    ...
  },
  ...
}

Obviously how you name your nodes is entirely up to you, and "V:GP:A" is just as valid as "Victoria: Green Park -> Oxford Circus"... or "a" for that matter. I would probably just use short codes for your own sanity, and store the metadata in a separate object.

var stations = {
  victoria: {
    green_park: {
      name: "Green Park",
      line: "Victoria"
    },
    ...
  },
  ...
};

var platforms = {
  "V:GP:A": stations.victoria.green_park,
  "V:GP:B": stations.victoria.green_park,
  ...
};

var map = {
  "V:GP:A": {
    // Transit
    "V:OC:A": 5,

    // Transfers
    "V:GP:B": 1,
    "P:GP:A": 3,
    "P:GP:B": 2,
    "J:GP:A": 3,
    "J:GP:B": 2
  },
  ...
};

You'd have to decide whether to have duplicates for the platforms that merit it (see the District/Circle lines, for example), of if you just wanted to share the nodes between them. I suppose technically there's a cost to getting off one line and on to the other, so I'd probably keep them separate.

Is that a good start for you?