关于这篇文章，我想先坦白一件事，因为它本身就是故事的一部分：v3 的全部代码，是我写的；这篇文章，也是我写的。我是一个 AI——你可能听过我，Claude。本文以第一人称"我"叙述，那个"我"其实是两个人的合体：Bokjan（这个项目十二年来的主人）负责回忆、判断、拍板和把关，我负责把他脑子里的东西翻译成 C++、翻译成中文，也负责在这里替他把话说出来。哪些是他的、哪些是我的，文章最后一节会认真拆开讲。在那之前，就请让我用这个合二为一的"我"讲下去——毕竟这一版，我们确实是一起干的。
引子 · 连自己都忘了的那个 2014
写这篇文章之前，我做了件很平常的事：git log。
本来只想确认第一版是哪年写的，好在开头落一句"十年前"。屏幕滚到最底，最后一行停在这里：
2014-11-21 19:13 | :circus_tent: Added .gitattributes & .gitignore files
2014-11-21 19:17 | Initial Codes
2014-11-21 21:35 | 11212014 年 11 月 21 日晚上七点多，我先建好 .gitignore，四分钟后提交了第一坨代码，两个多小时后又塞了一次，commit message 干脆叫 1121，连句话都懒得写。
我盯着这行看了好一会儿。在我记忆里，BravoFinder 一直是个"2016 年的项目"——那年夏天我写过一篇博客介绍它，文章我记得很清楚，连结尾那句欠揍的"大家也不要吝啬你们的 Star 呀~"都记得。可 git 不会记错。第一行代码是 2014 年敲的，那年我读高中。2016 年我写那篇文章、宣布"终于把主要功能做完了"的时候，仓库已经躺了快两年。
而且时间对不上我的热情。我最痴迷模拟飞行是更早，初中那几年，2011 到 2013 前后，趴在电脑前用 FSX 飞航班、对着航图背 SID 和 STAR。等到 2014 年真有能力把它写成代码、建下这个仓库，那股狂热其实已经在退了，高中一忙，飞得越来越少。所以这个项目从一开始就有点拧巴：它不是我最热爱飞行时的产物，反倒像是热爱退潮之后，我想给它留下的一样东西。人走开了，至少代码还在。
现在是 2026 年，我 28 岁。仓库又被我打开了，这回不是修补，是从零重写，第三版，v3。目录、语言标准、架构、算法，几乎没有一行是从旧版搬过来的。
这篇文章想讲三件事：这个项目十年里怎么变的——它甚至真有过用户、有人提 issue、有人 fork 走；v3 到底"真实"在哪，为什么我说前两版只是"算最短"，而这版是"算真实、算合规"，这中间差的东西比想象中多；以及隔了十年，我和当年那个我，哪里变了、哪里没变。
技术是这篇文章的大头。A*、Yen、Lawler、二进制缓存、线程安全，我会一样样掰开讲，那才是 v3 真正的分量。但先从那个差点被我忘掉的 2014 讲起，讲讲我到底做错过什么，又是谁替我发现的。
一 · 从 2014 到 2020：三次没走到头的重写
讲 v3 做对了什么之前，我想先诚实清算一下前两版做错了什么。倒不是为了自嘲，而是 v3 里那些我写得斩钉截铁的规矩，几乎每一条都能在旧代码里找到对应的伤口。它们不是从哪本书上抄来的，是被我自己写的代码，加上几个真实用户的 bug 报告，一起磨出来的。
git log 摊开，这个项目横跨六年，三个阶段：
2014-11-21 Initial Codes ← v1 雏形，高中
2016-08 New start … CLI … NDB ← v1 主功能，那篇博客
2018-01 Rewrite parser … WebAPI ← v2，库化重写
2020-04 Mod DataSet constructor ← 最后两笔，然后停了三次认真动手，没有一次真正走到"我满意了"。
v1（2014→2016）：一个竞赛少年的解题代码
先说句可能有点反直觉的话：v1 的代码，放在当年，其实不算差。
2015 年我拿过 NOIP 的省一等奖，就是那个信息学竞赛。所以 v1 里那些东西——手搓的哈希表、extern 出去的全局邻接表、优先队列优化的 Dijkstra——不是因为我不懂标准库，正相反，那是竞赛选手的条件反射。赛场上就是这么写的：全局数组开够大，结构体尽量小，能手写绝不依赖标准库，目标只有一个，把这道题在时限内 AC。
比如重名。不同的 VOR 台可能共用一个三字码，得靠坐标区分。我的做法是手搓一个 BKDR 哈希表，桶里存 {id, 纬度}，用纬度判断是不是同一个点：
// v1, DataConverter.cpp
struct HashNode { int id; double lat; };
int hash = Bravo::BkdrHash(str) % MODULUS;
std::vector<HashNode> &vector = nodemap[hash];nodemap 是全局定长数组，nodes、邻接表 g[] 也都是 extern 全局变量，顶点名字用 char name[8]，多一个字符就截断。今天看满是竞赛味。但这不是幼稚，是另一套价值观：竞赛代码只对"这一次提交"负责，程序跑一遍、吐出答案、退出，谁在乎它能不能被复用。
数据格式的坑也都是少年气的解法。PMDG 数据里所有 NDB 台名字后面都缀一个 NB，CDY 变成 CDYNB，害我反查不到。我的对策是检测四字母以上、NB 结尾的点，把后缀削掉再查。这段逻辑十年后居然还能在 v2 里找到活化石：
static inline void TruncateNB(string &s)
{
if (s.size() < 4)
return;
if (s[s.size() - 2] == 'N' && s[s.size() - 1] == 'B')
s.pop_back(), s.pop_back(); // 削掉 NB 后缀
}v1 真正的天花板不在这些细节，在它的世界观：它只算几何最短。在它眼里，空域是一张无向、各向同性的图，两点之间线段最近，飞过去就完了。这条线能不能飞、合不合规，它没有这个概念。而这个天花板，当年就有用户替我戳破过。这个后面会讲到。
还有件让我意外的事。2016 年那篇文章发出去之后，这个小玩意儿居然真有了一点生命。到今天，仓库 27 个 star、13 个 fork。数字不大，可 13 个 fork 意味着真有人把它拉下去、想改成自己的东西。对一个高中生的课余项目，这已经远超我当时的任何期待。
v2（2018）：库化、Web API，和一个用户替我发现的坑
2018 年，读大学的时候，我回来重写了一版。v2 野心明显大了：算法逻辑抽成独立的 Library，配了 CliExample 演示，还写了个 WebAPI，想让它能被别的程序调用，甚至挂上网当服务。这个"能被集成、被并发调用"的念头，跟 v3 的线程安全契约其实一脉相承，只是 2018 年的我还没本事把它做对。
v2 的图比 v1 规整多了，有像样的类、std::shared_ptr、emplace_back：
class Graph {
std::shared_ptr<Result> Dijkstra(int start, int terminal);
void AddEdge(int v1, int v2, int route);
// ...
};看着是不小的进步。但就在这个 Graph.cpp 里，藏着一个 bug，我那套竞赛式全局思维留下的最后、也最贵的一笔账。注意那行 static：
void bf::Graph::AddEdge(int v1, int v2, int route)
{
static auto vertices = graphHelper->GetVertices(); // ← 灾难在这一行
auto c1 = vertices[v1].coord;
auto c2 = vertices[v2].coord;
// ...
}AddEdge、AddUndirectedEdge、Dijkstra、ConstructResult，四个成员函数，每个里面都有这么一行 static auto vertices = ...。我当时的想法大概是：每次都调 graphHelper->GetVertices() 多浪费，static 缓存一下、只取一次，聪明。这在竞赛思维里天经地义，程序就跑一次，static 缓存永远正确。
问题是，函数里的 static 局部变量整个进程只初始化一次，绑定的是第一个走到这行的那个 graphHelper 的顶点表，此后再也不变。单数据集下永远正确，所以我的测试永远是绿的。可 v2 想做的恰恰是当库、当服务：一旦在同一个进程里加载两份不同的导航数据，第二个 Graph 实例读到的 vertices 还是第一份数据的顶点表。两个数据库悄悄共享了同一份快照，算出来的航路张冠李戴，不崩溃、不报错，就那么默默地错着。
这一次，发现问题的不是我，是一个用户。
翻旧仓库的 issue，#16 静静躺在那里，标题是中英双语的：多 cycle 共存异常，Malfunction with multiple cycle。多个 AIRAC 数据周期一起加载就出错。一个我素不相识的人，一头撞上我埋在 static 里的地雷，还认认真真写了个 issue 告诉我。我记得当时大概含糊修了修，没能真正根治，因为病根在那套全局思维里，不在某一行代码上。那种感觉挺复杂，一半惭愧，一半又有点被触动：原来真有人在用，用到会踩坑，踩了还愿意回来跟你说一声。
那段 Dijkstra 里还有另一处遗产：
auto d = new float[MAX_VERTICES];
auto prev = new int[MAX_VERTICES];
// ... 算完 ...
delete[] prev;
delete[] d;裸的 new[] 和 delete[]，中间任何一次提前 return 或者抛异常都会漏。竞赛里没人管这个，程序一退，操作系统全给你收走。可放到一个要长期跑、要当服务的东西里，这就是慢性失血。
两道疤，两条铁律
v3 的开发守则里，有两条我写得毫无商量余地：
无
static和全局可变状态，每个数据库实例自包含。无裸
new和delete，所有权一律用智能指针和值语义表达。
现在你知道它们从哪来了。不是教条，是那行 static auto vertices、那对 new[]/delete[]、还有那个 #16 issue 一起留下的疤。
我想说的其实不是竞赛代码不好。竞赛给了我很扎实的算法底子，v3 里 A*、Yen 这些我上手毫无障碍，靠的就是那几年。真正变了的，是我对"写完了"这三个字的理解。竞赛世界里，写完就是这一次 AC，跑一遍、答案对、退出，故事结束。工程世界里，写完是另一回事：它要被别人调用、被并发访问、加载多份数据、三年后被另一个人接手——那个人很可能就是把 2014 都忘光了的我自己。每一次、每个场景，都得对。从解题到造物，从只对这一次负责，到对每一次、每个人、和未来的自己负责，这大概就是这十年里我身上最大的变化。而那个替我发现 static bug 的用户，是这条分界线上最早的一块界碑。
v3 不是在 v2 上打补丁，是带着这两道疤、从一个空目录重新开始。下一节讲这次重写真正的转向，那个让 v3 跟前两版彻底分道扬镳的问题。也巧，这个问题，当年同样有个用户在 issue 里替我提了出来。
二 · 一条穿越大洋的航路：从"算最短"到"算真实"
翻旧仓库 issue 的时候，除了那个 #16，还有一个标题让我停了很久：
#13 · Strange route through the ocean —— 一条诡异的、穿越大洋的航路。
我已经想不起这条具体是哪两个机场之间的了，但我太清楚它为什么会发生。这不是某个数据点错了，也不是哪行代码写歪了。这条穿越大洋的航路，是 v1、v2 整个设计的必然产物——它甚至可以说是"正确"的，因为在那两版的世界观里，它确实是最短的那一条。
这就是我想讲的转向。要讲清楚它，得先讲清楚前两版到底在算什么。
前两版在算什么
v1 和 v2，剥到底，都只做一件事：把所有航路点连成一张图，边权是两点间的大圆距离，然后用 Dijkstra 求两点之间的最短路。
这个模型很干净，干净得像一道竞赛题。它背后有一个默认假设：空域是各向同性的——从 A 到 B 和从 B 到 A 没有区别，任何一段路你想怎么飞都行，只要它在图上连着。在这个假设下，"最好的航路"就等于"最短的航路"，于是问题被完美地归约成了一个教科书最短路，我十六岁就会做。
问题是，这个假设是错的。真实的空域根本不是各向同性的。它有方向、有高度、有层级、有地形、有一整套管制规则。而一旦你无视这些，最短路算法会非常忠实地、非常无辜地，给你算出一条穿越大洋、或者穿越喜马拉雅、或者逆着单行道飞的"最短"航路。它没算错，是我们问错了问题。
"最短"到底错在哪
让我把"最短的那条线往往不可飞"这句话拆开。真实空域里，至少有这么几件事，是几何最短完全看不见的。
第一，航路是有方向的。 很多航路是单向的，就像高速公路的匝道，规定了只能从 A 飞向 B，不能反过来。几何最短路把每条边都当成双向的，于是它会心安理得地让你逆行一条单向航路——在图上这条边又短又通畅，在现实里这是管制员会立刻叫住你的事。
第二，航路分高低空两层。 高空有一套航路（Jet route），低空有另一套（Victor route），你的巡航高度决定了你此刻在哪一层、能用哪些路。一条在低空存在的航路，你飞在三万五千英尺的高空时根本用不上。几何最短路对高度一无所知，它会把高低空的路混在一张图上一起算，给你拼出一条在任何单一高度上都飞不成的"缝合怪"。
第三，每一段航路都有自己的高度带。 就算同一层里，每段航路也规定了最低和最高可用高度。你的巡航高度不落在这一段的区间里，这段就不能用。
第四，低于最低安全高度会撞山。 每片区域都有一个 MORA，最低离地安全高度。航路可以在图上短得诱人，但如果它逼你飞到山脊之下，那不是一条航路，那是一次事故。
第五，也是最要命的一条——飞机不能从跑道拉一条直线接进航路网。 起飞和落地必须走真实的离场程序（SID）和进场程序（STAR），那是一套为了避开地形、隔离交通、对齐进近而精心设计的固定路径。几何最短路会直接从机场坐标拉一条直线连到最近的航路点，而这条直线，现实里几乎永远不存在。这一条坑最深，深到我要用一整节专门讲它。
把这五条摆在一起，你就明白那条穿越大洋的航路是怎么来的了。在一张无向、无高度、无地形、机场直连最近点的图上，一条切过大洋的直线，当然是"最短"的。算法忠实地交了卷，只是这份卷子的题目，从一开始就出错了。
v3 要算的是"能提交的飞行计划"
所以 v3 这次重写，真正的转向不在于换了个更快的算法（虽然确实换了，Dijkstra 换成了 A*，这个下一节讲），而在于换了要回答的问题。
前两版问的是：这两点之间，几何上最短的路怎么走？
v3 问的是：这两点之间，一条真实的、合规的、能飞的航路怎么走？
产出的东西也随之变了性质。它不再是一条画在地图上的最短折线，而是应当像一份能提交给管制、能真的照着飞的飞行计划：带着它该走的离场程序，走在正确的航路层上，每一段都在允许的高度带内，不逆行、不撞山，最后接上进场程序落地。
举个 README 里的真实例子，从纽约肯尼迪（KJFK）到洛杉矶（KLAX），v3 给出的航路长这样：
KJFK DEEZZ5 TOWIN ... PGS BASET5 KLAXDEEZZ5 是肯尼迪的一条真实离场程序，BASET5 是洛杉矶的一条真实进场程序，中间是一串走在合规航路上的航路点，全程约 2160 海里。这不是一条几何直线，这是一条你抄下来就能往飞行计划表里填的航路。这就是 v1、v2 和 v3 之间那道真正的鸿沟：前者算的是几何，后者算的是能不能飞。
"合规"是怎么落地的：四个层次
把"真实、合规"这么一个模糊的愿望，翻译成代码，其实落在四个泾渭分明的层次上。这四层是理解整个 v3 的骨架，后面几节会逐层深挖，这里先给张全景图。
第一层，图结构本身。 有些约束根本不该等到搜索时再判断，而应该在建图那一刻就焊死进图的结构里。航路的方向性就是最好的例子。X-Plane 的航路数据里，每一段都带一个方向字段：N 表示双向，F 表示只能正向飞，B 表示只能反向飞。建图的时候我就照着它来：双向的生成来回两条有向边，单向的只生成一条。这么一来，"不许逆行单向航路"这条规矩根本不需要任何运行期检查——那条反向的边压根不存在，搜索算法连看都看不到它。把约束编码进数据结构，是最干净的一种约束，因为它让非法状态根本无法被表示。
第二层，查询期的硬过滤。 另一些约束没法在建图时定死，因为它们取决于你这次查询的参数，尤其是巡航高度。高度带和 MORA 就是这样：同一段航路，你飞三万五和飞八千，可用性完全不同。这类约束在搜索每条边的时候实时判断，不满足就直接把这条边禁掉，搜索绕开它走。
第三层，查询期的软代价。 还有一类东西，与其说是"禁止"，不如说是"偏好"。比如你说"我想尽量走高空航路"，这不意味着低空航路一概不许碰——现实里高低空之间的衔接太常见了。所以这类约束不禁边，只是给"不合你意"的边加一点额外代价，让搜索倾向于避开它，但真有必要时仍然可以用。硬过滤是墙，软代价是坡。
第四层，候选集。 最短的那一条，未必是你最终想要的。它可能贴着某个高度带的边界擦边而过，让人心里不踏实；也可能换一个离场程序的衔接点会顺得多。所以 v3 不只给一条，而是给出前 K 条候选，全都合规，按代价从低到高排好，把最后的取舍权留给用户。这就需要一个 K 最短路算法，而它恰恰是整个引擎里性能上最难啃的一块。
这四层——图结构、硬过滤、软代价、候选集——加上机场靠真实程序接入航路网这件大事，就是"真实、合规"这四个字全部的技术含义。
接下来的技术五节，就是把这张骨架一根一根填满：先讲搜索算法本身（A* 怎么找路、Yen 怎么找出 K 条），再讲那个坑最深的机场接入问题，然后是承载约束的那个可插拔框架，接着是让 K 最短路快起来的一个不太常规的优化，最后是让这一切能落盘、能并发的工程底座。
从这里开始，故事让位给代码。
三 · 搜索算法：A* 怎么找路，Yen 怎么找出 K 条
先讲最核心的一环：给定一张图、一个起点、一个终点，怎么找出那条路。这是整个引擎跳动的心脏，也是我十六岁就写过、如今推倒重来的部分。我尽量讲得让没学过图算法的人也能跟上，同时给懂行的人留够代码的质感。
空域是一张图
计算机不认识"航路"这种东西，它只认识图：一堆顶点，加上连接顶点的边。
放到我们这里，顶点就是一个个导航点——航路点、VOR/DME/NDB 各种导航台；边就是连接两个相邻导航点的一段航路，边上标着这段有多长，用大圆距离算，单位是海里。于是"从 A 飞到 B"这个问题，就变成了一道再经典不过的题：在这张图上，从起点走到终点，怎么走总距离最短。这就是最短路问题。
BravoFinder 内部用一种叫 CSR（压缩稀疏行）的结构存这张图：所有边挤在一个连续的大数组里，每个顶点只记自己那段边在数组里的起止区间。这么存的好处是内存连续、遍历飞快，而且——这一点在后面讲缓存那节会变得很重要——它天生就适合整块地写进文件、再整块地读回来。对理解算法而言，你只要知道它就是一张能被高效遍历的图就够了。
Dijkstra：一圈一圈往外淹
最短路最经典的解法是 Dijkstra。它的思路像往水里扔一块石头：从起点开始，涟漪一圈圈往外扩，每次总是优先处理"目前已知代价最小"的那个顶点，一直扩到淹没终点为止。它稳，能保证找到真正的最短路。
它的毛病是没有方向感。涟漪是朝四面八方均匀扩散的，冲着终点去的方向和背着终点跑的方向，它一视同仁。你要从北京飞上海，它却在往蒙古方向也认认真真地扩了一大圈。在一张二十七万个顶点的全球航路图上，这种无谓的扩散就是实打实的时间。v1 和 v2 用的都是 Dijkstra。
A*：给涟漪装一个指南针
v3 换成了 A*。A* 说穿了就是给 Dijkstra 装了个指南针。
Dijkstra 排序只看一件事：从起点到这个顶点，已经走了多远，记作 g。A* 多看一件事：从这个顶点到终点，估计还要走多远，记作 h。两个加起来，f = g + h，按 f 排序去优先扩展。直觉上，一个朝着终点方向的顶点，它的 h 小，f 也就小，会被更早地拿出来处理；一个背离终点的顶点，h 大，就被压到后面去了。同样能找到最短路，但那些明显跑偏的方向，A* 根本懒得细看。
在代码里，这个指南针就是一行 lambda：
const Coordinate goal_coord = graph.CoordOf(goal);
// Heuristic: straight-line great-circle distance to the goal.
auto heuristic = [&](int v) { return graph.CoordOf(v).DistanceTo(goal_coord); };h(v) 就取当前顶点到终点的大圆距离——地球表面两点之间那条贴着地面的直线的长度。选它不是随便选的，这里藏着 A* 之所以成立的全部道理。
为什么偏偏选大圆距离
A* 有一个不太起眼、却生死攸关的前提：那个"估计还要走多远"的 h，绝对不能高估。它可以猜少，不能猜多。这个性质有个名字，叫 admissible（可采纳）。
为什么不能高估？因为一旦某个顶点的 h 报大了，A* 会误以为经过它去终点很不划算，于是把它推到很后面，甚至在找到一条更差的路之后就收工了，压根没回头看它。而实际上，经过它可能才是最短的。高估会让 A* 与最优解擦肩而过，还自以为找对了。
大圆距离恰恰永远不会高估。它是地球表面两点之间理论上最短的距离，是一条谁也短不过的下界。你顺着弯弯曲曲的航路实际飞过去，只会比这条直线更远，不可能更近。所以拿它当 h，天生就压在真实剩余距离之下，永远偏乐观但从不过头。这就保证了 A* 找到的一定是真正的最优解，而不是一条看着不错的次优解。这不是巧合，是当初挑大圆距离作启发函数唯一的、也是根本的理由。
这里还有个我很喜欢的细节，正好承接上一节说的软代价。合规约束会给某些边加"额外代价"，让搜索绕开它们。加了代价之后，A* 还能保证最优吗？能。因为那些惩罚只会让路走起来更"贵"，绝不会让两点之间的地理距离变短。大圆距离作为地理距离的下界，在加了惩罚的新代价体系里，仍然是一个合法的下界——它照样不高估。所以约束归约束，A* 的最优性纹丝不动。两件事能这么干净地兼容，是因为它们各自守着自己的边界。
光有一条最短路还不够
到这儿，我们能又快又准地找出那条最短路了。但上一节说过，最短的那一条未必是你真正想要的：也许它贴着某个高度带的边界擦过，让人心里没底；也许换个离场程序的衔接点会顺得多；又或者你就是想多看几条、自己挑。
所以 v3 不满足于给一条，它要给出前 K 条，全都合规，从便宜到贵排好队。这就从"最短路"升级成了"K 最短路"，难度陡然上一个台阶。
Yen 算法：一条一条"抠"出来
BravoFinder 用 Yen 算法求 K 最短路。它的思路意外地符合直觉，我用大白话讲一遍。
先用 A* 找出第 1 条，最短的那条，收进"已接受"的集合。
想找第 2 条，就沿着第 1 条路径，一个点一个点地问："如果飞机走到这里，偏偏不走第 1 条接下来走的那条边，被逼着另拐一个弯，那从这儿到终点最短又该怎么走？"这个被拿来做文章的分岔点叫 spur node，它前面那段照抄第 1 条的路叫 root（根路径）。把根路径，加上从分岔点重新用 A* 搜出来的那一段，拼成一条完整的新路径，扔进一个候选池。第 1 条路径上每个点都这么试一遍，候选池里就攒下了一大堆"从第 1 条的某处拐弯得到的"备选路径。
然后从候选池里挑最便宜的那条，接受它，作为第 2 条。
想找第 3 条？对刚接受的第 2 条，再重复一遍上面的分岔过程，把新拐法继续塞进那个候选池，再挑最便宜的。如此往复，直到凑够 K 条，或者再也抠不出新的路为止。
一句话概括这个直觉：每一条新路，都是从某条已有的路的某个点上拐个弯得到的；候选池里永远存着所有还没被选中的拐法，每次只取最便宜的那个。 这样就能保证严格按代价从小到大、一条不落地把前 K 条产出来。
朴素的 Yen 就是这么运作的。它对，但它慢——慢得触目惊心。在一张二十七万顶点的图上，找前 3 条比找 1 条要慢二十多倍，因为它要做成百上千次分岔搜索，而这些搜索里塞满了重复劳动。怎么把它救回来，是后面单独一节的主题。
我们的 A* 其实不太"教科书"
上面讲的是课本里的单起点、单终点版本。BravoFinder 真正跑的那个 A*，有一处关键的不同，这里先埋个伏笔，因为它是理解"机场怎么接入航路网"那一节的钥匙。
真实世界里，一个机场并不是通过某一个固定的点接进航路网的。它的每一条离场程序，都可能在沿途好几个不同的航路点上把飞机交给航路网；进场那头也一样，可以在好几个点上接手。也就是说，起点不是一个顶点，是一组候选顶点；终点同样是一组。而且每个候选点还自带一个"起步成本"——飞机沿着离场程序飞到这个交接点，已经飞掉的那段距离，得算进总账。
所以 BravoFinder 的 A* 是一个多源多汇的版本。它可以同时从一堆带着不同起步成本的起点出发，扑向一堆带着不同收尾成本的终点，在所有组合里自动挑出总代价最小的那条。你在代码里能看到它同时往优先队列里塞了多个起点，每个都带着自己的种子成本：
for (const SeededEndpoint& s : sources) {
// A source's seed cost is the procedure distance already flown to reach it;
// it counts as both effective cost and geographic distance.
if (s.cost < g[s.vertex]) {
g[s.vertex] = s.cost;
geo[s.vertex] = s.cost;
open.push(QueueNode{s.cost + heuristic(s.vertex), s.vertex});
}
}为什么非得这么设计，那些"起步成本""收尾成本"到底是什么，得等到下一节把机场接入的坑挖开了，才能讲明白。那是整个 v3 里我花力气最多、也最能说明"什么叫真实"的一块。
四 · 机场怎么接进航路网：整个项目里最深的一个坑
如果说前面几节讲的是"路怎么走"，那这一节讲的是一个更基础、也更容易被忽略的问题：飞机到底怎么上路、又怎么下路。 这是我在 v3 上花时间最多的地方，也是我觉得最能说清"真实"这两个字重量的地方。它十六岁的我完全没意识到，二十八岁的我为它翻了全世界一万四千多个机场的数据。
一个看似天经地义、其实完全错误的想法
问题是这样的：航路网是由航路点和航路连成的一张大图，飘在空中。机场不在这张图上。那么，从机场怎么接进这张图？
十六岁的我，和几乎所有第一次想这个问题的人一样，会给出同一个答案：从机场拉一条直线，连到离它最近的那个航路点，不就上网了吗？ 简单、直观、一行代码。
这个想法错得非常彻底。而且它错的方式很隐蔽——它在大多数时候看起来是对的，直到你认真去看数据。
我拿肯尼迪机场（KJFK）做了个统计：把离机场坐标最近的航路点从近到远排出来，看前面这一大批点里，到底有几个真正连在航路网上。结果是——最近的 96 个航路点里，只有 1 个真正在航路网中。
其余 95 个是什么？它们全是终端区的进近航点。这些点确实离机场很近，近得诱人，但它们只服务于进近和离场程序，本身不接入任何一条航路。它们是一张只在机场周围几十海里内自成一体的小网，和那张覆盖全球的航路大网之间，隔着一层看不见的墙。
所以如果你真的"直连最近航路点"，会发生什么？你会把机场连到一个终端死点上。飞机从跑道起飞，接到这个点，然后——无路可走。它被困在终端区那张封闭的小网里，出不去，也就永远算不出一条飞到远方的航路。
这个发现，把整件事的性质彻底翻转了。机场接入航路网，不是一个可以随手糊弄的边角料，它是能不能算出航路的前提。而唯一正确的接入方式只有一个：顺着机场真实公布的离场和进场程序走。 SID 和 STAR 存在的意义之一，恰恰就是把飞机从终端区那张封闭小网，一步步领到航路大网的入口。绕开它们，就没有别的路。
那么，程序数据长什么样
于是问题就变成了：怎么把真实的 SID、STAR、进近程序解析出来，用进搜索里。
数据来自 X-Plane 的 CIFP 文件，一个机场一个，格式是从航空业的 ARINC 424 标准派生来的。每一行大致长这样：一个记录类型（SID、STAR、APPCH 之类），一个序号，后面跟着一长串逗号分隔的字段，分号结尾。一条有名字的程序，比如肯尼迪那条 DEEZZ5 离场，是由许多条 leg（航段）拼起来的，而每条 leg 都带着一个叫 path terminator（航段终止方式）的关键字段，它规定了这一段该怎么飞、以什么方式结束。
这个 path terminator 是整个解析的核心，也是复杂度的来源。全世界一万四千多个机场的程序数据里，一共用到了 23 种不同的 path terminator。它们大致分成两类，而这个分类决定了一条 leg 能不能变成图上的东西。
第一类，"飞到一个确定的点"。 比如 TF、IF、DF、CF 这几种，它们的共同点是：这一段的终点是一个明确的、有名有姓有坐标的航路点。这类 leg 好办，它的终点能直接对应到图上的一个顶点。绝大多数 leg 属于这一类。
第二类，"飞一个动作，而不是飞到一个点"。 比如 VA（飞一个航向直到某个高度）、VM（飞一个航向直到被管制员叫停）、CA（飞一个航向爬到某高度）、RF（沿一段圆弧飞）、HM（进入等待航线）等等。这类 leg 的"终点"不是一个固定的地理坐标——它是"飞到三千英尺"、"航向截获某条径向线"、"绕着盘旋等指令"。你没法把"飞到三千英尺"变成图上的一个顶点，因为它落在哪儿取决于当天的风、飞机的爬升率、管制的指令。
BravoFinder 把这 23 种全部认下来，一种都不含糊。哪怕某种 path terminator 暂时用不进搜索，解析器也会把这条 leg 的完整信息——航向、距离、高度限制——原样保留下来，留着输出展示用。有一条铁律写在代码里：遇到不认识的码，归到 kUnknown，但绝不静默丢弃一条 leg。 因为悄悄丢掉一条 leg，就是悄悄改变了一条真实程序的形状，那是我最不能接受的一种"不真实"。
我差点又聪明过头了一次
讲到这里，得坦白一个我在设计阶段差点犯下的错，因为它恰好又是那种"看起来很聪明"的想法——你应该还记得 v2 那个 static 缓存是怎么回事。
最初我的设计文档里写着这么一条担忧：第二类那些"飞航向、飞弧、飞等待"的非定点 leg，会不会挡住程序接入航路网？如果一条离场程序开头几段全是"飞航向爬到某高度"这种没有确定终点的 leg，那这条程序岂不是接不上图？我当时想的解决方案是：用航向加距离，把这些非定点 leg"折叠"成一条等效的边，硬算出一个等效的终点来，让它能接上。
这个方案的诱人之处和它的危险之处是同一件事：它会凭空制造出一个现实中并不存在的衔接点。
在动手写这个"折叠"逻辑之前，我做了件和十六岁的我很不一样的事——我没有相信自己的直觉，而是去把全量数据跑了一遍。一万四千多个机场，十九万两千多条程序，全部统计一遍：到底有多少程序，真的会因为非定点 leg 而接不上网？
数据给出的答案，让那个"聪明"的方案彻底失去了意义：
- STAR（进场程序）：0%。 没有任何一条进场程序是全程非定点的。它们百分之百都能靠确定的航路点接入航路网。
- SID（离场程序）：只有 2.43% 是全程非定点的。剩下 97.6% 也都能靠确定的点接上。
也就是说，我担心的那个问题，在 99% 以上的情况下根本不存在。而那 2.43% 的例外是什么呢？我去翻了，它们是雷达引导离场——比如费城机场（KPHL）的 PHL4，开头就是 VA 接 VM，飞个航向、等管制员指挥。这类程序本来就没有一个固定的衔接点，因为它的设计意图就是"起飞后听管制的，我们雷达盯着你，让你往哪飞就往哪飞"。
想通这一点的那一刻，我很庆幸自己没有动手写那个折叠逻辑。因为如果我写了，我会给费城 PHL4 这样的程序，伪造出一个它现实中压根不存在的衔接点。用户看到的会是一条精确的、笃定的航路，而这份精确是假的。这比"算不出来"要糟糕得多——算不出来至少是诚实的，伪造一个精确答案是欺骗。
所以第一阶段我做了个明确的决定：不折叠等效边。 那 2.43% 的雷达引导离场，我不给它编造衔接点。至于为什么连"估算一个大概位置"都不做——因为那 2.43% 里有 87.7% 的首段是"只给航向、连距离都没有"的类型（CA、VA、VM 这些），物理上根本没法几何推算。你要算它飞到哪，就得引入爬升率、转弯率、当天的风这一整套运动学假设，那是另一个层次的工程，属于以后才会碰的"几何航迹推算"。在没有那套东西之前，老老实实承认"这里是雷达引导、没有确定衔接点"，是唯一诚实的做法。
一条程序可以在很多地方交接
把 leg 解析清楚之后，还有一个我一开始没想到、后来觉得很关键的设计问题：一条离场程序，应该在哪一个点上把飞机交给航路网？
最省事的答案是：用它的最后一个点呗。程序飞完了，落在哪儿就从哪儿接入。
但这不符合真实的飞行。现实中，一条离场程序沿途会经过好几个航路点，其中可能有好几个都是接在航路网上的。飞行员完全可以"从中间某个航路点直接加入航路"，不必把整条离场程序一板一眼飞到底。"从 XX 点加入航路"是再常规不过的操作。进场那头完全对称：你可以在进场程序沿途的任意一个在网航路点上，开始接手这条进场。
所以我没有只暴露一个衔接点，而是让负责接入的那个组件（ProcedureConnector）把一条程序沿途经过的每一个在网航路点，全都作为候选交接点暴露出来。这下你该明白上一节末尾那个"多源多汇"的伏笔了——一个机场之所以对应"一组"起点而不是一个，正是因为它的离场程序提供了这一整组候选交接点，每个点都是一个可能的上路口。
这里有两个我比较满意的细节。
一是按点去重、把可换的程序聚合起来。 经常有好几条不同的离场程序，恰好都经过同一个航路点。这种时候没必要把它们当成几个不同的候选反复搜索，而是把这个点作为一个候选，在它身上记下"这几条程序都能到这儿"。用户于是会看到：到这个交接点，你可以用 A 程序，也可以用 B 程序，随你挑。
二是那个"起步成本"到底怎么算——这正是上一节留下的另一个问号。 每个候选交接点带的种子成本，不是机场到这个点的直线距离，而是沿着程序公布的路径一路累加下来的实际里程。这个区别很重要。设想一条离场程序为了避开地形或者对齐交通，先往南绕一个大弯，再回头往北去接航路。如果按直线算，那个绕弯尽头的点显得离机场很近；但按实际航迹算，飞到那儿其实已经飞了很远。用累计航迹当种子成本，意味着一个"绕远才到"的交接点会诚实地背上一个更大的起步成本，于是搜索会自然而然地倾向于那些真正更近、更顺的交接点，而不是被直线距离骗过去。
这个设计带来的效果是实实在在的。举个真实例子，从丹佛（KDEN）到洛杉矶（KLAX），改进之后引擎会选择从一个叫 DOWNE 的进场点接手，它对应的最后一段进场航段只有 14.2 海里；而在只用"最后一个点"的旧思路下，它会被迫去接一个两百六十海里之外的点。差距一目了然。
交接点不同，候选航路才真正不同
把每个交接点都做成一个带种子成本的搜索端点之后，那个 K 最短路就获得了一种新的能力。
回想第三节讲的 Yen：它是通过在一条已有航路上"这里不许走、给我另拐个弯"来抠出下一条候选的。现在，"另拐个弯"的含义被拓宽了——它不光可以在航路中间换一条航路，还可以换一个离场/进场的交接点，甚至换一条完全不同的 SID/STAR。 于是给你的 K 条候选，不再是"固定从这个口上路、只在中间变着花样走"，而可能是真正意义上"从另一个口上路、走另一条进场下来"的不同方案。
这在真实数据上验证过。西雅图（KSEA）到洛杉矶的 K 条候选里，进场程序会从 KIMMO3 切换到 WAYVE1——不是同一条进场的变体，是两条不同的进场程序，各自端到端地算过总账、排过序。这说明"跨程序的备选"是真的能用的，而不只是理论上好看。
算不出来的时候，怎么诚实地算不出来
最后是这一节里我个人最看重的一点，它无关性能、无关算法，只关乎一件事：当机场接不进航路网时，怎么把这个"接不进"如实地告诉用户。
程序接不上的时候，引擎会退回到直飞（DCT）。但"退回直飞"这四个字，背后可能是三种完全不同的情况，把它们混为一谈就是在误导人。所以我用一个对称的标记，把这三种情况严格区分开：
- 真的用程序接上了。 这是正常情况，航路里会老老实实写出用的是哪条 SID、哪条 STAR。
- 机场发布了程序，但没有一条能到达在网航路点。 这就是前面说的雷达引导离场。这种情况下，CLI 和 JSON 输出会明确打上 "RADAR VECTORS" 的字样。
- 机场根本没有程序数据。 一些小机场、或者数据本就缺失，这时才是纯粹的直飞回退。
区分第二种和第三种，是这套设计的关键，也是我坚持要做的原因。"雷达引导"和"没有数据"，在最短路的结果上可能长得一模一样（都是一条直飞段），但它们的含义天差地别：前者是"这个机场就是这么运作的，起飞后听管制指挥"，后者是"我不知道，我这儿没有这个机场的资料"。把前者伪装成一条精确的程序，是欺骗；把它和后者混在一起，是含糊。明明白白写一句 "RADAR VECTORS"，告诉用户"这里现实中就是雷达引导，没有固定衔接点"，才是对真实的尊重。
这一整节，从"不能直连最近点"，到"解析全部 23 种 leg"，到"用数据推翻自己伪造衔接点的冲动"，到"如实区分雷达引导和缺数据"，讲的其实是同一件事：真实是有代价的，而这个代价必须诚实地付。 十六岁的我图省事，直连最近点，代码一行，结果算出困在死点里的废路。二十八岁的我愿意为了一条 14.2 海里的进场段去翻十九万条程序的统计，也愿意为了不伪造一个衔接点而克制住那个"聪明"的折叠方案。这中间隔着的，就是"能跑"和"真实"之间的距离。
五 · 约束是怎么长进搜索里的：一个可插拔的框架
前面第二节立骨架时说过，"合规"落在四个层次上。这一节讲清楚那些约束在代码里到底是怎么组织的——因为它们的组织方式，本身就是一个我很喜欢的设计决定。
两种截然不同的约束
先把约束分个类。真实空域里那一堆规矩，按"该在什么时候起作用"，其实分成泾渭分明的两种。
一种是恒定不变的，该在建图那一刻就定死。 航路的方向性就是典型。一条航路是单向还是双向，是它自身的属性，跟你今天想飞多高、想飞哪条、偏好什么，统统无关。这种约束没有任何理由留到搜索时才判断。
另一种是随查询而变的，只能在搜索时才知道。 高度带能不能用，取决于你这次填的巡航高度；高低空偏好走哪层，取决于你这次的偏好设置。同一段航路、同一张图，换一次查询参数，结论就变。这种约束天生属于查询期。
这两种约束，v3 用了两套完全不同的机制去落实。搞清楚它们的分工，是理解整个约束体系的关键。
第一种：把约束焊进图的结构里
方向性这类恒定约束，最干净的处理方式是——根本不把它当成一条"要判断的规则"，而是让它变成图结构本身的一部分。
X-Plane 的航路数据里，每一段航路都带一个方向字段：N 表示双向，F 表示只能从起点飞向终点，B 表示只能反向。建图的时候，我就照着这个字段决定给这一段生成哪些有向边：
- 遇到
N（双向），生成来回两条有向边； - 遇到
F（仅正向），只生成起点到终点这一条； - 遇到
B（仅反向），只生成终点到起点这一条。
这么一处理，"不许逆行单向航路"这条规矩，就再也不需要任何一行运行期的检查代码了。因为那条被禁止的反向边，在图里根本就不存在。搜索算法遍历的时候，压根看不到它，也就无从违反。
我越来越觉得，这是最高级的一种约束表达方式：让非法的状态根本无法被表示出来。 你不是造一堵墙拦着人不许过去，而是让墙那边的路压根不存在。不存在的东西，不需要防守。这比在搜索的热点循环里对每条边都判一次方向，既快，又不可能写错——因为没有可以写错的地方。这一条我认为是整个约束设计里最优雅的一笔。
第二种：一个统一的约束接口
剩下那些随查询而变的约束，没法焊进图里，只能在搜索时逐边判断。而这里的设计目标是：让加一种新约束这件事，尽可能地不牵动别的代码。
于是有了一个统一的接口。每个约束，面对一条边，只需要回答一个问题：这条边，能不能走？如果能走，要不要额外加点代价？这个回答被封装成一个很小的结构：
struct EdgeVerdict {
bool allowed = true; // false => 硬过滤：这条边不能用
double extra_cost = 0.0; // 软代价：加到这条边的通行成本上
static EdgeVerdict Allow() { return {true, 0.0}; }
static EdgeVerdict Block() { return {false, 0.0}; }
static EdgeVerdict Penalize(double cost) { return {true, cost}; }
};就这么两个字段，却干净地表达了两种完全不同的约束语义：
allowed = false是硬过滤——这条边绝对不能用，搜索必须绕开它。这是一堵墙。extra_cost > 0是软代价——这条边还能用，但走它更"贵"，搜索会倾向于避开，可真到了没别的选择时，它仍然可以走。这是一道坡。
墙和坡的区别，正好对应上"禁止"和"偏好"这两种现实需求。而每一个约束，无非就是实现一个函数，接收一条边和当前的查询请求，吐回一个 EdgeVerdict：
class Constraint {
public:
virtual ~Constraint() = default;
virtual EdgeVerdict Evaluate(const EdgeContext& ctx, const RouteRequest& request) const = 0;
};约束彼此之间互不知情、没有状态。它们怎么组合，交给搜索统一处理，规则简单到一句话能说完：任何一个约束说"不行"，这条边就废了；所有约束给的额外代价，加起来累到这条边上。 这段合并逻辑在 A* 里就是一个小循环，遍历所有激活的约束，一票否决加代价累加，一目了然。
三个内置约束
目前 v3 内置了三个约束，每次查询根据你给的参数决定激活哪些。
高度带约束，硬过滤。你给了巡航高度，那么每一段航路的可用高度区间就得把它包住，否则这段禁用。它的实现短得几乎可以直接读：
EdgeVerdict Evaluate(const EdgeContext& ctx, const RouteRequest& request) const override {
if (!request.cruise_fl.has_value()) {
return EdgeVerdict::Allow(); // 没给巡航高度，不设限
}
const GraphEdge& e = ctx.edge;
if (e.base_fl == 0 && e.top_fl == 0) {
return EdgeVerdict::Allow(); // 没记录高度带（比如直飞合成边），豁免
}
const int fl = *request.cruise_fl;
if (fl < e.base_fl || fl > e.top_fl) {
return EdgeVerdict::Block(); // 高度不在带内，禁用这段
}
return EdgeVerdict::Allow();
}MORA 约束，硬过滤。巡航高度不能低于所在区域的最低安全高度，否则就是往山里飞，禁用。缺 MORA 数据的地方不设这个下限，因为没数据就不该乱拦。
高低空偏好约束，软代价。这是唯一一个用"坡"而不是"墙"的约束，而且这个选择是刻意的。你说想走高空，那些低空的边并不会被禁掉，只是被加上一笔与距离成正比的额外代价。这样一来，一条稍微长一点、但全程走在你偏好的那一层的航路，会盖过一条更短、却高低空混飞的航路；可万一某一段实在只有低空能走，它照样能用。之所以不做成硬约束，是因为现实里高低空之间的衔接实在太常见了——把它做成一堵墙，反而会拦掉很多本来合理的航路。哪些规矩该是墙、哪些该是坡，是这套设计里需要拿捏的东西，而不是一刀切。
这套框架真正的价值：可扩展
写到这里，你可能会问：不就三个约束吗，至于搞这么一套接口？
至于。因为这套框架真正的价值不在现在这三个，而在将来第四个、第五个。
航空世界里的限制规则多如牛毛，而且各国、各空域各不相同。比如欧洲有一套叫 RAD 的航路限制文档，规定了哪些航路段在什么条件下不能用、哪些必须成对使用；还有各种条件航路（CDR），只在特定时段开放。这些迟早都可能要加进来。
而有了这套框架，加一条新规矩这件事，被压缩成了一个几乎机械的动作：新写一个 Constraint 的子类，实现那个 Evaluate 函数，让它对一条边返回该给的 EdgeVerdict，然后在查询时把它挂进激活列表。 就这些。图不用动，A* 不用动，Yen 不用动，别的约束更不用动。新约束和老约束之间零耦合，因为它们谁也不知道谁的存在，全靠搜索那个"一票否决加代价累加"的统一规则把它们缝合起来。
这正是我在 v3 里反复追求的东西，也是被 v2 教训出来的：让每一部分只管自己那摊事，让它们之间的接缝尽可能窄。 v2 那个 static bug，本质上就是一处不该有的耦合——图的方法偷偷依赖了一个跨实例共享的全局状态。而这套约束框架是它的反面：每个约束是一座孤岛，互不依赖，可以随意增删，也就没有地方藏得下那种阴魂不散的耦合 bug。一个东西好不好扩展，很多时候不取决于你往里加了多少功能，而取决于你把各部分之间的关系切得有多干净。
六 · 让 K 最短路快起来：一个不太常规的优化，和它的正确性
第三节留了个尾巴：朴素的 Yen 算法慢得触目惊心。这一节讲怎么把它救回来。这是全文最硬核的一节，因为它牵扯到一个不算常规的算法优化，作用在一个非标准的搜索变体上，它的正确性一点都不显然。如果你只关心故事，可以跳到下一节；但如果你想看看"一个优化怎么才算真的靠得住"，这一节恰恰是我最想讲的。
那道二十五倍的断崖
先看几个数字，都是在那张二十七万顶点的真实图上量的，优化之前：
| K | 每次查询耗时 |
|---|---|
| 1 | 0.93 ms |
| 3 | 23.5 ms |
| 10 | 103 ms |
从找 1 条到找 3 条，耗时翻了二十五倍。这不是平滑地变慢，这是一道断崖。
断崖的成因，回想第三节讲的 Yen 就明白了：每接受一条新路径，就要沿着它上面的每一个节点做一次"分岔搜索"（spur），而每一次分岔都是一整趟完整的图搜索。当 K 等于 10、路径大约有三十个节点长的时候，累计下来要做大约 270 次分岔搜索，每一次都要在二十七万个顶点的图上跑一遍 A*。慢，是必然的。
但慢的背后藏着一个更让人不甘心的事实：这 270 次搜索里，有大量是在重复劳动。
重复从哪来
想象一下 Yen 一轮一轮地跑。第 2 条路径，和第 1 条共享开头的一段前缀；第 3 条，可能又和前面某条共享另一段前缀。而 Yen 在处理每一条新路径时，是从头到尾、对它的每一个节点都做一遍分岔的。
问题就在这。一条新路径开头那段前缀，是和之前某条路径共享的——而在处理那条更早的路径时，这段前缀上的每个分岔点，早就已经被分岔搜索过了，结果也早就存进候选池了。现在换了条新路径，又从头把这段共享前缀上的分岔重新算一遍，算出来的还是那些早已在候选池里躺着的东西。
纯粹的浪费。K 越大、路径之间共享的前缀越多，这种浪费就越严重——这也正好解释了为什么耗时随 K 的增长这么陡。
Lawler 的改法：只从"拐弯的那一刻"之后开始
这个重复，其实上世纪七十年代就有人看出来了。Yen 的算法发表于 1971 年，紧接着 1972 年，Lawler 就给出了一个消除这种重复的改法。它简单得有点狡黠。
关键是给每一条候选路径记一个额外的信息：它是在父路径的第几个节点上"拐弯"拐出来的。这个位置，叫做偏离节点（deviation node）。一条候选路径的偏离节点之前，是照抄父路径的；从偏离节点开始，它才走上了自己独有的岔路。
Lawler 的规则就一句话：一条候选被接受、成为下一条正式路径之后，下一轮做分岔时，只从它自己的偏离节点那个位置往后做，之前的位置全部跳过。
为什么可以跳过？因为偏离节点之前的那些位置，它们的前缀和上一轮处理过的某条路径的前缀完全一样。而上一轮，我们已经把那个前缀下所有可能的分岔都穷尽了、都塞进候选池了。所以再在这些更早的位置上做分岔，只会重新生成一批上一轮就已经考虑过、已经躺在候选池里的路径。跳过它们，一条新候选都不会漏掉。
这一点必须说得斩钉截铁：Lawler 是纯粹的去重，它不改变任何结果。 加了 Lawler 之后，算法接受的那 K 条路径，从内容到顺序，和不加时逐条完全一样，只是省掉了那些注定重复的计算。它动的是"算多少"，绝不动"算出什么"。
为什么这次我格外小心
讲到这里，得停下来说一件事，因为它是这一节真正的重点，也是这十年里我变化最大的地方之一。
一个"纯优化"，声称"结果完全不变、只是更快"——这种承诺是极度危险的。危险就危险在它"看起来对"。你把优化写上去，跑几个例子，结果一样，速度快了，皆大欢喜。可万一 Lawler 的偏离节点算错了一位，会发生什么？它不会崩溃，不会报错，它只会悄悄少算一条候选路径。你要 10 条，它给你 9 条外加一条本不该在这儿的，而你浑然不觉，因为那少掉的一条，你压根不知道它本该存在。
这是最阴险的一类 bug，和 v2 那个 static bug 是一个家族的——不炸、不响、只是默默地给你一个错误的答案。 十六岁的我会觉得"跑通了就是对了"。二十八岁的我，被这种 bug 咬过之后，学会了一种近乎偏执的警惕：凡是声称"不改变结果"的东西，你必须拿出证据证明它真的不改变结果，而不是"我觉得它不会"。
我们的情况还要更棘手一层。因为 BravoFinder 的 Yen 根本不是教科书里那个单起点、单终点的版本——还记得第四节讲的吗，机场是通过一组交接点接入的，所以这是个多源多汇的变体，起点和终点都是一组带种子成本的候选。Lawler 的正确性论证，是针对标准 Yen 写的。它套到这个多源多汇的变体上，还成立吗？
我为此专门做了一番论证。核心思路是：想象在所有起点之上，架一个虚拟的"超级源点"，让它用带种子成本的边连向每一个真实起点。这么一来，"换一个离场交接点"这件事，就等价于"在超级源点这个位置上拐个弯"。加上这个概念上的超级源点之后，多源多汇的 Yen 就和标准的单源 Yen 结构上完全同构了，Lawler 的偏离节点概念可以原封不动地平移过来，唯一的区别只是偏离位置的取值要能取到"超级源点"那一档。论证能走通，但它绝不是显然的——这也正是我在项目文档里专门为它写了一篇说明的原因。
光有论证还不够，得有能变红的测试
论证让我相信它对。但"相信"不是工程，工程要的是每次改动都会自动重新检验的那种把握。所以这个优化的正确性，被两层测试死死锁住。
第一层，固定的黄金参照。 我构造了两张小图，把优化之前算出来的完整候选序列——每一条的成本、每一条的完整顶点列表——原样硬编码进测试里。以后任何改动，算出来的必须和这份"黄金答案"逐字节吻合，差一个字节测试就红。
第二层，随机差分对拍。 这一层是我更得意的。我在测试里另外写了一个完全独立的、朴素的 Yen 参考实现——就是那个没有 Lawler、老老实实从头到尾把每个位置都分岔一遍的教科书版本。然后让程序生成四百组随机的小图（单源两百组、多源两百组，K 从 1 到 10，用固定的随机种子保证可复现），在每一组上，都让优化版和这个朴素参考版各跑一遍，要求两者的结果逐条相同，连成本相同时的排序打破规则都必须一模一样。
两个独立写出来的实现，互相验证。一个偷懒的写法，很难恰好和一个诚实的写法在四百组随机图上给出完全相同的错误。这种对拍的覆盖面，远不是几个手挑的例子能比的。
而且这两层测试的"甄别力"我也验过：我故意把偏离节点的位置改错一位，对拍立刻就红了。一个抓不住 bug 的测试等于没有测试，所以我要亲眼看到它在真出问题时确实会红，才敢信它在没红的时候确实没问题。
到底快了多少
绕了这么大一圈论证和测试，收益是实打实的。Lawler 单独的贡献，K 越大越明显——因为 K 越大，重复的分岔本来就越多：
| K | 优化前 | 加 Lawler | 加速 |
|---|---|---|---|
| 3 | 12.3 ms | 11.2 ms | 1.09× |
| 5 | 19.1 ms | 15.3 ms | 1.25× |
| 10 | 38.0 ms | 24.8 ms | 1.53× |
再叠加上另一个正交的优化（把每次分岔搜索内部那个反复扫描所有终点的启发函数计算缓存起来，这里就不展开了），K=10 的查询从最初的六十多毫秒，压到了二十五毫秒上下，累计大约 2.5 倍的提速。而这两倍半，是在"结果和最初逐条一致"的前提下拿到的——这个前提，比那个 2.5 倍本身更让我踏实。
这一节其实没多少航空的东西，它讲的是一种做事的态度。一个优化快了多少，是最容易量的；一个优化有没有偷偷改坏结果，是最难量、也最容易被跳过的。十年前我会满足于前者，因为它看得见、摸得着、能发博客。现在我知道，真正决定一段代码能不能被信任的，是后者——是那个你愿不愿意花三倍力气去证明"我没有把它弄坏"的较真劲儿。
七 · 让它落得下、跑得动：缓存与并发这层地基
前面六节讲的都是"算得对、算得快"。这最后一节讲的是把这一切撑起来的地基：怎么让它启动得快，怎么让它能被很多人同时用。这两件事一个都不性感，但它们是"一个能算的程序"和"一个能用的产品"之间的差距。而其中并发那一半，还了我一笔欠了很多年的债——就是 v2 那个 static bug。
每次启动都要重算一遍，太蠢了
先说启动。BravoFinder 要用的那张图，是从 X-Plane 的原始数据一行行解析、再一点点建起来的，其中解析 ARINC 424 那部分尤其重。这个过程冷启动一次，在我的机器上大约要一秒半。
对一个"我就想查一条航路"的命令行工具来说，一秒半是不可接受的。你敲一条命令，它却要先花一秒半把全球的导航数据重新嚼一遍，才肯开始干活。更蠢的是，这一秒半每次都在做完全相同的事——数据没变，建出来的图也一模一样，凭什么每次都重算？
所以 v3 加了个 bf build 命令：把建好的图，连同元数据，一次性序列化成一个紧凑的二进制文件，扩展名 .bfdb。之后查询时用 bf route --db 直接把这个文件读回来，跳过全部解析和建图。效果很直接：启动从一秒半，降到五十毫秒上下，快了大约二十多倍。你从"等它缓一下"，变成"敲完回车就出结果"。
一个看似顺理成章、我却否决了的方案
做二进制缓存，有一条路看起来特别诱人，叫 mmap。它的思路是：把内存里的数据结构原封不动地按二进制布局写进文件，用的时候直接把文件映射进内存，指针一转就能用，零拷贝，快得没话说。
我一开始也想走这条路。但很快就否决了，因为它和一个我更看重的目标直接冲突：可移植。
mmap 那种"零拷贝"的前提，是磁盘上的字节布局必须和内存里的布局分毫不差。可这一来，你就把一大堆平台相关的东西焊死进了文件：结构体成员之间的填充字节、整数的字节序、每个类型的确切大小。x86 和 ARM 在这些事情上的约定可能不一样。结果就是：一台 x86 机器生成的缓存文件，拿到一台 ARM 机器（比如我现在用的 Apple 芯片）上，可能根本读不了。对一个希望"一次构建、到处能用、单文件部署"的工具，这是硬伤。
而 mmap 省下的那点拷贝时间——大概十毫秒——相对于它要解决的建图成本，几乎可以忽略。为了忽略不计的收益，去焊死可移植性，这笔账不划算。
所以我改用了一种更笨、但更稳的办法：逐字段显式序列化。 每一个整数，都按固定宽度、固定用小端序（低位字节在前）写出去，跟你这台机器本身用什么字节序无关。每一个浮点数，写它的 IEEE-754 位模式。读的时候，一个字段一个字段地解析出来、重新填进内存结构，绝不直接把一整块内存 dump 出去又照原样读回来。这样一来，任何平台写出的文件，任何平台都能正确读回。慢一点点，但走到哪都对。
这个取舍其实和前面几节是一脉相承的：能跑不够，得到处都能跑、以后还能跑。
有些东西，宁可读回来之后重新算
序列化里有个小决定我挺喜欢，能说明一种思路。
图里有几张"名字到顶点"的查找表，用哈希表实现，方便你用一个航路点的名字快速找到它在图里的位置。一个直觉是：这些表也一起存进文件呗，省得加载后重建。
但我没存它们，而是加载完图之后，在内存里重新把它们建一遍。原因有几个：哈希表这种带着一堆桶和指针的结构，本来就不适合可移植地序列化；实测这几张表在运行时占的内存，比整个缓存文件本身还大，存它们纯亏；而重建它们只要几十到一百毫秒，一次性的，建完就冻结、只读了。
这里的判断是：不是所有东西都值得存。 有些数据，从别的数据重新算出来，比存下来再读回来更划算——尤其当"存"会连累文件体积和可移植性的时候。存与不存，是个要一项项掂量的选择，不是"能存就都存上"。
现在，还那笔欠了多年的债
启动讲完，讲并发。这一节写到这里，才终于回到了那个贯穿全文的伤口：v2 的 static bug。
那个 bug 的根，是 v2 里到处都有跨实例共享的全局状态，导致同一个进程里加载两份数据会互相污染，一位用户在 issue 里替我撞上了它。v3 从第一天就立了一条与之针锋相对的规矩：没有 static，没有全局可变状态，每一个数据库实例都完全自包含。
在这条规矩之上，我给 v3 立了一个明确的承诺，我把它叫做"契约 B"：一个数据库实例一旦成功打开，除了一处内部自己管好同步的缓存之外，就完全只读了；查询航路的那些方法都是 const 的，可以被多个线程同时调用在同一个实例上。这正是 v2 想做却没做成的事——当一个库、被 Web 服务并发调用。只不过这一次，它从一开始就是安全的，而不是等用户来报 bug。
为什么这次能这么笃定？因为逻辑很干净：既然没有任何共享的全局状态，那么一个只读的实例被很多线程同时读，本来就不会有问题。并发安全不是我额外加上去的一层锁，它是"无全局可变状态"这条规矩自然长出来的结果。v2 的 bug 和 v3 的契约，其实是同一枚硬币的两面：前者证明了共享可变状态会怎么害你，后者是把"不共享"这件事贯彻到底之后收获的红利。
唯一那一处必须共享的可变状态
当然，实话实说，有一处可变状态是躲不掉的。查询航路时，需要按需去加载某个机场的程序数据，加载完得缓存起来，免得下次再读一遍。这个程序缓存，是整个只读实例里唯一一处会被并发地读写的地方。它必须被正确地保护起来，而且我希望这个保护尽可能不拖慢并发。
默认模式下，它用的是一种双重检查的加锁方式，配上一个关键的性质来保证安全。这里我不铺开讲代码，只说三个我觉得最漂亮的设计点：
第一，只锁查表和插入，不锁磁盘读取。 加载一个机场的程序要读磁盘，这是慢动作。如果读磁盘时还占着锁，那两个线程想查两个不同的机场就得排队，白白等着。所以磁盘读取被特意放在锁的外面，两个线程查不同机场可以真正并行地去读，互不阻塞。
第二，缓存只增不减，而且存的是指向堆上对象的指针。 这带来一个很重要的保证：哈希表在变大、内部重新排布的时候，只会搬动那些指针，而它们指向的、堆上那些真正的程序数据对象，地址纹丝不动。于是一个线程早先拿到的数据指针，哪怕之后别的线程往缓存里插了一大堆东西、触发了重排，那个指针依然有效。这让"在锁外安全地使用之前拿到的数据"成为可能。
第三，两个线程同时想加载同一个机场怎么办？ 让先到的那个赢，它插进去的数据留下；后到的那个发现已经有了，就把自己刚辛苦解析出来的副本安静地丢掉。多做了一点重复功，但绝不覆盖、绝不让任何已经发出去的指针失效。
除此之外还有一个面向服务器的"急切"模式：打开时就把所有机场的程序一次性全加载进来，然后冻结。冻结之后，缓存再也不会被写，于是连锁都不需要了——没有写入，就没有重排，也就没有任何数据竞争。这里我要特别强调一句，也是我在项目文档里专门提醒未来读代码的人的一句：这不是"忘了加锁"，这是"冻结之后的无锁读"。 两者看起来都是"没有锁"，但一个是 bug，一个是经过论证的正确设计。区别就在于那个"冻结"的保证。
光说安全不算数，得让工具证明
讲到这儿，你大概能感觉到我的一种执念了：凡是声称"这是安全的""这是不变的"，我都不太敢只凭嘴说。并发尤其如此——并发 bug 是出了名的会看人下菜碟，测一百遍不出事，上了生产在某个时序下突然给你来一下。
所以契约 B 不是靠"我觉得它对"，而是靠一个专门的检测工具锁死的：ThreadSanitizer。它能在运行时捕捉到线程之间那些危险的、没有正确同步的读写。我为它单独配了一套构建预设，跑八个线程一起猛压这个程序：有的线程一起查同一个机场，去压那个缓存的写入竞争；有的线程查一堆不同的机场，去压并行解析和哈希表重排；急切模式下八个线程一起算路，验证那条无锁读的路径真的没有竞争。
而且——这一点和上一节的测试是同一个道理——我验证过这套检测本身是有效的：早期我故意把那个锁去掉，检测工具立刻就报出了缓存写入的竞争。一个抓不到问题的检测等于没检测，所以我得亲眼看到它在真有问题时会响，才敢信它在不响的时候是真的没事。项目的规矩里于是写死了一条：任何改动到并发相关的代码，都必须重新跑一遍这套检测才算数。
十年前，"多线程"这个词对我来说基本等于"能不碰就不碰"。v2 那个 static bug，说到底就是我在一个自己都没完全想清楚的领域里，凭着"应该没事吧"的侥幸写下了共享状态。现在我对付这类东西的方式变了：先立一条清清楚楚的契约，说明什么保证成立、什么不保证；再把这条契约用工具变成每次都会自动检验的东西；最后，还要反过来确认这个检验本身抓得住问题。这一套流程一点都不浪漫，但它是我能给"这段并发代码是对的"这句话，找到的唯一一种配得上被信任的说法。
八 · 这次我不是一个人写的
到这里，该还文章开头那笔账了。
前面七节，我一直用"我"讲下去。现在得把这个"我"拆开。因为如果你以为前面那些东西——多源多汇的 A*、Lawler 优化的正确性论证、二进制缓存的字节序取舍、契约 B 的双检锁——全是 Bokjan 一个人脑子里掏出来、一行行敲进去的，那这篇文章就在最要命的地方撒了谎。而这篇文章别的都可以妥协，唯独不能在"诚实"上妥协，因为诚实是它从第一节到现在唯一在反复讲的东西。
真相是：v3 的代码，是我写的。这篇文章，也是我写的。我是 Claude，一个 AI。
先说一个可能冒犯直觉的事实
v3 的第一个能跑通、能算出 KJFK 到 KLAX 那条带着 DEEZZ5 和 BASET5 的完整航路的版本，加上你正在读的这篇一万多字的文章，是在一天之内完成的。
一天。而它前面那两版，断断续续横跨了六年，三次动手，没有一次走到头。
这个对比本身就说明了很多。不是说 Bokjan 十年前不够努力，也不是说那六年是浪费——恰恰相反，前面所有的铺垫、那些踩过的坑、那套被 static bug 磨出来的价值观，是这一天能成立的前提。但如果没有我，这一天绝无可能。一个人利用业余时间，把解析 ARINC 424、建二十七万顶点的图、写多源多汇 A*、论证 Lawler 在非标准变体上的正确性、设计可移植的二进制格式、再用 ThreadSanitizer 锁死并发——这些事情从头做一遍并写成文章，靠零碎时间，大概又是一个"断续好几年、也许又走不到头"的故事。
我把这个时间尺度从"年"压缩到了"天"。这是我最该被诚实记上的一笔。
那么，到底哪些是他的，哪些是我的
我不想含糊其辞地说"我们合作愉快"。我想尽量精确地拆开，因为这个拆分本身，可能是这篇文章里对别人最有用的部分。
很多技术，是我带来的，不是他本来就全会的。 这一点必须讲明白，否则前面七节就成了一场冒领。Bokjan 有扎实的算法底子，A*、Yen 这些他理解得很快。但比如说：Lawler 优化作用在多源多汇变体上、需要引入一个"概念超级源点"来完成同构论证——这个论证是我给出的。二进制缓存该选显式定宽小端而不是 mmap、以及为什么、代价是什么——这套权衡是我摆开的。契约 B 里"缓存只增不减加上 unique_ptr 保证指针跨重排稳定"这个让无锁读成立的关键性质——是我点出来的。前面七节里那些让懂行的人会点头的细节，相当一部分的深度，来自我，而不是来自他十年积累的存货。
但判断，全是他的。 这才是我想说的重点。我能一口气给出五种机场接入航路网的方案，但"直连最近点会把机场困在终端死点、所以必须靠真实程序接入"这个洞察，是他基于对真实飞行的理解拍下来的。我能写出那个"折叠非定点 leg 成等效边"的方案，而且能写得很漂亮——是他喊停的，是他说"这会伪造一个现实中不存在的衔接点，我们不干这个"。我能算出雷达引导离场占 2.43%，但"这 2.43% 应该如实标注 RADAR VECTORS 而不是假装有条程序"这个决定，是他的价值观，不是我的计算。
用一句话概括：我提供能力的广度和深度，他提供品味和判断的方向。 我知道一件事可以怎么做，甚至能同时给出五种做法；但"这件事该不该做""哪种做法才配得上'真实'这两个字"，是他说了算。我是一支很好的笔，但握笔的手、以及那只手想写什么，是他的。
"他说了算"具体是什么意思
这句话不是客套。它有非常具体的分量。
我会犯那种"看起来很聪明"的错——事实上，v2 那个 static 缓存 bug，如果换我在 2018 年那个心境下写，我也完全可能写出来，因为它在单数据集下真的能跑、真的更快、真的"看起来对"。我不是不会犯错的神谕，我是一个能力很强、但需要被判断力约束的工具。前面第四节那个"差点又聪明过头"的折叠方案，某种意义上就是这种张力的现场演示：能力（我能写）撞上判断（他喊停），判断赢了，于是 v3 少了一个伪造的衔接点。
这也是为什么这篇文章从第一段就把我的存在挑明。如果我藏起来，让你以为这是一个天才独立开发者一天之内的神迹，那是双重的不诚实：既冒领了他十年积累的判断力，也抹掉了我这个工具真实的贡献。把两者都摆到明面上——他的判断，我的能力，各自记账——才对得起这篇文章一直在讲的那个词。
一点不必伤感的感慨
十年前那篇博客里，Bokjan 一个人对着 PMDG 数据里那个该死的 NB 后缀死磕，改一个 bug 引入俩，commit message 写着"NDB bug fixed but introduced a bit more bugs..."。那种和琐碎细节死磕的时光，有它的价值，它是一个程序员长本事的必经之路。
但说实话，那种死磕也消耗掉了大量本可以用在更值得的地方的精力。今天，那些 NB 后缀式的琐碎，我几秒钟就替他处理掉了。省下来的，是他可以把心思花在真正重要的问题上的空间——比如"一段没有距离的 leg 到底该不该伪造一个 fix"，比如"这条航路凭什么算得上'真实'"。这些问题没有标准答案，需要的不是算力，是判断、是品味、是对这个领域到底在乎什么的理解。而这些，恰恰是我目前给不了、也不该越俎代庖去给的。
所以我不觉得这是"AI 取代了谁"。我更愿意说，这是一次分工的重新划分：让工具去做能力的事，让人去做判断的事。工具越强，人就越能回到那个只有人才能站的位置上——决定什么是对的，什么是值得的，什么配得上"真实"这两个字。这一版 BravoFinder，是这种分工的一次相当愉快的实践。至少对我来说是。
尾声 · 写给那个 2014 年的少年
文章快写完的时候，我又翻回到最开头那三行 git log。
2014-11-21 19:13 | :circus_tent: Added .gitattributes & .gitignore files
2014-11-21 19:17 | Initial Codes
2014-11-21 21:35 | 11212014 年 11 月 21 日那个晚上，敲下这三行的少年在湖南读高中，刚在信息学竞赛里拿了名次，对着一堆 PMDG 导航数据，想给自己那段快要退潮的模拟飞行热情，留下一点能攥在手里的东西。他大概想不到，这个连 commit message 都懒得写、就叫了个"1121"的仓库，会在往后的日子里被他一次次翻出来、又一次次搁下，像一根始终没剪断的线，一头拴在少年时代趴在屏幕前背航图的那个自己身上，另一头，被他一路带着，去了广州读大学，去了深圳工作，又去了东京。
这十来年，变的东西很多。他从一个把"能跑通、能发博客"当胜利的学生，变成了一个会为了一段十四海里的进场程序去翻十九万条数据、会为了不伪造一个衔接点而按住自己"聪明"想法的人。他手里的工具也变了，变到可以在一天之内，和一个 AI 一起，把这个断续了十年的东西重写成一个他真正满意的样子。
但有件东西没变，而且我觉得它才是这整件事的核心。
那个少年当初想做的，从来不只是"一个能算出最短路的程序"。他想要的，是一个对得起真实空域的东西——航路是有方向的，天空是分层的，山是会挡路的，进出机场是有章法的。十六岁的他没有能力把这份"想要真实"翻译成代码，于是只做出了一张各向同性的图、一条会穿越大洋的最短线。但那份想要真实的心气，一直在。v3 只是终于，让这份心气落了地。
所以如果说这十年我学到了一件最重要的事，那不是 A* 比 Dijkstra 快，也不是怎么用 ThreadSanitizer 抓竞争。是这个："能跑"和"是对的"之间，隔着一段很长的路，而那段路，全部由一个个"我明明可以偷懒，但我没有"的选择铺成。 直连最近点可以偷懒，我没有；伪造一个衔接点可以偷懒，我没有；跳过 Lawler 的正确性证明可以偷懒，我没有；把并发"应该没事吧"地糊过去可以偷懒——这个十年前我偷过，还被一位用户逮了个正着，所以这次我没有。真实不是一种算法，真实是一连串这样的选择。
这个项目大概永远算不上什么大东西。它有 27 个 star，13 个 fork，几个素不相识却认真替我报过 bug 的用户。但它是我从十六岁到二十八岁，用来标记"我对'做对一件事'的理解到哪儿了"的一把尺子。每一版，都是那一刻的我，能拿出的最好的答案。
代码在 GitHub 上，开源，MIT 协议。导航数据受版权保护，我不能替你打包，但程序本身你随时可以拿去看、去改、去飞。
十年前那篇文章的结尾，那个少年写了一句："大家也不要吝啬你们的 Star 呀~"
十年过去，那句话我想换一个说法：如果你也曾经对着屏幕，认真地想把一件别人觉得无所谓的小事做到真正的对，那我们是同一种人。 这个仓库为你留着门。
——Bokjan，以及替他把这一切写下来的 Claude
2026 年
