走一条通道会消耗能量,补给通道也可能使净消耗为负。此时总消耗更低不一定意味着路径更短;如果能够循环补给,某些目的地甚至没有有限的最低消耗值。
明确本例规则
本例是有向图,边数值表示净消耗,可以为负;不设置能量上限或中途最低余额限制。先从起点零反复松弛边,最多做房间数减一轮。之后若还能降低某个可达房间的值,就把它及从它能继续到达的房间标为无有限下界。
输入与逐步结果
六个房间,起点零。边记录依次为起点、终点、净消耗,负数代表净补给。
有向通道:[[0, 1, 3], [1, 2, -3], [5, 4, 5], [2, 3, 5], [4, 2, 7], [2, 4, 0], [4, 3, 7], [3, 4, -3]] 每轮到各房间的估计;None表示尚不可达: 0轮:[0, None, None, None, None, None] 1轮:[0, 3, None, None, None, None] 2轮:[0, 3, 0, None, None, None] 3轮:[0, 3, 0, 5, 0, None] 4轮:[0, 3, 0, 5, 0, None] 5轮:[0, 3, 0, 5, 0, None] 最终分类:[0, 3, 0, 5, 0, '不可达'] 受可达负循环影响:[]
编号仅标识本次案例中的对象,不能把它当成重要性排名。复算时先保留原输入,再按表格顺序记录中间状态。零值、空列表和未到达各有含义,不能因为显示相似就合并处理。需要分数的地方保存精确值,小数只用于阅读。
结果如何核对
不可达、有限最小值和无有限下界是三种不同状态。负边本身不是问题,只有从起点可到达的负总和循环才会造成无限降低;而且受影响范围仅包括循环之后仍可到达的房间。
本例用每轮旧距离统一生成新距离,表格因而可按路径最多增加一条边来理解。再用全对距离检查可达负循环和后继范围,可避免把与起点无关的负环也误报到整个地图上。
使用边界
这是为了讲清算法边界的抽象模型,不代表实际游戏允许无限补给。若补给只能领取一次、需要携带容量或通道有限次使用,状态必须包含这些信息,不能继续用同一个房间编号概括所有历史。
练习可以先保持其他条件不变,只调整一项输入,观察哪个中间步骤首先产生差异。如果结果不同,先确认单位、端点和同值处理是否一致,再查具体运算。最终答案应与输入和过程一起保存,才方便判断这份结论适用于什么情境。
