图论：最短路算法有哪些以及它们的比较?
人气：490 ℃ 时间：2020-04-16 20:11:17
解答
弗洛伊德 n^3 的时间把n个点两两的最短路求出来
迪杰斯特拉 n^2的时间(用堆优化到Nlog(M),M是边数),单源最短路,但是不能对付有负权的图
SPFA,M*k的时间（K是一个常数）,单源最短路,能对付有负权的图
感觉常用的就这三个了吧.
推荐
猜你喜欢
- “省会”与“省悟”的“省”读什么读音
- 甲乙两架飞机从同一机场起飞,向同一个方向飞行,甲机比乙机早开出0.2小时,甲机的速度是870千米,乙机
- That way of speaking is _____ people in this part of the country．
- 已知点P在x轴上,它与点Q(0,4)的距离恰好等于它与点B(11,6)距离的一半,求点P的坐标
- 要详细一点,长一点,最好至少有250字
- 第一宇宙速度,第二宇宙速度
- H2O+Na=?
- 张大爷和王大爷两人每天早晨都按时起床出门散步,两人相向而行,张大爷每分行35米,王大爷每分钟行25米,
