作业帮关于Dijkstra、SPFA、Bellman-Ford、Floyed算法的问题总觉得这几个算法的基本框架都差不多,都看重 v[i]>=v[j]+g[i,j] 这个不等式,SPFA是队列优化的Bellman-Ford,但我觉得SPFA如果不用邻接表用起来好像也就
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/05 15:03:45
![关于Dijkstra、SPFA、Bellman-Ford、Floyed算法的问题总觉得这几个算法的基本框架都差不多,都看重 v[i]>=v[j]+g[i,j] 这个不等式,SPFA是队列优化的Bellman-Ford,但我觉得SPFA如果不用邻接表用起来好像也就](/uploads/image/z/12687087-39-7.jpg?t=%E5%85%B3%E4%BA%8EDijkstra%E3%80%81SPFA%E3%80%81Bellman-Ford%E3%80%81Floyed%E7%AE%97%E6%B3%95%E7%9A%84%E9%97%AE%E9%A2%98%E6%80%BB%E8%A7%89%E5%BE%97%E8%BF%99%E5%87%A0%E4%B8%AA%E7%AE%97%E6%B3%95%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%A1%86%E6%9E%B6%E9%83%BD%E5%B7%AE%E4%B8%8D%E5%A4%9A%2C%E9%83%BD%E7%9C%8B%E9%87%8D+v%5Bi%5D%3E%3Dv%5Bj%5D%2Bg%5Bi%2Cj%5D+%E8%BF%99%E4%B8%AA%E4%B8%8D%E7%AD%89%E5%BC%8F%2CSPFA%E6%98%AF%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96%E7%9A%84Bellman-Ford%2C%E4%BD%86%E6%88%91%E8%A7%89%E5%BE%97SPFA%E5%A6%82%E6%9E%9C%E4%B8%8D%E7%94%A8%E9%82%BB%E6%8E%A5%E8%A1%A8%E7%94%A8%E8%B5%B7%E6%9D%A5%E5%A5%BD%E5%83%8F%E4%B9%9F%E5%B0%B1)
关于Dijkstra、SPFA、Bellman-Ford、Floyed算法的问题总觉得这几个算法的基本框架都差不多,都看重 v[i]>=v[j]+g[i,j] 这个不等式,SPFA是队列优化的Bellman-Ford,但我觉得SPFA如果不用邻接表用起来好像也就
关于Dijkstra、SPFA、Bellman-Ford、Floyed算法的问题
总觉得这几个算法的基本框架都差不多,都看重 v[i]>=v[j]+g[i,j] 这个不等式,SPFA是队列优化的Bellman-Ford,但我觉得SPFA如果不用邻接表用起来好像也就跟Dijkstra差不多.
痛苦啊,迷茫啊.神牛快来丫.总觉得这几个差不多.如果是NOIP提高组,需要掌握的有什么?
关于Dijkstra、SPFA、Bellman-Ford、Floyed算法的问题总觉得这几个算法的基本框架都差不多,都看重 v[i]>=v[j]+g[i,j] 这个不等式,SPFA是队列优化的Bellman-Ford,但我觉得SPFA如果不用邻接表用起来好像也就
bellman-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提高组多练搜索,学会动态规划差不多了,其他的模拟提都简单,主要是多练题
纯手打