判断某边是否在图中给定两点间的最短路径上(结论)

由于图中给定两点(假设为No.1 & No.n)间的最短路径不止一条,但可以确定一定是简单通路,因此存在一个较为标准的方法找出在1->n的最短路径的所有边:
  1. 通过对原图跑Dijkstra求出原点到其他所有点的最短距离dis(1,i) (i : 1~n),通过对原图的反图跑Dijkstra求出其他所有点到终点的最短距离dis(i,n) (i : 1~n)
  2. 依次扫描图中每条边,对于某条边(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老师所讲)。

全部评论

相关推荐

用微笑面对困难:你出于礼貌叫了人一声大姐,大姐很欣慰,她真把你当老弟
点赞 评论 收藏
分享
11-11 16:40
已编辑
门头沟学院 人工智能
不知道怎么取名字_:这个有点不合理了,相当于已经毕业了,但还是没转正,这不就是白嫖
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务