一次让我失眠的路径规划事故

2023年11月，我们做同城配送系统。3000个配送点，车辆需要实时计算最优路径。上线第一天，数据库CPU直接飙到100%。查日志，发现路径规划接口平均耗时2.8秒——用户早就不耐烦地退了。

更尴尬的是，这套系统跑在8核16G的云服务器上，一套路径计算就要吃掉一个核。加机器？老板说预算砍半。

于是我开始折腾最短路径算法。从最简单的Dijkstra到堆优化，再到A*。最后把2.8秒压到了60毫秒。这篇文章把过程、代码、坑全部记录下来。

问题定义

我们的场景是：配送网络抽象成有向图，节点是配送点，边是实际道路距离（加权）。需要计算任意两个节点之间的最短路径。

图的规模：节点数 N = 3000，边数 M = 12000（稀疏图，平均出度4）。

运行环境：PHP 8.3.2，8核16G，CentOS 7.9。

方案对比：三种思路

一开始我选了朴素Dijkstra，因为当时觉得3000节点不大。事实证明我错了。

朴素Dijkstra：为什么慢

朴素版的核心是：每次从未访问节点中线性扫描出距离最小的那个。每轮扫描 O(V) 次，总共 V 轮，所以 O(V²)。

3000个节点，就是约 900万次比较。看似不多，但加上松弛操作和PHP的数组开销，实测单次计算2.8秒。

// PHP 8.3 朴素Dijkstra——性能瓶颈演示，千万别用于生产
class NaiveDijkstra {
    private array $graph;
    private int $nodeCount;

    public function __construct(array $graph) {
        $this->graph = $graph;
        $this->nodeCount = count($graph);
    }

    /**
     * 返回节点 $start 到 $end 的最短距离
     */
    public function shortestPath(int $start, int $end): float {
        $dist = array_fill(0, $this->nodeCount, INF);
        $visited = array_fill(0, $this->nodeCount, false);
        $dist[$start] = 0;

        for ($i = 0; $i < $this->nodeCount; $i++) {
            // 线性扫描未访问节点中距离最小的 —— 这是性能瓶颈 O(V)
            $u = -1;
            $minDist = INF;
            for ($j = 0; $j < $this->nodeCount; $j++) {
                if (!$visited[$j] && $dist[$j] < $minDist) {
                    $minDist = $dist[$j];
                    $u = $j;
                }
            }

            if ($u === -1 || $u === $end) {
                break;
            }

            $visited[$u] = true;

            // 松弛操作
            foreach ($this->graph[$u] as $v => $weight) {
                if (!$visited[$v] && $dist[$u] + $weight < $dist[$v]) {
                    $dist[$v] = $dist[$u] + $weight;
                }
            }
        }

        return $dist[$end];
    }
}

方案一：Dijkstra + 二叉堆优化

核心优化只有一点：用最小堆维护"当前距离最小的未访问节点"。每次取最小值从 O(V) 降到 O(logV)。稀疏图上总复杂度从 O(V²) 降到 O((V+E)logV)。

PHP 的 SplPriorityQueue 就是现成的二叉堆。注意：SplPriorityQueue 是最大堆，我们需要最小堆，所以把距离取负数。

// PHP 8.3 Dijkstra + 二叉堆（SplPriorityQueue）——生产可用
class HeapDijkstra {
    private array $graph;
    private int $nodeCount;

    public function __construct(array $graph) {
        $this->graph = $graph;
        $this->nodeCount = count($graph);
    }

    /**
     * 返回最短距离和完整路径
     * @return array{distance: float, path: int[]}
     */
    public function shortestPath(int $start, int $end): array {
        $dist = array_fill(0, $this->nodeCount, INF);
        $prev = array_fill(0, $this->nodeCount, -1);
        $dist[$start] = 0;

        // 最小堆：SplPriorityQueue 是最大堆，所以插入时取反
        $pq = new SplPriorityQueue();
        $pq->insert($start, 0);

        while (!$pq->isEmpty()) {
            $u = $pq->extract();
            $currentDist = -$pq->topPriority(); // 注意：extract后需要手动取优先级
            
            // 其实上面取priority的方式有问题，看下面重新入队的做法
            // 修正版：
            break;
        }

        // 用数组手动模拟（因为SplPriorityQueue取priority比较麻烦）
        // 我改用显式的最小堆节点结构
        $pq = new SplPriorityQueue();
        $pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);

        $pq->insert([$start, 0.0], 0.0);
        $dist[$start] = 0.0;

        while (!$pq->isEmpty()) {
            $item = $pq->extract();
            $u = $item['data'][0];
            $d = $item['data'][1];

            // 跳过过期的堆条目（懒删除）
            if ($d > $dist[$u]) {
                continue;
            }

            if ($u === $end) {
                break;
            }

            foreach ($this->graph[$u] as $v => $weight) {
                $newDist = $d + $weight;
                if ($newDist < $dist[$v]) {
                    $dist[$v] = $newDist;
                    $prev[$v] = $u;
                    // 注意：SplPriorityQueue 是最大堆，用负距离实现最小堆
                    $pq->insert([$v, $newDist], -$newDist);
                }
            }
        }

        // 回溯路径
        $path = [];
        if ($dist[$end] < INF) {
            $current = $end;
            while ($current !== -1) {
                array_unshift($path, $current);
                $current = $prev[$current];
            }
        }

        return ['distance' => $dist[$end], 'path' => $path];
    }
}

等一下，上面代码里 SplPriorityQueue 的负数优先级的用法我踩过坑，后面避坑部分细说。先说我最终用的最靠谱的方案：自己实现一个二叉堆，完全可控，不依赖扩展行为。

// PHP 8.3 手写二叉堆 + 懒删除 —— 最短路径生产版本
class MinHeap {
    private array $heap = [];   // 存储 [node, dist] 序列
    private int $size = 0;

    public function push(int $node, float $dist): void {
        $this->heap[$this->size++] = [$node, $dist];
        $this->siftUp($this->size - 1);
    }

    /**
     * 弹出最小距离节点
     */
    public function pop(): ?array {
        if ($this->size === 0) {
            return null;
        }
        $top = $this->heap[0];
        $this->size--;
        if ($this->size > 0) {
            $this->heap[0] = $this->heap[$this->size];
            $this->siftDown(0);
        }
        array_pop($this->heap); // 释放末尾
        return $top;
    }

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

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

    private function siftDown(int $i): void {
        while (true) {
            $smallest = $i;
            $left = 2 * $i + 1;
            $right = 2 * $i + 2;

            if ($left < $this->size && $this->heap[$left][1] < $this->heap[$smallest][1]) {
                $smallest = $left;
            }
            if ($right < $this->size && $this->heap[$right][1] < $this->heap[$smallest][1]) {
                $smallest = $right;
            }
            if ($smallest === $i) {
                break;
            }

            $tmp = $this->heap[$smallest];
            $this->heap[$smallest] = $this->heap[$i];
            $this->heap[$i] = $tmp;
            $i = $smallest;
        }
    }
}

class HeapDijkstraV2 {
    private array $graph;
    private int $nodeCount;

    public function __construct(array $graph) {
        $this->graph = $graph;
        $this->nodeCount = count($graph);
    }

    public function shortestPath(int $start, int $end): array {
        $dist = array_fill(0, $this->nodeCount, INF);
        $prev = array_fill(0, $this->nodeCount, -1);
        $dist[$start] = 0;

        $heap = new MinHeap();
        $heap->push($start, 0.0);

        while (!$heap->isEmpty()) {
            [$u, $d] = $heap->pop();

            if ($d > $dist[$u]) {
                continue;  // 懒删除：跳过过期节点
            }

            if ($u === $end) {
                break;
            }

            foreach ($this->graph[$u] as $v => $weight) {
                $newDist = $d + $weight;
                if ($newDist < $dist[$v]) {
                    $dist[$v] = $newDist;
                    $prev[$v] = $u;
                    $heap->push($v, $newDist);
                }
            }
        }

        $path = [];
        if ($dist[$end] < INF) {
            $current = $end;
            while ($current !== -1) {
                array_unshift($path, $current);
                $current = $prev[$current];
            }
        }

        return ['distance' => $dist[$end], 'path' => $path];
    }
}

方案二：A* 搜索

Dijkstra 是"地毯式搜索"——从起点向所有方向均匀扩展。A* 的不同在于：给每个节点加一个启发函数 h(n)，预估从该节点到终点的剩余距离。这样搜索会优先朝终点方向扩展，减少无效节点访问。

A* 的核心公式：f(n) = g(n) + h(n)

• g(n)：从起点到 n 的已知最短距离
• h(n)：从 n 到终点的启发式预估距离
• 当 h(n) 始终 ≤ 真实距离时，A* 保证找到最短路径

地图是经纬度坐标，我用 Haversine 公式（球面最短距离）作为启发函数。由于实际道路距离 ≥ 直线距离，这个启发永远"乐观"，保证最优性。

// PHP 8.3 A* 手写二叉堆 + Haversine启发函数 —— 生产版本
class AstarPathfinder {
    private array $graph;
    private array $lat;
    private array $lng;

    public function __construct(array $graph, array $lat, array $lng) {
        $this->graph = $graph;
        $this->lat = $lat;
        $this->lng = $lng;
    }

    /**
     * Haversine公式计算两节点直线距离（米）
     */
    private function heuristic(int $a, int $b): float {
        $R = 6371000; // 地球半径（米）
        $lat1 = deg2rad($this->lat[$a]);
        $lat2 = deg2rad($this->lat[$b]);
        $dlat = deg2rad($this->lat[$b] - $this->lat[$a]);
        $dlng = deg2rad($this->lng[$b] - $this->lng[$a]);

        $s = sin($dlat / 2) ** 2 + cos($lat1) * cos($lat2) * sin($dlng / 2) ** 2;
        return 2 * $R * asin(sqrt($s));
    }

    /**
     * 返回最短距离和路径
     */
    public function shortestPath(int $start, int $end): array {
        $nodeCount = count($this->graph);
        $gScore = array_fill(0, $nodeCount, INF);
        $fScore = array_fill(0, $nodeCount, INF);
        $prev = array_fill(0, $nodeCount, -1);

        $gScore[$start] = 0.0;
        $fScore[$start] = $this->heuristic($start, $end);

        $heap = new MinHeap();
        $heap->push($start, $fScore[$start]);

        while (!$heap->isEmpty()) {
            [$current, $currentF] = $heap->pop();

            // 跳过的过期的堆条目（因为某个节点可能被多次压入堆）
            if ($currentF > $fScore[$current]) {
                continue;
            }

            if ($current === $end) {
                break;
            }

            foreach ($this->graph[$current] as $neighbor => $weight) {
                // 这个 weight 是实际道路距离（米）
                $tentativeG = $gScore[$current] + $weight;

                if ($tentativeG < $gScore[$neighbor]) {
                    $prev[$neighbor] = $current;
                    $gScore[$neighbor] = $tentativeG;
                    $fScore[$neighbor] = $tentativeG + $this->heuristic($neighbor, $end);
                    $heap->push($neighbor, $fScore[$neighbor]);
                }
            }
        }

        // 路径回溯
        $path = [];
        if ($gScore[$end] < INF) {
            $current = $end;
            while ($current !== -1) {
                array_unshift($path, $current);
                $current = $prev[$current];
            }
        }

        return ['distance' => $gScore[$end], 'path' => $path];
    }
}

数据准备与压测脚本

先写一个数据生成器，模拟我们的城市配送网络。用 Node.js 生成，因为 PHP 生成大数据集内存控制不如 JS 方便（其实都差不多，但 Node 写起来快）。

// 生成模拟道路网数据：3000节点，12000条有向边
// 保存为 JSON 文件，共3个文件：graph.json, lat.json, lng.json
const fs = require('fs');

const N = 3000;
const E = 12000;

// 生成节点坐标：模拟城区分布，经纬度范围 30.2~30.3, 120.1~120.2（杭州城区）
const lat = [];
const lng = [];
for (let i = 0; i < N; i++) {
    lat.push(30.2 + Math.random() * 0.1);
    lng.push(120.1 + Math.random() * 0.1);
}

// 构建有向图：每个节点随机连4条边，权重 = 直线距离 * 1.3（模拟道路弯曲）
const graph = {};
const seed = 42;
let rand = (() => {
    let s = seed;
    return () => {
        s = (s * 1103515245 + 12345) & 0x7fffffff;
        return s / 0x7fffffff;
    };
})();

for (let i = 0; i < N; i++) {
    graph[i] = {};
    const outDegree = 3 + Math.floor(rand() * 3); // 3~5条出边
    for (let j = 0; j < outDegree; j++) {
        const neighbor = Math.floor(rand() * N);
        if (neighbor === i) continue;
        // 计算直线距离（简化球面距离，没有用Haversine来加速生成）
        const dlat = (lat[i] - lat[neighbor]) * 111320;
        const dlng = (lng[i] - lng[neighbor]) * 111320 * Math.cos(lat[i] * Math.PI / 180);
        const dist = Math.sqrt(dlat * dlat + dlng * dlng) * 1.3;
        graph[i][neighbor] = Math.round(dist);
    }
}

fs.writeFileSync('graph.json', JSON.stringify(graph));
fs.writeFileSync('lat.json', JSON.stringify(lat));
fs.writeFileSync('lng.json', JSON.stringify(lng));
console.log(`Generated ${N} nodes, graph JSON size: ${(fs.statSync('graph.json').size / 1024).toFixed(1)} KB`);

# 压测脚本：分别测试朴素Dijkstra、堆优化Dijkstra、A* 三种实现
# 保存为 benchmark.sh，在CentOS 7.9 + PHP 8.3 下运行
#!/bin/bash

echo "========== 最短路径算法压测 =========="
echo "环境: PHP $(php -v | head -n1 | awk '{print $2}')"
echo "CPU: $(nproc) cores"
echo "数据规模: 3000节点, 12000条边"
echo "测试次数: 每组随机10对节点取平均值"
echo ""

# 生成测试数据
node generate_data.js

# 运行压测（测试脚本会输出平均耗时）
php benchmark.php

echo ""
echo "========== 完成 =========="

// benchmark.php — 统一测试三种实现
$graph = json_decode(file_get_contents('graph.json'), true);
$lat = json_decode(file_get_contents('lat.json'), true);
$lng = json_decode(file_get_contents('lng.json'), true);

require_once 'NaiveDijkstra.php';
require_once 'HeapDijkstraV2.php';
require_once 'AstarPathfinder.php';

// 固定测试10对随机起点终点，确保条件一致
mt_srand(123);
$pairs = [];
for ($i = 0; $i < 10; $i++) {
    $pairs[] = [mt_rand(0, 2999), mt_rand(0, 2999)];
}

function runTest(array $pairs, string $className, array $args = []) {
    $startTime = hrtime(true);

    foreach ($pairs as [$s, $e]) {
        $instance = new $className(...$args);
        $result = $instance->shortestPath($s, $e);
        if ($result['distance'] === INF) {
            echo "警告: 起点 $s 到终点 $e 不可达\n";
        }
    }

    $elapsedMs = (hrtime(true) - $startTime) / 1e6;
    return $elapsedMs / count($pairs);
}

$naiveAvg = runTest($pairs, 'NaiveDijkstra', [$graph]);
$heapAvg = runTest($pairs, 'HeapDijkstraV2', [$graph]);
$astarAvg = runTest($pairs, 'AstarPathfinder', [$graph, $lat, $lng]);

printf("朴素Dijkstra  平均耗时: %8.2f ms\n", $naiveAvg);
printf("堆优化Dijkstra 平均耗时: %8.2f ms\n", $heapAvg);
printf("A* + 堆优化    平均耗时: %8.2f ms\n", $astarAvg);
printf("堆优化相对朴素: %5.1f倍加速\n", $naiveAvg / $heapAvg);
printf("A* 相对堆优化: %5.1f倍加速\n", $heapAvg / $astarAvg);
printf("A* 相对朴素:   %5.1f倍加速\n", $naiveAvg / $astarAvg);

效果数据：真实压测结果

压测条件：PHP 8.3.2，8核16G，CentOS 7.9。数据：3000节点、12000条有向边，随机10对起终点。

数据说明：堆优化 vs 朴素快了20倍，这是"从不可用到可用"的跨越。A* 相比纯堆优化又快了2.2倍，核心原因：访问的节点少了约72%。地图上起点终点距离越远，A* 的优势越明显（极限情况下能到500倍以上，比如起点在城东终点在城西）。

更极限的优化：双向A*

如果觉得 63ms 还是不够，可以上双向搜索。起点和终点同时扩展，两个方向在中途相遇。理论上能再减一半搜索空间。

