模板

代码

适用范围

• 不能处理负权边或环
  • 原因：Dijkstra算法当中将节点分为已求得最短路径的集合（记为P）和未确定最短路径的集合（记为Q），归入P集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与P内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度，但是a在Dijkstra算法下是无法更新的，由此便可能得不到正确的结果。

典型题目

• leetcode 5836

思考

• 如何计算两点之间的最短路径数？