求めるに至った動機

虎ノ門ヒルズ駅開業や多くの徒歩連絡駅の追加など、変化が多々あったため、それらを加味してステイホーム中に経路を求めてやろうと思ったため。

計算の方法

メトロの初乗り運賃170円と都営地下鉄の初乗り運賃180円から、両者を乗り継ぐ際に適用される乗継割引70円を引いた額(170+180-70=280)増税前は260円(だった気がする)

東京メトロ・都営地下鉄には駅構内の都合から一度改札を出て乗り換えをする必要のある駅がある。また、開設当初は無関係だった駅同士を乗客の利便性向上を目的に乗換駅に指定する例もある。まずはその一覧を示す

これらの駅で乗り換えをするには条件がある。それは、発駅からその駅までの最短運賃が乗車券の金額以下であることである。例えば、表参道から渋谷までの最短運賃は170円である。今回使う乗車券の運賃は280円であるため改札を出場できる。しかし、これが西船橋からの場合渋谷までの最短運賃は290円であるため、280円の乗車券では改札を出られない。これは、乗り換えのためとはいえこのケースでの出場を許してしまうと、ここで客が乗車を終えた際に運賃をとりっぱぐれるためである。しかし、このルールが区間によっては行きと帰りで運賃が異なるという現象を生むことにもなる(詳しくは、デスクトップ鉄のデータルームをご覧ください)

一般に連絡乗車券は、発駅Aから接続駅Bまでとそこから何円区間、といった表記がなされることがほとんどである。例えば、横浜線新横浜から菊名のりかえ東急線130円区間、といった具合である。しかしながら、メトロ、都営の連絡乗車券は独特の表示をしている。発駅Aから都営地下鉄線連絡何円区間、という表示である。もうお気づきだろうが、接続駅の指定がないのである。メトロも都営も都内に蜘蛛の巣のように張り巡らされており両者の接続駅も無数に（なんと30駅も）あるからである。このおかげで我々は特に意識することなく最も便利な経路を選んで乗車をすることができる。
しかしながら、運賃の計算となると少しややこしい。ここで、メトロ、都営連絡で運賃が280円となる条件を考える。先に挙げた通り、この運賃はメトロ初乗りと都営初乗りの合計なわけだから、メトロ発駅-都営接続駅の最短運賃が170円かつ都営接続駅-都営着駅の最短運賃が180円、またはその逆に都営発駅-メトロ接続駅-メトロ着駅が同様にそれぞれ初乗りとなればいいわけである。当然ながら、この接続駅は計算上の接続駅なので、それ以外の接続駅でも発駅からの最短運賃が足りていれば改札外に出て乗り換えできる。

これらを満たすルートの中で最長のものを求めればよい

次の記事で具体的な計算に使うアルゴリズムなどを解説します