最短路变形加法换成乘法求连续相乘最短路与最长路总结

﹏ヽ暗。殇╰゛Y 2022-10-22 07:43 140阅读 0赞

### 乘法最短路问题 ###

普通的最短路问题是将路径上的所有边的权值相加，求最小权值和的一条路。但这里的变形是将加法换成乘法，求最小权值积的一条路。这里我们可以用[dijkstra][]或[spfa][]来做，只是将加号换成乘号即可。  
我们的更新语句就是：

if(dis[v] > dis[u] * w[i])	//v是循环的点，u是上一次被修改过的点
    { 
    	dis[v] = dis[u] * w[i];
    }

注：这里保证所有**边的权值都是非负数**，因为一旦出现负数，相乘之后最小值会变成最大值，最大值会变成最小值，就非常难了，需要同时维护最小值和最大值，普通的最短路问题很难解决，所以这里不包含负数。

**证明：** 为什么将加号变成乘号后最短路问题依旧适用呢？  
我们可以将这个问题做一个转换，转化到加法问题，就可以证明乘法依旧适用了，所以我们给乘法问题取一个以e为底的对数： ln ⁡ ( w 1 × w 2 × . . . × w n ) = ln ⁡ w 1 + ln ⁡ w 2 + . . . + ln ⁡ w n \\ln \{(w\_1\\times w\_2 \\times ... \\times w\_n)\} = \\ln w\_1 + \\ln w\_2 + ...+\\ln w\_n ln(w1×w2×...×wn)=lnw1\+lnw2\+...\+lnwn而ln函数就是一条单调递增的函数，所以 ln ⁡ w 1 + ln ⁡ w 2 + . . . + ln ⁡ w n \\ln w\_1 + \\ln w\_2 + ...+\\ln w\_n lnw1\+lnw2\+...\+lnwn的最大值就是 w 1 + w 2 + . . . + w n w\_1 + w\_2+...+w\_n w1\+w2\+...\+wn的最大值。  
![ln][]

### 乘法最长路问题 ###

和上面的问题一样，只是要求一条相乘后权值积最大的一条路。这里就需要分成两种情况来看了。  
**一、** 所有**边权值都在0和1之间**，乘的都是小数，这里我们可以用dijkstra和spfa，将加号变成乘号，大于变成小于即可。

if(dis[v] < dis[u] * w[i])
    { 
    	dis[v] = dis[u] * w[i];
    }

**二、** 所有**边的权值只保证非负数**，而不一定小于1，这里只能用spfa，而不能用dijkstra  
因为当权值为正数时，我们每次不一定能确定最远的一个就是最大值，因为他还会乘一个正数遍得更大，所以dij是不行的，而如果保证权值都是在0和1之间的话，那就能确定最远的一个就是最大值了，因为他再乘一个小数就会变小，所以可以用dij。

[dijkstra]: https://blog.csdn.net/qq_45735851/article/details/106564326
[spfa]: https://blog.csdn.net/qq_45735851/article/details/107517718
[ln]: /images/20221022/a203653e997a45b4bdae414a1d09014a.png