ダイクストラアルゴリズムによるジャカルタ鉄道の最短経路
概要
「Leetcodeは過大評価されている」や「退屈な講義で学ぶ複雑なアルゴリズムやデータ構造は実際には使わない」という発言を聞いたことがありますか？
私の以前の経験は、少なくともいくつかの基本的なデータ構造を知っていることがキャリアにかなり役立つことを証明しています。この記事では、それについて詳しく説明します！
アプリの目標
アプリの名前はComuteで、主にジャカルタ、インドネシア地域で聴覚障害者が電車で通勤するのを助けることに焦点を当てたナビゲーションアプリです。アプリの主な機能は：
- ユーザーの位置を追跡
- ユーザーが通過する必要のある駅のリストを含む最短経路ルートを生成
- 特定の駅（通常は乗り換え駅と終点駅）で通知
駅のルートを達成するために、ほとんどの場合、人々はGoogle Maps APIやOpenStreetMapなどのAPIを調べます。それらの主な問題は：
- ネットワークが必要
- おそらく無料ではなく、安くもない
そこで、ダイクストラアルゴリズムを使用して最短経路を自分たちで計算するという回避策を見つけました。
ダイクストラアルゴリズム
目的と使用例
ダイクストラアルゴリズムを使用すると、グラフ内のノード間の最短経路を見つけることができます。特に、ノード（「ソースノード」と呼ばれる）から他のすべてのノードへの最短経路を見つけ、最短経路ツリーを生成できます。
このアルゴリズムは、GPSデバイスで現在地と目的地の間の最短経路を見つけるために使用されます。
歴史
このアルゴリズムは、優れたオランダのコンピュータ科学者およびソフトウェアエンジニアであるDr. Edsger W. Dijkstraによって作成され、公開されました。1959年に、彼は「A note on two problems in connexion with graphs」というタイトルの3ページの記事を発表し、新しいアルゴリズムを説明しました。
2001年のインタビューで、Dr. Dijkstraは次のように明かしました：
「ロッテルダムからグローニンゲンへの最短経路は何ですか？それは最短経路のアルゴリズムで、約20分で設計しました。ある朝、婚約者とアムステルダムで買い物をしていて、疲れてカフェのテラスに座ってコーヒーを飲みながら、これができるかどうか考えていて、最短経路のアルゴリズムを設計しました。」
基本概念
グラフは、要素のペア間の「接続」を表すために使用されるデータ構造です：
- ノードは実生活のオブジェクト、人、またはエンティティを表します
- エッジはノード間の接続です
アルゴリズムの手順
要約すると、アルゴリズムは：
- ブール配列
spt[]を取り、すべての要素を0（0=未訪問、1=訪問済み）に初期化 - 開始ノードからのノードの距離を保持する配列
v[]を作成し、無限大に初期化 - パラメータとして与えられたノードから開始し、このノードと他のすべてのノード間の最短経路を返す
- 各ノードからソースへの最短距離を計算し、より短い経路が見つかった場合はこの値を保存
- 最短経路が見つかったら、ノードを訪問済みとしてマーク
- すべてのノードが訪問されるまで手順4と5を繰り返す
時間計算量
ダイクストラアルゴリズムの計算量は実装によって異なりますが、通常は**O(n²)で、nは頂点の数です。空間計算量はO(n)**です。
結果
Comuteアプリは：
- Apple Developer Academyに取り上げられました
- Detik.com（インドネシアの主要ニュースメディア）で紹介されました
- 1,800人以上のユーザーダウンロードを達成しました
結論
この経験から、データ構造とアルゴリズムは単なる学術的な演習ではないことを学びました。それらは人々の日常生活を助けることができる実世界のアプリケーションを持っています。コーヒーを飲みながら20分で設計されたダイクストラアルゴリズムは、世界中のナビゲーションシステムを動かし続けています。