Google Maps 一秒算路線的背後：不是只靠 Dijkstra，而是圖論、階層預處理與即時權重

Maps / Graph Algorithms / Local SEO

Threads 貼文從一支導航演算法視覺化影片切入：搜尋路徑像波紋一樣從起點與終點同時擴散，最後在中間交會，這是雙向搜尋的直觀畫面。真正值得保存的是：導航系統把道路世界轉成加權圖，再用 Dijkstra / A* / Bidirectional Search / Contraction Hierarchies / Multi-level Routing 等技術，把巨大搜尋空間壓縮到可即時查詢。

保守解讀：Google Maps 內部完整演算法並不公開，不能簡化成只用某一種技術。比較合理的理解是：現代導航由圖論建模、預處理索引、階層路網、即時交通權重、ETA 預測與多路線最佳化共同組成。

道路就是圖

路口可視為 node，道路可視為 edge，距離、時間、限制與交通狀態可視為 weight。導航問題本質上是巨大加權圖上的最小成本路徑問題。

為何不能只靠 Dijkstra

全球道路網節點可能達數千萬、邊數上億。傳統 Dijkstra 雖然正確，但直接擴散搜尋太慢，因此需要 A*、雙向搜尋與階層式預處理。

Contraction Hierarchies

CH 的直觀想法是道路不等價：高速公路、幹道比巷弄更常出現在長距離路線。系統預先建立重要性階層與 shortcut，查詢時可少拜訪大量低價值節點。

技術	作用	限制
Dijkstra	在非負權重圖中保證找到最短路徑。	大圖直接查詢成本高。
A*	用 heuristic 引導搜尋方向，減少不必要擴散。	heuristic 品質會影響效率與適用性。
Bidirectional Search	起點與終點同時搜尋，在中間交會。	需要處理反向邊、停止條件與權重一致性。
Contraction Hierarchies	預處理階層與 shortcut，大幅縮小查詢空間。	路網或權重頻繁變動時，更新成本與動態 traffic 融合較複雜。
Realtime traffic weighting	把塞車、封路、事故、速度與限制納入 weight。	資料延遲、GPS 誤差、道路上下層重疊都會造成錯誤。

Local SEO 角度可轉成的實務檢查：

商家地標位置是否正確，入口是否落在可導航位置。
是否靠近主要幹道、交流道、停車場、捷運/公車站等可達性節點。
Google 商家資訊、營業時間、類別、電話與網站是否一致。
提高真實點擊、導航、到店、停留、評論與互動，而不是只塞關鍵字。
若導航常繞路，應回報道路、入口或地標修正，因為可達性會影響使用者行為。

來源：
Threads 原文：https://www.threads.com/@mr_gmap/post/DYwNcSDgdQf
Google Maps Platform Routes / Route Optimization docs：https://developers.google.com/maps/documentation/route-optimization
Contraction Hierarchies paper：Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks