有向无回路图的最短路径和拓扑排序

xiaoxiao2021-02-28  3

先要了解无回路

就是这种形式的

所以如果没有这种形式的东西 就可以得出一个线性的图

这就是拓扑排序做的事了

得到这样一个图以后,就可以利用松弛技术了,只需要遍历每个点,再松弛每个点所指向的点的那条边即可。时间复杂度奇低

转载请注明原文地址: https://www.6miu.com/read-2050328.html

最新回复(0)