2026/9/15 20:56:41
FEATURED · 精选文章 
Effect Graph 最短路径算法的边权校验拒绝 NaN 与 -Infinity 的有限边权语义【免费下载链接】t3code项目地址: https://gitcode.com/GitHub_Trending/t3/t3code本篇技术指南围绕 Effect 库 Graph 模块的一次核心补丁展开在 Dijkstra、A*、Bellman-Ford、Floyd-Warshall 等最短路径算法中统一拒绝NaN与-Infinity作为边权仅允许非负有限数值与作为不可通行哨兵的Infinity。读者将掌握这些算法的边权合法域、校验时机、错误类型以及Infinity与非法数值在路径计算中的不同语义。变更背景一次针对 Graph 最短路径边权合法性的修复在 effect-smol 仓库的变更集中fix-graph-finite-edge-weights.md记录了这样一条patch级别变更RejectNaNand-Infinityedge weights in Graph shortest-path algorithms.该变更将effect包的 Graph 模块Graph.ts中所有最短路径类算法对边权的校验收紧为同一套规则边权必须是非负的有限数值non-negative finiteNaN与-Infinity一律拒绝而正Infinity则被保留作为不可通行边impassable edge的合法标记。从源码结构看这套校验贯穿了模块内五个核心路径算法/结构且错误均以GraphError抛出保证 API 行为的一致性与可预期性。边权合法域什么值允许、什么值拒绝Effect Graph 对最短路径边权的判定规则可以归纳为一张清晰的对照表边权值是否合法语义非负有限数值0及以上✅ 合法正常的通行成本例如 5、2、0Infinity正无穷✅ 合法表示该边不可通行impassable edge路径计算时直接跳过负数如-1❌ 拒绝仅 Dijkstra 与 A* 拒绝二者要求非负权重Bellman-Ford 允许负权但拒绝负无穷NaN❌ 拒绝非法权重全部算法均抛出GraphError-Infinity负无穷❌ 拒绝非法权重全部算法均抛出GraphError路径累计距离溢出有限数值范围❌ 抛出计算过程中一旦距离不再是有限数值立即抛错而非静默污染结果这套语义的核心设计是Infinity是唯一的无穷哨兵且只允许以正无穷的形式存在。它让调用方可以在不删除边的前提下表达这条路暂时不通而NaN与-Infinity则往往是成本函数cost function的 bug 产物——如未初始化的变量、错误的数学运算——因此必须被快速失败fail-fast而不是被悄悄带入距离比较否则会产生不可复现的错误路径结果。Dijkstra非负权重 运行时数值域检查Dijkstra 是模块中最常用的单源最短路径算法。其配置接口DijkstraConfigEGraph.ts要求提供源点、目标点与一个把边数据映射为数值权重的cost函数export interface DijkstraConfigE { source: NodeIndex target: NodeIndex cost: (edgeData: E) number }在dijkstra的实现Graph.ts中边权校验发生在算法主循环之前——权重被一次性预计算进Float64Array缓存并在该过程中执行校验const edgeWeights new Float64Array(cachedEdges.length) withMutationGuard(graph, () { for (let i 0; i cachedEdges.length; i) { const weight config.cost(cachedEdges[i].data) if (Number.isNaN(weight) || weight 0) { throw new GraphError({ message: Dijkstras algorithm requires non-negative edge weights }) } edgeWeights[i] weight } })可以看到Dijkstra 在此处拒绝NaN与一切负权重含-Infinity因为-Infinity 0成立而Infinity得以通过并进入后续计算。此外算法在松弛阶段relaxation还会做第二层运行时防护防止路径距离累计溢出const nextDistance currentDistance edgeWeights[edge] if (edgeWeights[edge] ! Infinity !Number.isFinite(nextDistance)) { throw new GraphError({ message: Dijkstra distance calculation exceeded the finite number range }) }也就是说单条边权为Infinity时该边被跳过但若两条有限边权相加后距离变为非有限值极端大数溢出则会抛错避免Float64Array中产生静默的精度污染。一个完整可运行的最小示例来自 Graph.ts 内嵌的 vitest 文档测试import { Graph, Option } from effect const graph Graph.directedstring, number((mutable) { const a Graph.addNode(mutable, A) const b Graph.addNode(mutable, B) const c Graph.addNode(mutable, C) Graph.addEdge(mutable, a, b, 5) Graph.addEdge(mutable, a, c, 10) Graph.addEdge(mutable, b, c, 2) }) const result Graph.dijkstra(graph, { source: 0, target: 2, cost: (edgeData) edgeData }) Option.map(result, ({ distance, path }) [distance, path] as const) // Option.some([7, [0, 1, 2]]) // A - B - C总代价 5 2 7Floyd-Warshall全对最短路径的显式 -Infinity 拒绝对于全对最短路径all-pairs shortest paths模块提供floydWarshall。其校验更为显式——由于该算法在数学上允许-Infinity参与距离更新会产生歧义实现直接对NaN与-Infinity二者单独判定并抛出明确错误信息Graph.tsif (Number.isNaN(weight) || weight -Infinity) { throw new GraphError({ message: Floyd-Warshall algorithm does not support NaN or -Infinity edge weights }) }在动态规划主循环中Infinity被用作两点之间尚不可达的占位值仅在distanceIK Infinity或distanceKJ Infinity时跳过中间点合并从而保证Infinity不会污染真实的距离比较。Bellman-Ford允许负权但拒绝 NaN 与负无穷Bellman-Ford 是三类最短路径算法中唯一允许有限负权边的算法文档注释明确写到 Negative edge weights are allowed, andInfinitybehaves like an impassable edge。但它的校验仍然遵循本次变更的统一基调Graph.tsif (Number.isNaN(weight) || weight -Infinity) { throw new GraphError({ message: Bellman-Ford algorithm does not support NaN or -Infinity edge weights }) }其距离更新同样把Infinity当作不可通行处理if (distance Infinity || weight Infinity) { return Infinity }因此它的合法边权集合是任意有限实数可为负Infinity唯独排除NaN与-Infinity。这与Infinity是唯一允许的无穷哨兵的设计原则保持一致。最小生成森林与 A*同一套校验的扩展覆盖本次变更的校验语义并不只作用于严格意义上的最短路径算法还扩展到了最小生成森林minimumSpanningForest与带启发式的 A*astarminimumSpanningForest在 Graph.ts 中校验Number.isNaN(weight) || weight -Infinity并跳过weight ! Infinity的边astar在 Graph.ts 中与 Dijkstra 一致拒绝NaN与负权重并在累计距离失去有限性时抛出GraphError。从源码结构看这两处与 Dijkstra / Floyd-Warshall 的校验逻辑互为镜像说明该变更是一次横跨整个 Graph 算法族的系统性收紧而非针对单一函数的局部修复。错误处理与调用方注意事项所有上述校验失败均抛出GraphError其message字段携带算法名称与原因便于快速定位是哪个算法、哪条边出了问题。调用方在接入边权时应重点注意成本函数必须为纯函数由于权重在算法入口处一次性预计算并缓存进Float64Array成本函数会被调用固定次数若函数带有随机性或副作用校验结果与计算结果将不可复现。用Infinity表达断路而非删除边这是模块的官方语义既保留了图结构又能在遍历/重建时保留边的存在性。警惕极大数据溢出即便通过了边权校验路径距离累计仍可能突破有限数范围此时 Dijkstra / A* 会额外抛错调用方应将其视为输入数据异常的提示。NaN通常意味着上游 bug成本函数返回NaN几乎总是未初始化数据或非法运算的结果fail-fast 的抛错行为正是为了让这类问题在开发期暴露。结语fix-graph-finite-edge-weights这条patch变更看似微小实则为 Effect Graph 的整套路径算法确立了统一的数值契约非负有限数值 正无穷哨兵其余一切非有限值NaN、-Infinity均在入口被快速拒绝。理解这套边权语义是正确使用Graph.dijkstra、Graph.astar、Graph.bellmanFord、Graph.floydWarshall与Graph.minimumSpanningForest的前提也能帮助你在排查路径结果异常时第一时间定位到成本函数的数据质量问题。【免费下载链接】t3code项目地址: https://gitcode.com/GitHub_Trending/t3/t3code创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Effect Graph 最短路径算法的边权校验：拒绝 NaN 与 -Infinity 的有限边权语义
Effect Graph 最短路径算法的边权校验拒绝 NaN 与 -Infinity 的有限边权语义【免费下载链接】t3code项目地址: https://gitcode.com/GitHub_Trending/t3/t3code本篇技术指南围绕 Effect 库 Graph 模块的一次核心补丁展开在 Dijkstra、A*、Bellman-Ford、Floyd-Warshall 等最短路径算法中统一拒绝NaN与-Infinity作为边权仅允许非负有限数值与作为不可通行哨兵的Infinity。读者将掌握这些算法的边权合法域、校验时机、错误类型以及Infinity与非法数值在路径计算中的不同语义。变更背景一次针对 Graph 最短路径边权合法性的修复在 effect-smol 仓库的变更集中fix-graph-finite-edge-weights.md记录了这样一条patch级别变更RejectNaNand-Infinityedge weights in Graph shortest-path algorithms.该变更将effect包的 Graph 模块Graph.ts中所有最短路径类算法对边权的校验收紧为同一套规则边权必须是非负的有限数值non-negative finiteNaN与-Infinity一律拒绝而正Infinity则被保留作为不可通行边impassable edge的合法标记。从源码结构看这套校验贯穿了模块内五个核心路径算法/结构且错误均以GraphError抛出保证 API 行为的一致性与可预期性。边权合法域什么值允许、什么值拒绝Effect Graph 对最短路径边权的判定规则可以归纳为一张清晰的对照表边权值是否合法语义非负有限数值0及以上✅ 合法正常的通行成本例如 5、2、0Infinity正无穷✅ 合法表示该边不可通行impassable edge路径计算时直接跳过负数如-1❌ 拒绝仅 Dijkstra 与 A* 拒绝二者要求非负权重Bellman-Ford 允许负权但拒绝负无穷NaN❌ 拒绝非法权重全部算法均抛出GraphError-Infinity负无穷❌ 拒绝非法权重全部算法均抛出GraphError路径累计距离溢出有限数值范围❌ 抛出计算过程中一旦距离不再是有限数值立即抛错而非静默污染结果这套语义的核心设计是Infinity是唯一的无穷哨兵且只允许以正无穷的形式存在。它让调用方可以在不删除边的前提下表达这条路暂时不通而NaN与-Infinity则往往是成本函数cost function的 bug 产物——如未初始化的变量、错误的数学运算——因此必须被快速失败fail-fast而不是被悄悄带入距离比较否则会产生不可复现的错误路径结果。Dijkstra非负权重 运行时数值域检查Dijkstra 是模块中最常用的单源最短路径算法。其配置接口DijkstraConfigEGraph.ts要求提供源点、目标点与一个把边数据映射为数值权重的cost函数export interface DijkstraConfigE { source: NodeIndex target: NodeIndex cost: (edgeData: E) number }在dijkstra的实现Graph.ts中边权校验发生在算法主循环之前——权重被一次性预计算进Float64Array缓存并在该过程中执行校验const edgeWeights new Float64Array(cachedEdges.length) withMutationGuard(graph, () { for (let i 0; i cachedEdges.length; i) { const weight config.cost(cachedEdges[i].data) if (Number.isNaN(weight) || weight 0) { throw new GraphError({ message: Dijkstras algorithm requires non-negative edge weights }) } edgeWeights[i] weight } })可以看到Dijkstra 在此处拒绝NaN与一切负权重含-Infinity因为-Infinity 0成立而Infinity得以通过并进入后续计算。此外算法在松弛阶段relaxation还会做第二层运行时防护防止路径距离累计溢出const nextDistance currentDistance edgeWeights[edge] if (edgeWeights[edge] ! Infinity !Number.isFinite(nextDistance)) { throw new GraphError({ message: Dijkstra distance calculation exceeded the finite number range }) }也就是说单条边权为Infinity时该边被跳过但若两条有限边权相加后距离变为非有限值极端大数溢出则会抛错避免Float64Array中产生静默的精度污染。一个完整可运行的最小示例来自 Graph.ts 内嵌的 vitest 文档测试import { Graph, Option } from effect const graph Graph.directedstring, number((mutable) { const a Graph.addNode(mutable, A) const b Graph.addNode(mutable, B) const c Graph.addNode(mutable, C) Graph.addEdge(mutable, a, b, 5) Graph.addEdge(mutable, a, c, 10) Graph.addEdge(mutable, b, c, 2) }) const result Graph.dijkstra(graph, { source: 0, target: 2, cost: (edgeData) edgeData }) Option.map(result, ({ distance, path }) [distance, path] as const) // Option.some([7, [0, 1, 2]]) // A - B - C总代价 5 2 7Floyd-Warshall全对最短路径的显式 -Infinity 拒绝对于全对最短路径all-pairs shortest paths模块提供floydWarshall。其校验更为显式——由于该算法在数学上允许-Infinity参与距离更新会产生歧义实现直接对NaN与-Infinity二者单独判定并抛出明确错误信息Graph.tsif (Number.isNaN(weight) || weight -Infinity) { throw new GraphError({ message: Floyd-Warshall algorithm does not support NaN or -Infinity edge weights }) }在动态规划主循环中Infinity被用作两点之间尚不可达的占位值仅在distanceIK Infinity或distanceKJ Infinity时跳过中间点合并从而保证Infinity不会污染真实的距离比较。Bellman-Ford允许负权但拒绝 NaN 与负无穷Bellman-Ford 是三类最短路径算法中唯一允许有限负权边的算法文档注释明确写到 Negative edge weights are allowed, andInfinitybehaves like an impassable edge。但它的校验仍然遵循本次变更的统一基调Graph.tsif (Number.isNaN(weight) || weight -Infinity) { throw new GraphError({ message: Bellman-Ford algorithm does not support NaN or -Infinity edge weights }) }其距离更新同样把Infinity当作不可通行处理if (distance Infinity || weight Infinity) { return Infinity }因此它的合法边权集合是任意有限实数可为负Infinity唯独排除NaN与-Infinity。这与Infinity是唯一允许的无穷哨兵的设计原则保持一致。最小生成森林与 A*同一套校验的扩展覆盖本次变更的校验语义并不只作用于严格意义上的最短路径算法还扩展到了最小生成森林minimumSpanningForest与带启发式的 A*astarminimumSpanningForest在 Graph.ts 中校验Number.isNaN(weight) || weight -Infinity并跳过weight ! Infinity的边astar在 Graph.ts 中与 Dijkstra 一致拒绝NaN与负权重并在累计距离失去有限性时抛出GraphError。从源码结构看这两处与 Dijkstra / Floyd-Warshall 的校验逻辑互为镜像说明该变更是一次横跨整个 Graph 算法族的系统性收紧而非针对单一函数的局部修复。错误处理与调用方注意事项所有上述校验失败均抛出GraphError其message字段携带算法名称与原因便于快速定位是哪个算法、哪条边出了问题。调用方在接入边权时应重点注意成本函数必须为纯函数由于权重在算法入口处一次性预计算并缓存进Float64Array成本函数会被调用固定次数若函数带有随机性或副作用校验结果与计算结果将不可复现。用Infinity表达断路而非删除边这是模块的官方语义既保留了图结构又能在遍历/重建时保留边的存在性。警惕极大数据溢出即便通过了边权校验路径距离累计仍可能突破有限数范围此时 Dijkstra / A* 会额外抛错调用方应将其视为输入数据异常的提示。NaN通常意味着上游 bug成本函数返回NaN几乎总是未初始化数据或非法运算的结果fail-fast 的抛错行为正是为了让这类问题在开发期暴露。结语fix-graph-finite-edge-weights这条patch变更看似微小实则为 Effect Graph 的整套路径算法确立了统一的数值契约非负有限数值 正无穷哨兵其余一切非有限值NaN、-Infinity均在入口被快速拒绝。理解这套边权语义是正确使用Graph.dijkstra、Graph.astar、Graph.bellmanFord、Graph.floydWarshall与Graph.minimumSpanningForest的前提也能帮助你在排查路径结果异常时第一时间定位到成本函数的数据质量问题。【免费下载链接】t3code项目地址: https://gitcode.com/GitHub_Trending/t3/t3code创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
