Floyd 和 Dijkstra 算法

弗洛伊德算法很简单,疯狂试试就出来了

这个狄克斯特拉就得慢慢找了…

这是Floyd


这是Dijkstra

分析一下这个Dijkstra

先说说这个 Dijkstra ,书上说的所谓“松弛”,其实就是某个点可以用来当中转站这个意思。先找最小的,再以这个最小的点作为中转站然后去扩展(或者说是去“努力”到达【因为可能并不能通过这个点去到达其他点】)其他的点。

这个算法是基于贪心算法而来的,就是说我一直选离我最近的点且保证松弛以后其他点不会离我更近。因此出现负边权就用不了了, 因为每次选取的是当前最短的边进行松弛,当边都是正权时,松弛后边权一定比当前最短边大,所以满足贪心的条件,有了负边后后续的松弛会出现比前边小的情况,不满足贪心的条件所以不能用 Dijkstra 计算带有负边的单源最短路。

总结

1.Floyd 空间复杂度为 N^2 时间复杂度为 N^3

2.Dijkstra 空间复杂度为 M 时间复杂度为 (M+N)logN

分类….

发布者

我乃堂堂SCUT的一条咸鱼!

发表评论

电子邮件地址不会被公开。 必填项已用*标注