# VectorPaint负边最短路：先确定的四会被三改写，负环又取消有限最短值

语言：zh-CN
原文：[VectorPaint负边最短路：先确定的四会被三改写，负环又取消有限最短值](<https://allluckly.cn/guides/vectorpaint-negative-edge-shortest-walk-settled-dijkstra-counterexample/>)
中文：[中文 HTML](<https://allluckly.cn/guides/vectorpaint-negative-edge-shortest-walk-settled-dijkstra-counterexample/>)
English: [English HTML](<https://allluckly.cn/en/guides/vectorpaint-negative-edge-shortest-walk-settled-dijkstra-counterexample/>)
发布于: 2026-11-18T00:00:00+08:00
内容更新于: 2026-11-18T00:00:00+08:00
署名：Bison

用四顶点有向图逐层核三步最短值，明确Dijkstra非负条件与可达负环的不同问题。

画一个含一条负权边的有向图，逐条列出从S到T的路线，并用限制边数的账本独立复算。原图没有环，仍足以反驳把已确定顶点永不重开的Dijkstra流程用于任意负边。再单独加一条边，说明负环时为什么连有限最小值都可能消失。

## 明确有向边与抽象权重

顶点S、A、B、T，边为S到A权二、S到B权五、B到A权负四、A到T权二、B到T权十。权值是可相加的抽象代价，不代表可为负的实际路程或时间。原图拓扑次序可取S、B、A、T，故无环；边方向不能省略，否则问题已改变。建立顶点、箭头、权标签、路径账与控制层，先存原稿。本课用“路线”允许重复顶点的有向行走；原图无环所以有限路线不重复，后续负环控制再明确重复的意义。

## 列出三条完整路线核最小三

原图S到T恰有S到A到T代价2+2=四，S到B到T代价5+10=十五，S到B到A到T代价5−4+2=三。故最小值三，经B再A；S到A的最好代价是一，不是直达边的二。先列完整路线再比较，不能因为经过更多边就认定更长。图上用一条独立描边标最优路线但保留所有原边，标签写“抽象代价三”，避免把负权解释为真实捷径或据此推荐出行操作。

## 逐次演示确定顶点的错误前提

从S开始的暂定值A二、B五，按最小值先确定A，再得到T四。此时T四比B五小，若采用目标被确定即停止的Dijkstra流程，会返回四，漏掉尚未处理B所带来的负四改进。若继续但坚持已确定A不再更新，同样不能修复A的正确值一。反例针对非负条件被违反时的保证，不能反向宣称每张含负边图都一定算错。允许重开顶点的其他流程需要自己的定义与证明，不可只换一个软件标签就视为同一保证。

## 以最多一条边为第一层账本

定义δk(v)为从S到v最多使用k条边的最小代价，δ0(S)=零，其余无可达路线记∞，不是一个很大的实数。第一层δ1中A二、B五、T仍∞。每层可保留上一层值，或用上一层某点代价加一条到达边，取最小值；必须全部读取上一层，不能混用本层刚更新的值又称“只加一条边”。列S、A、B、T四栏并标“最多”，否则恰好k条边的定义会让S零和旧最短值的保留规则产生歧义。

## 再算两层并与路线枚举对照

第二层A取min(二,五减四)=一，B仍五，T取min(二加二,五加十)=四。第三层T可从上一层A一加二得到三，A一、B五保持。于是δ0到δ3的T栏依次∞、∞、四、三，和三条路线枚举一致。原图四个顶点且无环，任一路线最多三条边，因此这里三层足够；这个理由来自本图结构，不是对任意有环图盲目截三步。账本中负号必须保留，∞加有限权仍表示不可达，不能当零处理。还可按原图拓扑序S、B、A、T手工传播：先得B五，再用负四把A改为一，最后T为三。该顺序尊重全部边方向，说明无环条件能支持另一种正确核验，不需要假装原图权值全非负。

```
S->A:2; S->B:5; B->A:-4; A->T:2; B->T:10
S-A-T=4; S-B-T=15; S-B-A-T=3
at most k edges; columns S,A,B,T
k=0: 0,inf,inf,inf
k=1: 0,2,5,inf
k=2: 0,1,5,4
k=3: 0,1,5,3
control add A->B:1
cycle A-B-A=1-4=-3, reachable from S and able to reach T
```

## 加反向边后把负环与负边分开

另存只加A到B权一的版本，A到B到A环代价1−4=负三，且从S可达，走完环后仍能到T。每多绕一圈总代价再减三，可任意降低，因此允许重复顶点的最短路线没有有限最小值。若规定只能走不重复顶点的简单路径，那是另一个有限候选问题，不可用它否认本控制中的负环结论。原图只有负边但无负环，仍有最小三，两个事实不能混成“见负号就没有答案”；保留添加前后两版供比较。

## 按方向落图并分开反向弧线

建议2200×1500画布，S=(300,750)、B=(900,350)、A=(900,1100)、T=(1800,750)。B到A的负四边向下，控制版A到B另画偏离直线的弧，不能用一条无向线共用两个权值。先点后箭头再标签，图上的像素位置只为排版，权重不由线段长度读取。排障先核边方向和负号，再核δ层读取规则及停止条件。若最优高亮遮住箭头，可减细或移动高亮而不改权，不能为了画面直观偷偷删掉反例所需边。

## 重开先验路线再解释算法限制

保存两版可编辑图与账本，导出SVG或PDF并另开PNG，缩小核B到A方向仍清楚，放大核负四和负三未失负号。重开原稿先从三条完整路线恢复最小三，再对照确定流程返回四的原因，最后说明控制版无有限最小值的可达条件。交付图、三层账和两类前提，未执行的输出检查记待办。VectorPaint仅手工呈现有向图，不声称内置最短路、负环检测或真实网络优化，也不把未做的运行写成测试通过。

## 相关教程与资料

[VectorPaint 五节点加权路线：先加边权再比较候选路径](<https://allluckly.cn/guides/vectorpaint-five-node-weighted-routes/>)、[VectorPaint 有向依赖图：让箭头与可行顺序一一对应](<https://allluckly.cn/guides/vectorpaint-dependency-arrows-feasible-order/>)。

方法来源：[MIT6.006 Lecture13, Dijkstra and nonnegative weights](<https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/d819e7f4568aced8d5b59e03db6c7b67_MIT6_006S20_lec13.pdf>)、[MIT6.006 Lecture12, Bellman–Ford and negative cycles](<https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/2430d7903a5529451d80c17f89a41fe8_MIT6_006S20_lec12.pdf>)。

版本与操作范围：2026年11月18日核[VectorPaint官方商店](<https://apps.apple.com/cn/app/id1587272880>)与[Apple公开查询](<https://itunes.apple.com/lookup?id=1587272880&country=cn&entity=software&timestamp=20261118-vectorpaint>)，公开1.0.8，最低iOS / iPadOS 17.0。使用已公开的形状、钢笔、贝塞尔节点、网格辅助线、对齐、图层分组、文字和保存输出手工绘图；入口按安装版本实际可见为准。计算、定义与复算在应用外准备，不推断内置公式、统计或图论求解能力。原生稿保留可编辑结构，SVG、PDF、PNG各按需要阅读检查，含导入位图的SVG或PDF不自动成为全矢量。画布与样本为原创教学设定，未执行真机或实物测量，未做的操作明确待做。

