神马作文网关于Dijkstra、SPFA、Bellman-Ford、Floyed算法的问题
来源：学生作业帮 编辑：神马作文网作业帮 分类：数学作业 时间：2024/11/13 00:29:59
关于Dijkstra、SPFA、Bellman-Ford、Floyed算法的问题
总觉得这几个算法的基本框架都差不多,都看重 v[i]>=v[j]+g[i,j] 这个不等式,SPFA是队列优化的Bellman-Ford,但我觉得SPFA如果不用邻接表用起来好像也就跟Dijkstra差不多.
痛苦啊,迷茫啊.神牛快来丫.总觉得这几个差不多.如果是NOIP提高组,需要掌握的有什么?
总觉得这几个算法的基本框架都差不多,都看重 v[i]>=v[j]+g[i,j] 这个不等式,SPFA是队列优化的Bellman-Ford,但我觉得SPFA如果不用邻接表用起来好像也就跟Dijkstra差不多.
痛苦啊,迷茫啊.神牛快来丫.总觉得这几个差不多.如果是NOIP提高组,需要掌握的有什么?
ellman-ford可以有负权,但不能有负权回路,
spfa是bellman-ford的队列优化,时间发咋度o（ke）,其中k为所有顶点进队的平均次数,可以证明k一般小于等于2.
dijkstra不可以有负权,但效率比bellman-ford快,o（2n次方）,用二叉堆优化o((m+n)log n),斐波纳契堆能稍微提高一些性能,让算法运行时间达到o(m + n log n).
floyed算每对顶点之间的最短路,前几个是单源的
noip提高组多练搜索,学会动态规划差不多了,其他的模拟提都简单,主要是多练题
纯手打
spfa是bellman-ford的队列优化,时间发咋度o（ke）,其中k为所有顶点进队的平均次数,可以证明k一般小于等于2.
dijkstra不可以有负权,但效率比bellman-ford快,o（2n次方）,用二叉堆优化o((m+n)log n),斐波纳契堆能稍微提高一些性能,让算法运行时间达到o(m + n log n).
floyed算每对顶点之间的最短路,前几个是单源的
noip提高组多练搜索,学会动态规划差不多了,其他的模拟提都简单,主要是多练题
纯手打