@iyowei/dijkstra

找到两个顶点之间的最短路径。

• [x] 现代化；
• [x] 高性能；
• [x] 包含 "单源、有向、无环、无负权、多叉树" 图的编辑、最短路径查询等函数；
• [x] Treeshaking 友好；
• [x] 充分测试；

目录

• 使用
• APIs
• 性能
• 安装
• 参与贡献
• 其它

使用

import { log } from 'console';
import { grapher, addEdge, find } from '@iyowei/dijkstra';

const grapherInstance = grapher();

addEdge('one', 'two', 5, graph);
addEdge('one', 'three', 2, graph);

addEdge('three', 'two', 8, graph);
addEdge('three', 'five', 7, graph);

addEdge('two', 'four', 4, graph);
addEdge('two', 'five', 2, graph);

addEdge('four', 'five', 6, graph);
addEdge('four', 'final', 3, graph);

addEdge('five', 'final', 1, graph);

const { path } = find({
  startNode: 'one',
  endNode: 'final',
  grapherInstance,
});

log(path); // ['one', 'two', 'five', 'final']

APIs

grapher()

初始化实例数据，支持多实例。

addEdge(parentNodeId, childNodeId, weight, grapherInstance)

• parentNodeId { String } 父节点 ID
• childNodeId { String } 子节点 ID
• weight { Number } 权重
• grapherInstance 使用 grapher() 创建的图实例
• 返回 { Number } 添加权重成功与否，1 表示成功，-1 表示操作失败

向图中增加新的权重关系。

find({ startNodeId, endNodeId, grapherInstance })

• startNodeId { String } 开始节点 ID
• endNodeId { String } 结束节点 ID
• grapherInstance 使用 grapher() 创建的图实例
• 返回 { Object }
  • path { Array } 最短路径
  • weight { Array } 最短路径权重

指定开始节点、结束节点，寻找它们的最短路径。

isAcyclic(startNodeId, endNodeId, grapherInstance)

• startNodeId { String } 开始节点 ID
• endNodeId { String } 结束节点 ID
• grapherInstance 使用 grapher() 创建的图实例
• 返回 { Boolean }
  • true 无环
  • false 回环

指定开始节点、结束节点，检查是否回环。

deleteNode(nodeId, grapherInstance)

• nodeId { String } 节点 ID
• grapherInstance 使用 grapher() 创建的图实例
• 返回 { Number } 删除节点成功与否，1 表示成功，-1 表示操作失败

删除指定节点。

deleteDependence(startNodeId, endNodeId, grapherInstance)

• startNodeId { String } 开始节点 ID
• endNodeId { String } 结束节点 ID
• grapherInstance 使用 grapher() 创建的图实例
• 返回 { Number } 删除节点成功与否，1 表示成功，-1 表示操作失败

删除指定节点间的权重。

性能

import Benchmark from 'benchmark';
import { grapher, addEdge, find } from './dijkstra.js';

const grapherInstance = grapher();
grapherInstance.acyclic = true;
grapherInstance.source = true;

addEdge('one', 'two', 5, grapherInstance);
addEdge('one', 'three', 2, grapherInstance);
addEdge('three', 'two', 8, grapherInstance);

addEdge('three', 'five', 7, grapherInstance);

addEdge('two', 'four', 4, grapherInstance);

addEdge('two', 'five', 2, grapherInstance);
addEdge('four', 'five', 6, grapherInstance);

addEdge('four', 'final', 3, grapherInstance);

addEdge('five', 'final', 1, grapherInstance);

const foundShortestPath = find({
  startNodeId: 'one',
  endNodeId: 'final',
  grapherInstance,
});

new Benchmark.Suite()
  .add('find', () => {
    find({
      startNodeId: 'one',
      endNodeId: 'final',
      grapherInstance,
    });
  })
  .add('path', () => {
    foundShortestPath.path;
  })
  .on('cycle', (event) => {
    console.log(String(event.target));
  })
  .run({ async: true });

find

find x 1,774,453 ops/sec ±0.86% (89 runs sampled)

path

path x 3,250,928 ops/sec ±0.62% (91 runs sampled)

测试用机器，

                    'c.
                 ,xNMM.
               .OMMMMo           OS: macOS 12.1 21C52 x86_64
               OMMM0,            Host: MacBookPro11,5
     .;loddo:' loolloddol;.      Kernel: 21.2.0
   cKMMMMMMMMMMNWMMMMMMMMMM0:    Uptime: 3 days, 13 hours
 .KMMMMMMMMMMMMMMMMMMMMMMMWd.    Packages: 172 (brew)
 XMMMMMMMMMMMMMMMMMMMMMMMX.      Shell: zsh 5.8
;MMMMMMMMMMMMMMMMMMMMMMMM:       Resolution: 1920x1200@2x
:MMMMMMMMMMMMMMMMMMMMMMMM:       DE: Aqua
.MMMMMMMMMMMMMMMMMMMMMMMMX.      WM: Rectangle
 kMMMMMMMMMMMMMMMMMMMMMMMMWd.    Terminal: iTerm2
 .XMMMMMMMMMMMMMMMMMMMMMMMMMMk   Terminal Font: Hack-Regular 12
  .XMMMMMMMMMMMMMMMMMMMMMMMMK.   CPU: Intel i7-4870HQ (8) @ 2.50GHz
    kMMMMMMMMMMMMMMMMMMMMMMd     GPU: AMD Radeon R9 M370X, Intel Iris Pro
     ;KMMMMMMMWXXWMMMMMMMk.      Memory: 8880MiB / 16384MiB
       .cooc,.    .,coo:.

安装

NPM

npm add @iyowei/dijkstra

PNPM

pnpm add @iyowei/dijkstra

Yarn

yarn add @iyowei/dijkstra

参与贡献

其它

"@iyowei/dijkstra" 使用 @iyowei/create-esm 脚手架生成。