证明在图中边权为负时，Dijkstra 算法不能正确运行。

[问答题]

段班宇

若允许边上带有负权值，有可能出现当与S（已求得最短路径的顶点集，归入S内的结点的最短路径不再变更）内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度，而此时a在Dijkstra算法下是无法更新的。

发表于 2019-12-05 13:07:14 回复(0)

提交观点

问题信息

上传者：小小

难度：

1条回答 0收藏 1000浏览

扫一扫，把题目装进口袋