Path-Finding in Subway Networks

[Paul Dale]

I played around with this kind of thing building word graphs (change one letter to make the next word in the sequence, optionally rearranging the letters). My first thought is to use Djikstra's original algorithm which avoids the priority queue but runs in O(n²) time. I'd make links along a line cost 1 and a transfer cost 10⁶ or similar -- this favours staying on a train over more transfers. The result will indicate the number of stations and the number of transfers and the path can be backtracked from the final station.

To downplay transfers, make everything cost one. In this case, the algorithm can be stopped once the destination is reached since no path can be shorter.

I went on to search for maximal diameters in the graphs.


Pauli