图论算法

算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，但因为它实践中的效果不错，仍不失为一个很实用的算法。

4)菜鱼有话说：

这个N久前有人提出个叫“SPFA”的东西，主要思想是：维护一队列，对队头的顶点u，枚举它的邻接边，如果它可以用来更新顶点v，则更新v的dis。更新后，如果顶点不在队中，则加入队。重复，直至队列空。有人说这个算法是O(kE)，k平均为2。看完算法的描述，我直观上就感觉这是bellman-ford的一种实现方式，但无奈没有证据，在与Zroge和Amber的讨论中没有能说明。但是，偶尔翻起一本书《Data structures and Algorithm analysis》，终于确定所谓SPFA就是Bellman-Ford（如果以上算法描述的确是SPFA的描述的话）。如有怀疑可以参考此书，网上有CHM电子书。既然是Bellman-Ford，它的算法复杂度就是O(VE)。而实际上，对于这个所谓“SPFA”是可以很轻易构造出使它复杂度为VE的例子的（有负权回路即可）。

以上为我个人说法，有不同观点可以讨论。

4、Topological Sort(拓扑排序)

1) 适用条件&范围：

a) AOV网(Activity On Vertex Network);

b) 有向图;

c) 作为某些算法的预处理过程(如DP)

2)算法描述：

很简单的算法：每次挑选入度为0的顶点输出(不计次序)。

如果最后发现输出的顶点数小于|V|，则表明有回路存在

3) 算法实现：

a) 数据结构： adj:邻接表;有4个域{u,v,w,next}

indgr[i]:顶点i的入度;

stack[]:栈

b) 初始化:top=0 (栈顶指针)

c) 将初始状态所有入度为0的顶点压栈

d) I=0 (计数器)

e) While 栈非空(top>0) do

i.顶点v出栈；输出v；计数器增1；

ii For 与v邻接的顶点u do

1. dec(indgr[u]);

2. If indgr[u]=0 then 顶点u入栈

f) EXIT(I=|V|)

简单&高效&实用的算法。上述实现方法复杂度O(V+E)

5、SSSP On DAG

1) 适用条件&范围：

a) DAG(Directed Acyclic Graph,有向无环图);

边权可正可负

2)算法描述：

a) Toposort;

b) If Toposort=False Then HALT(Not a DAG)

c) For 拓扑序的每个顶点u do

For u的每个邻接点v do

Relax(u,v,w);