最短路算法及差分系统.docx

最短路算法及差分系统 Yuke Liao liao.yu.ke@ 2012/7/29 定义 在最短路问题中给出的是一有向加权图G=(V,E) 在其上定义的加权函数W:ER为从边到实型权值的映射路径P=(v0, v1, vk)的权是指其组成边的所有权 值之和 ? ? ? = ? ?1) ?=0 ?定义u到v间最短路径的权为 ? ? ? ? v) ? ?min?w( p:u?v? 如