一．SPFA的深度优先实现及其优化
【基于Dfs的SPFA的基本原理】回忆之前的SPFA算法，由于采用广度优先的思想，每当我们扩展出一个新的节点，总是把它放到队列的末尾。而实际上如果采用深度优先的思想，算法的实现方式可以改成不断从新节点往下递归进行求解。而对于负环的判断则显得更为简单，因为假如存在负环a1->a2->….ak->a1，那么算法运行时，会从某个点a1开始Dfs，最后又回到了这个点。所以只需用一个辅助数组记录当前节点是否在递归栈中便可及时检测出负环。
【伪代码】
1.Void SPFA(Node) { //当前搜到Node
2. Instack[Node]=true; //设当前节点在递归栈中
3. For (Node,v) ∈E //枚举出边
4. If dis[Node]+edge(Node,v)<dis[v] then {
5. dis[v]=dis[Node]+edge(Node,v);
6. If not Instack[v] then
7. SPFA(v);
8. Else{ //若v点已在递归栈中，则出现负环
9. Return;
10. }
11. }
12. Instack [Node] =false; //将当前节点退栈
13.}
我们发现，一般情况下广度会有很大的优势。Dfs往往由于不断盲目地迭代而耗费了太多时间甚至远远超过时间的限制。
【基于Dfs的SPFA的相关优化】我们考虑网络流使用贪心初始流进行优化的方法，因为当前解的优劣程度对之后的迭代有很大影响。而且Dfs的低效很大程度上是因为频繁地使用较次解去更新大片的元素。由此我们可以考虑先在第一次Dfs时，对扩展节点采取一些限制以快速求得一个较优解，然后再进行第二次完整的Dfs。最终，我们得出一种不错的贪心初始解方法，即对于每个节点只更新一条边后便退出。
【伪代码】
1.bool SPFA_Init(Node){
2. For (Node,v) ∈E
3. If dis [Node] +edge (Node, v) <dis[v] {
4. Dis[v] =dis [Node] +edge (Node, v);
5. SPFA_Init(v);
6. Return true;
7. }
8. Return false;
9.}
10.Main {
11. For Node∈V
12. While SPFA_Init(Node);
13. For Node∈V
14. SPFA (Node)
15.}
分析Bfs与Dfs的不同，可以发现Bfs的优势主要体现在某个点出队前可能再次被更新而得到更优的解进行下一次迭代。而Dfs往往会用一个次解进行层次很深的迭代(一个次解会导致O(N)级别的更新)。
由此，可以联想到深度优先搜索的一个改进版本：迭代加深搜索，结合前面贪心初始解的原理，我们可以通过限制节点递归的深度并逐步放宽限制求解。加入这个优化后，总体还是比Bfs略逊一筹，但差距已不大。值得注意的是：对深度限制的不同，时间效率也有差异，以下总结出了两种效果相对不错的限制方法：
- 1 依次设置深度上限为1,2,4,8,16,32,64…..2k….. maxlongint
- 2 依次设置深度上限为20，30，40，50，60，80，100….maxlongint