偶然想到的,不敢保证正确性。
dijkstra算法可以看作对w[ ]组成的集合,做二元运算,去更新dist数组。
dijkstra可以成立的充要条件
1.w[ ]和二元运算 * 得严格满足含幺半群,同时定义w[ ]的比较关系是全序关系。
2.以“最短”路径为例,要求任取w[ ] > 单位元,“最长”路径,要求任取w[ ] < 单位元。
3.在算法初始化时,dist[1] = 单位元,其余按照需要修改即可。
以1126. 最小花费为例
这个问题中0 < w[ ] < 1,且1是乘法的单位元,可以用dijkstra求得最长路。
反之如果w[ ] > 1,可以用dijkstra求得最短路。