判断某边是否在图中给定两点间的最短路径上(结论)
由于图中给定两点(假设为No.1 & No.n)间的最短路径不止一条，但可以确定一定是简单通路，因此存在一个较为标准的方法找出在1->n的最短路径的所有边：
- 通过对原图跑Dijkstra求出原点到其他所有点的最短距离dis(1,i) (i : 1~n)，通过对原图的反图跑Dijkstra求出其他所有点到终点的最短距离dis(i,n) (i : 1~n)
- 依次扫描图中每条边，对于某条边(u,v)(边权记为w(u,v))，若dis(1,u)+dis(v,n)+w(u,v) = dis(1,n) 或 dis(1,v)+dis(u,n)+w(u,v) = dis(1,n) 则可判定边(u,v)位于1->n的最短路径上，可以认为这是个充要条件(据d老师所讲)。
投递蔚来等公司10个岗位 >
查看12道真题和解析