最短路径法与节约法的区别

最短路径法与节约法的区别：含义不同，计算不同。

一、含义不同：在这里启发式指的是一个在一个搜寻树的节点上定义的函数h(n)，用于评估从此节点到目标节点最便宜的路径。启发式通常用于资讯充分的搜寻算法，例如最好优先贪婪算法与a*。

路径指的是实现查找的方法或算法，而树是把算法变化成可见的结构图。可以理解成树是文章的结构，路径是完成一篇作文的语句。

二、计算不同：最好优先贪婪算法会为启发式函数选择最低代价的节点；a*则会为g(n)+h(n)选择最低代价的节点，此g(n)是从起始节点到目前节点的路径的确实代价。

最短路径是一个路径，最小树是一个树（支撑树），虽然二者都是要求覆盖每一个节点，但是路径和树究竟不同，后者分叉前者不分叉。

SPFA算法

可以用于存在负数边权的图，这与dijkstra算法是不同的。与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。

在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。