日本から3ホップ以内にすべての国に到達できるか

Wikipediaには空港の存在しない国の一覧という記事があり、ここに載っている5カ国については明らかに到達できないのだが、そういったそもそも空港が国内にない国を除いたとしたら、日本から3ホップ、つまり日本からある国Aとある国Bを経由して全ての国に到達できるか、という命題をしばらく前から考えていた。

日本から南米のパラグアイだって、例えば羽田 → マドリード → アスンシオンというルートが存在する。南太平洋のナウルだって成田 → ブリスベン → ナウルというルートで到達できる。アフリカ大陸のマイナーな国レソトも羽田 → 香港 → ヨハネスブルグ → レソトとなり3ホップだ。2ホップでもかなり多くの国に到達できるし、いくら遠方だとしても3ホップ使えればどの国だってとりあえず到達できるのではないだろうか。

ネットで調べてみてもとくに言及されているような投稿も見つからなかったので自分で確かめてみることにした。世界の航空路線に関するオープンデータとしてOpenFlights.orgというものがあるのでこれを使わせていただくことにする。このデータは世界の空港と、その空港を結ぶ定期運行便をおおむね網羅したデータベースだ。収録されているデータ自体は2014年で更新が止まっているため最新のデータとは言えないものの、この10年くらいであれば新規の直行便開設による経路短縮はあるかもしれないが、たいていの路線は現在と同じように就航されているだろうと判断しそのまま使うことにした。もし新たに開拓された路線があったとしても、その数は限られていると思うので結果を吟味する際に検討しよう。

必要なフライト数の調べ方はそれほど難しくない。世界中すべての空港を対象にすると数万では収まらない数の就航フライトを考えないとならないので少々計算量は増えるが、今回知りたいのは単に日本から他国というだけなので、すべてのフライトを国単位に集約させたと考えれば国連加盟国のみを対象としても193ノード程度のごく小さなグラフにとどまる。この程度ならグラフDBを使う必要もなく、単にメモリ上で国同士の隣接グラフを構築し、日本ノードから幅優先探索で最短ホップ数を調べ、3を超えた経路をはじき出すだけである。総当たりというか、隣接行列のかけ算でもとめてもこの規模では余裕である。注意すべき点として、OpenFlightsのデータにおいて国の記載はISO3166に従っているとのことなので、そこに国連加盟国に限るという条件を付けるのであれば事前に不要なノードを削除しておく必要がある。

というわけで、日本からの必要フライト数で国連加盟国をまとめた結果が以下となる。

── 0 hops (1) ──
Japan

── 1 hop (33) ──
Australia, Austria, Canada, China, Denmark, Finland, France, Germany, India, Indonesia, Italy, Malaysia, Mexico, Mongolia, Myanmar, Netherlands, New Zealand, Palau, Papua New Guinea, Philippines, Qatar, Russia, Singapore, South Korea, Sri Lanka, Switzerland, Thailand, Turkey, United Arab Emirates, United Kingdom, United States, Uzbekistan, Vietnam

── 2 hops (139) ──
Afghanistan, Albania, Algeria, Angola, Antigua and Barbuda, Argentina, Armenia, Azerbaijan, Bahamas, Bahrain, Bangladesh, Barbados, Belarus, Belgium, Belize, Benin, Bhutan, Bolivia, Bosnia and Herzegovina, Brazil, Brunei, Bulgaria, Burkina Faso, Cabo Verde, Cambodia, Cameroon, Central African Republic, Chad, Chile, Colombia, Congo (Brazzaville), Congo (Kinshasa), Costa Rica, Cote d'Ivoire, Croatia, Cuba, Cyprus, Czech Republic, Djibouti, Dominican Republic, East Timor, Ecuador, Egypt, El Salvador, Estonia, Ethiopia, Fiji, Gabon, Georgia, Ghana, Greece, Grenada, Guatemala, Guinea, Guyana, Haiti, Honduras, Hungary, Iceland, Iran, Iraq, Ireland, Israel, Jamaica, Jordan, Kazakhstan, Kenya, Kiribati, Kuwait, Kyrgyzstan, Laos, Latvia, Lebanon, Liberia, Libya, Lithuania, Luxembourg, Madagascar, Maldives, Mali, Malta, Marshall Islands, Mauritania, Mauritius, Micronesia, Moldova, Montenegro, Morocco, Namibia, Nauru, Nepal, Nicaragua, Niger, Nigeria, North Korea, North Macedonia, Norway, Oman, Pakistan, Panama, Paraguay, Peru, Poland, Portugal, Romania, Rwanda, Saint Kitts and Nevis, Saint Lucia, Samoa, Saudi Arabia, Senegal, Serbia, Seychelles, Sierra Leone, Slovakia, Slovenia, Solomon Islands, Somalia, South Africa, South Sudan, Spain, Sudan, Suriname, Sweden, Tajikistan, Tanzania, Togo, Tonga, Trinidad and Tobago, Tunisia, Turkmenistan, Uganda, Ukraine, Uruguay, Vanuatu, Venezuela, Yemen, Zambia, Zimbabwe

── 3 hops (15) ──
Botswana, Burundi, Comoros, Dominica, Equatorial Guinea, Eritrea, Eswatini, Gambia, Guinea-Bissau, Lesotho, Malawi, Mozambique, Saint Vincent and the Grenadines, Sao Tome and Principe, Tuvalu

── Not in flight data (5) ──
Andorra, Liechtenstein, Monaco, San Marino, Syria

日本から1ホップで到達できる国が33カ国、2ホップで到達できる国が139カ国、3ホップかかる国が15カ国あり、4ホップ以上かかる国は一カ国もなく、到達不能な国が5つある、という結果となった。

