How Baidu Maps Revolutionized Cycling Navigation with the HD (High Dijkstra) Algorithm

Introduction

Path planning is a core technology for driving, public transit, walking, and cycling services, and it directly impacts user experience. This article examines how major map providers, especially Baidu Maps, tackled the technical challenges of cycling navigation.

Cycling Path Planning Basics

In the LBS industry, path planning means finding one or more routes from a start point to an end point on a weighted road network graph using a search algorithm . To enable cycling navigation, two prerequisites are required:

A road network model suitable for cycling

A search algorithm optimized for cycling

1. Cycling Road Network Model

According to Chinese traffic regulations, motor vehicles, non‑motor vehicles, and pedestrians must follow specific traffic rules. Therefore, a cycling road network should have the following characteristics:

Traffic rules : ride on the right side of dedicated bike lanes; where no bike lane exists, ride on the right side of the vehicle lane.

Non‑traversable roads : highways and any road explicitly prohibiting non‑motorized vehicles.

The resulting model is a directed weighted graph that represents only the subset of the road network where cycling is permitted.

2. Cycling Search Algorithm

Baidu Maps launched its cycling navigation in May 2015 and has gone through three major algorithmic milestones:

Sprint 1 – A* : built an initial routing engine based on the A* algorithm and released it on May 18.

Sprint 2 – HD (High Dijkstra) : introduced the HD algorithm to overcome A*’s performance and optimality limitations, achieving a major technical breakthrough and launching on September 10.

Sprint 3 – HD+ : further optimized the HD algorithm for both performance and reasonableness, releasing the enhanced version on December 16.

Sprint 1: A*

Initially, Baidu Maps reused the well‑known A* algorithm to quickly deliver a cycling routing engine, meeting the urgent product launch schedule.

Sprint 2: HD

User feedback highlighted two main pain points: poor usability (99.99% of targets were far from optimal) and unreasonable routes (70% of complaints concerned accuracy). To address these, Baidu introduced the HD algorithm, which combines Dijkstra’s optimality with space‑time trade‑offs via offline preprocessing and a sparse virtual topology.

HD Algorithm Foundations

Dijkstra guarantees optimal routes.

Reducing the search space improves performance.

Techniques from CH and CRP algorithms align with these goals.

Map hierarchical display mirrors human map‑reading.

Virtual topological layers derived from hierarchical maps further shrink the search space.

HD Algorithm Design

The HD algorithm adopts a “space for time” strategy: offline preprocessing creates a simplified, sparse virtual topology, then a layered, bidirectional Dijkstra search runs on this structure.

It consists of two main components:

Offline preprocessing : cluster the cycling network into adjacent closed regions, then build a simplified virtual topology.

Online search : perform layered, bidirectional Dijkstra on the virtual topology.

Sprint 3: HD+

Further optimizations focused on memory management, collision condition handling, and parallelizing the preprocessing pipeline, resulting in significant speed gains.

Conclusion

The HD algorithm is fundamentally a Dijkstra‑based method that ensures route optimality while leveraging a virtual topology to dramatically reduce search space. Benchmarks show that on PC the routing time is sub‑second for any two points, and on mobile devices routes under 1000 km also return in sub‑second latency. Compared with A*, HD improves performance by 2–10×, with larger gains on longer routes.