大家好，很高兴又见面了，我是"高级前端‬进阶‬"，由我带着大家一起关注前端前沿、深入前端底层技术，大家一起进步，也欢迎大家关注、点赞、收藏、转发，您的支持是我不断创作的动力。

今天给大家带来的主题是ngraph.path，即任意图的快速路径查找。

什么是 ngraph.path

ngraph.path 是任意图的快速路径查找。

根据作者的描述，其在纽约市道路图（733,844 个边，264,346 个节点）上测量了该库的性能，即通过解决 250 个随机路径查找问题来完成测试。 不同算法都解决同一组问题，下表显示了解决一个问题所需的时间。

如图所示，“A* greedy”收敛速度最快，然而顾名思义，找到的路径却不一定是全局最优。

目前 ngraph.path 在 Github 上通过 MIT 协议开源，有超过 2.8k 的 star，是一个值得尝试的前端开源项目。

为什么 ngraph.path 这么快

有一些因素有助于提高该库的性能。

ngraph.path 使用基于堆的优先级队列（heap-based priority queue），专门为路径查找而构建。 ngraph.path 本质上通过修改堆的实现，以便更改任何元素的优先级只需要 O(lg n) 的时间复杂度。

每个路径查找器（path finder）在探索过程中都会打开许多图节点，从而给垃圾收集器带来压力。 为了避免压力，ngraph.path 创建了一个对象池，其会在可能的情况下回收节点。

一般来说，A* 算法比 Dijkstra 更快地收敛到最优解，因为它使用启发式函数的“提示”。 当在两个方向（源 -> 目标和目标 -> 源）执行搜索时，可以进一步提高收敛性。 NBA* 算法是一种双向路径查找器，可保证最佳最短路径。 同时消除了平衡启发式要求，它似乎也是这里实现的最快的算法。

ngraph.path 还尝试创建双向 A* 搜索版本，结果比预期的要难 ，即两个搜索很快相遇，但它们相遇的点在最短全局路径上并不是必需的。 虽然接近最优，但不是最优。 因此，如果速度比正确性更重要，这可能是一个很好的权衡，这个算法称为 A* 贪婪算法，但也许它应该是 A* 懒惰算法。

如何使用 ngraph.path基本用法

下面是一个基本示例，它查找任意图中任意两个节点之间的路径：

let path = require('ngraph.path');let pathFinder = path.aStar(graph);// graph is  现在可以找到两个节点之间的路径：let fromNodeId = 40;let toNodeId = 42;let foundPath = pathFinder.find(fromNodeId, toNodeId);// foundPath 是图中的节点数组

上面的示例适用于任何图，它相当于未加权的 Dijkstra 算法。

加权图

假设我们有以下图表：

let createGraph = require('ngraph.graph');let graph = createGraph();graph.addLink('a', 'b', { weight: 10 });graph.addLink('a', 'c', { weight: 10 });graph.addLink('c', 'd', { weight: 5 });graph.addLink('b', 'd', { weight: 10 });

想要找到一条权重尽可能最小的路径：

let pathFinder = aStar(graph, {  // We tell our pathfinder what should it use as a distance function:  distance(fromNode, toNode, link) {    // We don't really care about from/to nodes in this case,    // as link.data has all needed information:    return link.data.weight;  },});let path = pathFinder.find('a', 'd');

此代码将正确打印路径：d <- c <- a。

当 pathfinder 搜索两个节点之间的路径时，会考虑给定节点的所有邻居，没有任何偏好。 在某些情况下，开发者可能想要引导 pathfinder 并告诉它首选的探索方向。

例如，当图中的每个节点都有坐标时，可以假设应该在其他节点之前探索更接近路径查找器目标的节点。

let createGraph = require('ngraph.graph');let graph = createGraph();// Our graph has cities:graph.addNode('NYC', { x: 0, y: 0 });graph.addNode('Boston', { x: 1, y: 1 });graph.addNode('Philadelphia', { x: -1, y: -1 });graph.addNode('Washington', { x: -2, y: -2 });// and railroads:graph.addLink('NYC', 'Boston');graph.addLink('NYC', 'Philadelphia');graph.addLink('Philadelphia', 'Washington');

当构建从纽约到华盛顿的最短路径时，告诉 pathfinder 它应该更喜欢费城而不是波士顿。

let pathFinder = aStar(graph, {  distance(fromNode, toNode) {    // In this case we have coordinates. Lets use them as    // distance between two nodes:    let dx = fromNode.data.x - toNode.data.x;    let dy = fromNode.data.y - toNode.data.y;    return Math.sqrt(dx * dx + dy * dy);  },  heuristic(fromNode, toNode) {    // this is where we "guess" distance between two nodes.    // In this particular case our guess is the same as our distance    // function:    let dx = fromNode.data.x - toNode.data.x;    let dy = fromNode.data.y - toNode.data.y;    return Math.sqrt(dx * dx + dy * dy);  },});let path = pathFinder.find('NYC', 'Washington');

通过这种简单的启发式方法，算法变得更智能、更快。 非常重要的是，启发式函数不会高估两个节点之间的实际距离。如果这样做，那么算法就不能保证最短路径。

关于 ngraph.path 的最多示例本文不再过多展开，可以参考文末的资料自行研究。

参考资料