フライトデータが存在しなかった5カ国のうち、アンドラ、リヒテンシュタイン、モナコ、サンマリノは前述の通り国内に空港が存在しないため到達不能国として出現するのは正しい。また、シリアはOpenFlightsのデータが編纂された2014年当時はちょうどシリア内戦によって国際線がすべて停止していたタイミングと符号している。シリアにはトルコやドバイ、ドーハなど中東諸国からのフライトが現在就航しているためこの結果から削除してもよいだろう。さらに、国内に空港が存在しない国としてWikipedia上で挙げられていたバチカン市国は国連加盟国ではないため、今回の探索対象から外れる。

結論として、日本から3ホップ以内に到達できない国というのは、空港が存在しない国をのぞけば一カ国も存在しないことがわかる。日本から地球上のどの国であれ、空港のある国ならどこでも3回飛行機に乗ればたどり着けるのだ！

3ホップ必要な国について

結果を吟味するため、日本から最短でも3ホップ必要になると計算された国を眺めてみる。すると大半がアフリカ、一部カリブとオセアニアであることがわかる。それらの国へ到達するまでのルートをOpenFlightデータを元に計算してみるとそれぞれ以下のようになった（結果は一例）。

Botswana: Japan → South Korea → Kenya → Botswana
Burundi: Japan → South Korea → Kenya → Burundi
Comoros: Japan → South Korea → Kenya → Comoros
Dominica: Japan → United States → Netherlands Antilles → Dominica
Equatorial Guinea: Japan → South Korea → Spain → Equatorial Guinea
Eritrea: Japan → Philippines → Saudi Arabia → Eritrea
Eswatini: Japan → China → South Africa → Eswatini
Gambia: Japan → South Korea → Spain → Gambia
Guinea-Bissau: Japan → United States → Morocco → Guinea-Bissau
Lesotho: Japan → China → South Africa → Lesotho
Malawi: Japan → South Korea → Kenya → Malawi
Mozambique: Japan → South Korea → Kenya → Mozambique
Saint Vincent and the Grenadines: Japan → United States → Barbados → Saint Vincent and the Grenadines
Sao Tome and Principe: Japan → China → Angola → Sao Tome and Principe
Tuvalu: Japan → South Korea → Fiji → Tuvalu

うーん、なんとなく合ってそうに見えるが、しかし奇妙なルートが最短経路として出ている（旅慣れてくると一目でわかるようになるのだ）。たとえば赤道ギニアは韓国を経由してスペインから赤道ギニアに至っているが、日本からスペインの直行便は存在しているのでこの経路は明らかに最短ではない。また、ツバルも韓国を経由しているがこれも成田からフィジーへの直行便が存在しているので正しくない。ほかにも韓国経由ケニア行きの便（Japan → South Korea → Kenya）が頻出しているのが目立つものの、仁川ナイロビ線は10年以上前に廃止されている。OpenFlightsのデータは信頼できるものなのだろうか。

そう思って各路線が就航したタイミングを調べてみると、どうもOpenFlightsのデータが制作されたタイミングでは両路線はまだ存在していなかったと見られる。成田空港のプレスリリースを確認したところ、どちらも編纂されたタイミングである2014年には存在しないフライトであることがわかった。

成田〜マドリード線は2016年就航

成田〜ナンディ線は2018年就航

そのため韓国迂回ルートが算出されていたことがわかる。今回の目的に対しては十分な精度を持っていると考えてもよさそうだ。

成田からナイロビの経由便候補

また、仁川-ナイロビ線がすでに廃止されているという点についても、日本-XX-ナイロビを満たす代替ルートはトルコや中国、ヨーロッパや中東、遠回りを許せばニューヨーク路線などに多数存在している。かなりロバストな命題と言ってもいいだろう。

4次の隔たり

日本から3ホップ必要な国の中でも直感的に遠そうだなと感じる組み合わせとして、サントメプリンシペとツバルを考えてみよう。サントメプリンシペはアフリカ中西部の離島、ツバルはオセアニアの島嶼国である。かなり貧弱な航空路線しか持っていないこの2カ国間をフライトでつなぐとどうなるか。結果としては次のようになる。

Sao Tome and Principe → Portugal → United States → Fiji → Tuvalu

ぱっと見であきらかに遠そうな2カ国であっても4ホップでつながることができている。就航都市数の大きい日本は3ホップで全ての国に到達できたが、一方で両端がマイナーな国であっても4ホップと、その差はわずか1ホップしかないのだ。どうにも不思議な感じがする。

そこで全188カ国（国連加盟国193 - 空港のない4カ国（空港のない5カ国からバチカンを抜いた数） - 元データ上存在しないシリア1カ国 ＝ 188）の各国に対し、ほか187カ国への最短到達経路を調べてみた。すると興味深いことに、日本と同じく3ホップ以内に全ての国に到達可能な国が76カ国、4ホップ必要になる国が112カ国、そして5ホップ必要になる国は一カ国も存在しなかった。つまりどの国を起点に選んだとしても、世界中の約4割の国は3ホップ以内に全ての国にいくことができ、残り6割の国も最大4ホップで全ての国に到達可能なのである。世界は思ったより狭い。ちなみに最も孤立した国はツバルだった。国際線がフィジーだけの一路線しか就航していないため、世界82カ国から4ホップ必要となっている。

六次の隔たりという有名な仮説がある。これは世界の誰であれ自分の知り合いを6人たどることで誰とでもつながることができるという話であるが、それの国家版と言えそうだ。どのような国であれ、限られた数の飛行機や空港の発着枠の価値を最大化しようとすると地域のハブとなるようなある程度大きな都市とつながろうとする意思が働くのだろう。その結果自然とグラフの距離が収斂していくというのは面白い現象だなと思った。