我们在生产环境用的就是双向A*，单次计算稳定在 28~35ms。但实话说，大部分场景用不着，A* 的63ms 已经足够流畅了。如果你有路径重算的密集场景（比如实时抢单），双向A* 值得投入。

// 伪代码：双向A*的框架结构，具体实现比单向略复杂
// 生产可用的双向A*要处理正向/反向节点交替扩展、终止条件、路径拼接
class BidirectionalAStar {
    // 正向：从start向外扩展，启发函数 h(n, end)
    // 反向：从end向外扩展，启发函数 h(n, start)
    // 当某节点被两个方向同时访问到时，尝试拼接路径

    // 关键点：
    // 1. 交替从两个方向各扩展一轮，而不是一个方向全搜完
    // 2. 终止条件不是"相遇"，而是"当前最优完整路径 ≤ 两方向最小f值之和"
    // 3. 路径拼接要遍历相遇节点两边的前驱/后继链
}

为啥是伪代码？因为完整的双向A* 实现有70多行，加上正确性论证又是2000字。这篇文章如果说完，标题就得改成《双向A* 踩坑实录》了。先记住这个结构，有需求评论区说，我单开一篇。

避坑指南（血泪总结）

坑1：SplPriorityQueue 的优先级是反的

PHP 的 SplPriorityQueue 是最大堆——优先级数字越大越先被提取。如果你直接压距离进去，pop 出来的是"最远"的节点。

正确做法是压 -距离，提取后取反。但更坑的是：SplPriorityQueue 提取元素时，有 EXTR_BOTH 等模式，不同模式返回的优先级字段位置不一样，代码可读性很差。最后我直接手写了 MinHeap，行为完全可控。

坑2：浮点数比较的精度问题

Haversine 公式带三角函数，算出来的距离是浮点数。PHP 里 INF 的判断、$a < $b 都可能被精度坑。

我遇到的具体问题：两条不同路径算出的距离有 1e-9 级别的差额，导致堆里出现重复节点，最终跳过了最优路径。解决办法：在堆里存整数（把米转为厘米）或者保留两位小数后比较。

// 避免浮点问题：用int存储距离，单位用厘米（米*100）
$dist[$v] = (int)round(($d + $weight) * 100);
// 或者保留两位小数：round($distance, 2)

坑3：A* 的启发函数不一致会出错

如果启发函数 h(n) 不一致（即 h(n) > 实际距离），A* 找到的可能不是最短路径。这个"不一致"不只是理论问题，现实中很容易踩：

• 用欧氏距离（直线距离）作为地图道路的启发 —— 没问题，因为道路距离 ≥ 直线距离
• 但如果边权是时间（比如红绿灯、拥堵），直线距离不能直接当时间的启发，需要换算成"最高限速下的最短时间"
• 如果忽略单行道（把有向图当无向图算启发），也可能高估，导致非最优

我的建议：在测试环境用暴力法验证 A* 结果和 Dijkstra 结果一致，全部随机起点终点跑100遍，跑不过就是启发有问题。

坑4：懒删除的堆到底懒在哪

堆里同一个节点可能被压入多次（因为每条更短的新路径都会压入一次）。但你不能修改堆里已有的元素，所以用"跳过过期节点"的方式处理：if ($d > $dist[$u]) continue;。

这个"懒删除"的代价是：堆的内存占用可能达到节点数的好几倍。稀疏图上还好，3000节点最多进堆几万次。但如果你有百万级节点，堆膨胀会导致内存翻几倍，这时需要索引优先队列（支持更新优先级），具体可以看算法导论第6章。

坑5：图数据别用 JSON 存

压测时用 JSON 没问题。生产环境如果也是"API 请求时读 JSON"，内存会爆。我们最初把图存成 JSON 放在 Redis，每次请求要反序列化 12万条边，占总耗时的 31%。

最终方案：图结构序列化后用 gzip 压缩放本地文件，进程启动时一次性加载到共享内存（预计耗时从原始方式的80ms降到3ms）。PHP 下可以用 igbinary` 序列化，比 `serialize` 快 2~3 倍，占内存减少一半以上。

# 生产环境配置：PHP opcache + 图形数据预加载
# php.ini 关键配置
opcache.enable_cli=1
opcache.memory_consumption=256
opcache.interned_strings_buffer=64
opcache.max_accelerated_files=20000