先说我踩过的坑

2023年4月，我负责的外卖配送调度系统出了故障。高峰期每分钟进来3000个新订单，每个订单都要算骑手到商家的最短路径。当时用的是朴素Dijkstra，单次计算平均1.6秒。结果就是：上游队列堆积了8万条消息，骑手端订单迟迟派不出去，高峰期持续了40分钟。

事后我把整个路径计算模块用PHP 8.2重写了一遍，核心干了两件事：堆优化Dijkstra + A*启发式搜索。单次计算从1860ms压到96ms，高峰期终于能扛住了。

这篇文章不聊理论推导，直接给你能跑的代码和真实压测数据。

问题定义：配送场景下的最短路径

路网是一个无向带权图 G=(V, E)，V 是路口节点，E 是路段，每条边有权重 w(u,v)（单位：米）。给定起点 s 和终点 t，求最短路径。

配送场景有三个硬性要求：

• 快：单次计算必须 <300ms，否则高峰期扛不住
• 准：必须返回最优路径，不是近似解
• 动态：路况权重实时变化，不能依赖静态缓存

图规模：一个城市城区约 5000~20000 个路口节点，边数约 15000~60000。我司当时用的是两千万级订单的物流网络，但单城路径计算规模就是这个量级。

方案对比：三条路，一个比一个快

三条路的核心差异就一句话：Dijkstra 不知道终点在哪，四面八方都搜；A* 知道终点在哪，朝着那个方向搜。

方案一：朴素 Dijkstra

原理不赘述了，贪心 + 松弛。每轮从「未访问」节点中找距离最小的，然后更新所有邻居。

问题在「找最小」这一步：未访问节点有 V 个，每轮都要扫描一遍，所以复杂度是 O(V²)。V=5000 时，每轮扫 5000 个节点，最多 5000 轮，2500 万次比较。PHP 跑这个量级，1.8 秒很正常。

 $w) {
            if (!$visited[$v] && $dist[$u] + $w < $dist[$v]) {
                $dist[$v] = $dist[$u] + $w;
                $prev[$v] = $u;
            }
        }
    }

    return [$dist, $prev];
}

这段代码你直接在本地跑一下，5000 节点的图就要等将近 2 秒。生产环境绝对不能这么干。

方案二：堆优化 Dijkstra

优化点只有一个：把「每轮扫描找最小」换成「用最小堆取最小」，复杂度从 O(V²) 降到 O((V+E)logV)。

PHP 里有两套实现：标准库 SplPriorityQueue，和手写二叉堆。我都写了，先说标准库版本。

堆优化版本 A：SplPriorityQueue

一个巨大的坑：SplPriorityQueue 是最大堆，优先级最高的元素先出队。Dijkstra 要的是最小堆，所以插入的时候必须取负。2021 年我一个同事把负号漏了，线上路径全部反向，几十个骑手被派往相反方向。

setExtractFlags(SplPriorityQueue::EXTR_BOTH);
    // 优先级存负距离，因为 SplPriorityQueue 是最大堆
    $pq->insert([$start, 0], 0);

    while (!$pq->isEmpty()) {
        $item = $pq->extract();
        $u = $item['data'][0];
        $d = -$item['priority']; // 还原真实距离

        // 惰性删除：跳过过期的堆元素
        if ($d > $dist[$u]) continue;
        if ($u === $end) break;

        foreach ($graph[$u] as $v => $w) {
            $nd = $d + $w;
            if ($nd < $dist[$v]) {
                $dist[$v] = $nd;
                $prev[$v] = $u;
                // 同样取负
                $pq->insert([$v, $nd], -$nd);
            }
        }
    }

    return [$dist, $prev];
}

SplPriorityQueue 的问题是：它没有 decrease-key 方法。当我们发现一个更短的路径时，不能更新堆里已有元素，只能再 insert 一个重复节点。这就导致堆里会有很多过期元素，靠「惰性删除」来过滤。

堆优化版本 B：手写二叉堆

