离散更新、循环与边界
VectorPaint负边最短路:先确定的四会被三改写,负环又取消有限最短值
用四顶点有向图逐层核三步最短值,明确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 五节点加权路线:先加边权再比较候选路径、VectorPaint 有向依赖图:让箭头与可行顺序一一对应。
方法来源:MIT6.006 Lecture13, Dijkstra and nonnegative weights、MIT6.006 Lecture12, Bellman–Ford and negative cycles。
版本与操作范围:2026年11月18日核VectorPaint官方商店与Apple公开查询,公开1.0.8,最低iOS / iPadOS 17.0。使用已公开的形状、钢笔、贝塞尔节点、网格辅助线、对齐、图层分组、文字和保存输出手工绘图;入口按安装版本实际可见为准。计算、定义与复算在应用外准备,不推断内置公式、统计或图论求解能力。原生稿保留可编辑结构,SVG、PDF、PNG各按需要阅读检查,含导入位图的SVG或PDF不自动成为全矢量。画布与样本为原创教学设定,未执行真机或实物测量,未做的操作明确待做。