7.12 Dijkstra 算法正确性试证明

[rawcheeselatte]

假设点集 Vertex 中所含子集 A，对于从 A 出发的边集 Edge，若选定其中权重最小的边 Em，Em 指向点 B，可知：

• Edge 中不存在权重小于 Em 的边
• 对于 Edge 中除 Em 外的任意边 E*
  • 若 weight( E* ) > weight( Em )，则对于 E* 所指向的点 V* 不存在边 EV 指向 B 使得 weight( E* ) + weight( EV ) <= weight( Em )
  • 若 weight( E* ) = weight( Em )，当且仅当 E* 所指向的点 V* 中存在指向 B 的 EV 有 weight( EV ) == 0 时， weight( E* ) + weight( EV ) = weight( Em ) 此时 A --Em--> B 等价于 A --E*--> V* --EV--> B

对于 A + B = A* 的边集 Edge + EdgeB = Edge* 中权重最小的边 Em* 所指向的点 C 同理可证

参考《数据结构（C语言版）》--严蔚敏 P188