手写二叉堆支持 decrease-key，堆里每个节点只有一个元素，不会堆积重复节点。实测比 SplPriorityQueue 快约 17%。

 在 heap 中的索引

    public function push(int $node, int $value): void {
        $this->heap[] = [$node, $value];
        $idx = count($this->heap) - 1;
        $this->pos[$node] = $idx;
        $this->siftUp($idx);
    }

    public function pop(): array {
        if (count($this->heap) === 0) return [null, null];
        $top = $this->heap[0];
        $last = array_pop($this->heap);
        if (count($this->heap) > 0) {
            $this->heap[0] = $last;
            $this->pos[$last[0]] = 0;
            $this->siftDown(0);
        }
        unset($this->pos[$top[0]]);
        return $top;
    }

    public function decreaseKey(int $node, int $newValue): void {
        if (!isset($this->pos[$node])) return;
        $idx = $this->pos[$node];
        // Dijkstra/A* 中 value 只会变小，如果变大直接忽略
        if ($newValue >= $this->heap[$idx][1]) return;
        $this->heap[$idx][1] = $newValue;
        $this->siftUp($idx);
    }

    public function has(int $node): bool {
        return isset($this->pos[$node]);
    }

    public function isEmpty(): bool {
        return count($this->heap) === 0;
    }

    private function siftUp(int $i): void {
        while ($i > 0) {
            $parent = intdiv($i - 1, 2);
            if ($this->heap[$i][1] >= $this->heap[$parent][1]) break;
            $this->swap($i, $parent);
            $i = $parent;
        }
    }

    private function siftDown(int $i): void {
        $n = count($this->heap);
        while (true) {
            $left = 2 * $i + 1;
            $right = 2 * $i + 2;
            $smallest = $i;
            if ($left < $n && $this->heap[$left][1] < $this->heap[$smallest][1]) {
                $smallest = $left;
            }
            if ($right < $n && $this->heap[$right][1] < $this->heap[$smallest][1]) {
                $smallest = $right;
            }
            if ($smallest === $i) break;
            $this->swap($i, $smallest);
            $i = $smallest;
        }
    }

    private function swap(int $a, int $b): void {
        $tmp = $this->heap[$a];
        $this->heap[$a] = $this->heap[$b];
        $this->heap[$b] = $tmp;
        $this->pos[$this->heap[$a][0]] = $a;
        $this->pos[$this->heap[$b][0]] = $b;
    }
}

配合这个堆的 Dijkstra：

push($start, 0);

    while (!$heap->isEmpty()) {
        [$u, $d] = $heap->pop();
        if ($d > $dist[$u]) continue;
        if ($u === $end) break;

        foreach ($graph[$u] as $v => $w) {
            $nd = $d + $w;
            if ($nd < $dist[$v]) {
                $dist[$v] = $nd;
                $prev[$v] = $u;
                if ($heap->has($v)) {
                    // 节点已在堆中，更新它的距离
                    $heap->decreaseKey($v, $nd);
                } else {
                    $heap->push($v, $nd);
                }
            }
        }
    }

    return [$dist, $prev];
}

方案三：A* 算法

A* 和 Dijkstra 的区别只有一点：Dijkstra 只考虑起点到当前点的实际代价 g(n)，A* 额外考虑当前点到终点的估计代价 h(n)。

总代价 f(n) = g(n) + h(n)。每次优先扩展 f(n) 最小的节点，相当于给搜索加了个「方向感」。

h(n) 用欧氏距离（直线距离）。有一个关键性质叫「可采纳性」：只要 h(n) 不超过 n 到终点的真实最短距离，A* 一定能返回最优路径。因为在路网中，真实路径长度必然大于等于两点间直线距离，所以这里用欧氏距离是安全的。

push($start, $f[$start]);
    $closed = []; // 已扩展节点集合

    while (!$open->isEmpty()) {
        [$u, $fu] = $open->pop();
        if ($fu > $f[$u]) continue; // 过期元素
        $closed[$u] = true;
        if ($u === $end) break;

        foreach ($graph[$u] as $v => $w) {
            if (isset($closed[$v])) continue;

            $ng = $g[$u] + $w;
            if ($ng < $g[$v]) {
                $g[$v] = $ng;
                $prev[$v] = $u;
                $newF = $ng + heuristic($coord, $v, $end);
                $f[$v] = $newF;

                if ($open->has($v)) {
                    $open->decreaseKey($v, $newF);
                } else {
                    $open->push($v, $newF);
                }
            }
        }
    }

    return [$g, $prev, count($closed)];
}

function heuristic(array $coord, int $a, int $b): int {
    // 欧氏距离，单位：米
    // 纬度方向 1 度约 111320 米
    // 经度方向需要乘 cos(纬度) 修正
    $dx = ($coord[$a][0] - $coord[$b][0]) * 111320.0;
    $dy = ($coord[$a][1] - $coord[$b][1]) * 111320.0 * cos(deg2rad($coord[$a][0]));
    return (int) round(sqrt($dx * $dx + $dy * $dy));
}

最后是路径重建函数，三个方案共用：

 dijkstraNaive($graph, $start, $end));
benchmark('SplPriorityQueue Dijkstra', fn() => dijkstraHeap($graph, $start, $end));
benchmark('手写MinHeap Dijkstra', fn() => dijkstraMinHeap($graph, $start, $end));
benchmark('A* (欧氏距离)', fn() => astar($graph, $start, $end, $coord));

// 额外打印 A* 探索节点数
[$g, $prev, $explored] = astar($graph, $start, $end, $coord);
printf("\nA* 探索节点数: %d / %d\n", $explored, $nodes);

=== 最短路径算法压测（5000节点/15000边）===
朴素Dijkstra          :  1862.40 ms
SplPriorityQueue Dijkstra :  458.77 ms
手写MinHeap Dijkstra    :  391.20 ms
A* (欧氏距离)         :   96.84 ms

A* 探索节点数: 628 / 5000

if ($newValue >= $this->heap[$idx][1]) return;