太久没写算法了，最短路径都全忘了，开个坑，今天晚点再整理。主要算法应该是Dijkstra，Bellman-Ford以及SPFA算法。
最短路径算法是图论中的基础算法之一，其中分为单源最短路径算法以及所有点之间的最短路径算法。其中单源最短路径算法是求图中任意两个顶点之间的最短路径。
单源最短路径算法比较常用的算法包括Dijkstra算法，Bellman-Ford算法以及SPFA算法，而所有点中的最短路径算法一般常用的是Floyd算法。
Dijkstra算法
Dijkstra算法主要的思想是贪心。算法的大致流程如下：
- 第一步：把所有节点标记为未访问。建立一个簇，用于储存所有未访问的节点，记为unvisited set。
- 第二步：设置每个节点的distance。把源点的值设为0，其他点设为正无穷。该distance的含义实际上为该点到源点的距离。把源点设为当前节点。
- 第三步：对于当前节点，寻找其所有未被访问的邻居，然后计算这些节点的distance。比较新的distance与原来该节点的distance，并取小值。
- 第四步：把当前节点设为已访问。
- 第五步：检查剩下的未访问节点。如果所有剩下的节点都已访问或者剩下的所有节点的距离都是正无穷，则停止搜索。否则把未访问节点中到源点距离最短的节点设为新的当前节点，并且回到第三步。
伪代码（未经过堆优化）：
function Dijkstra(Graph, source):
for each vertex v in Graph.Vertices:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u still in Q:
alt ← dist[u] + Graph.Edges(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]时间复杂度：$O(|V^2|)$，其中每个点需要遍历一次，而对于每一个点的遍历需要$(V-k)\times 2$次循环来找到所有剩余点到源点的最短距离，其中$k$是已经访问过的节点数量。因此最后的时间复杂度为$O(V*(V-k)\times 2)=O(V^2)$。
如果使用堆优化，则其中时间复杂度可以有所下降，可以降为$O((|V|+|E|)log|V|)$。
Bellman-Ford算法
Bellman-Ford算法实际上比Dijkstra算法要慢，不过其有点在于能够用于处理负权回路。
Bellman-Ford算法的核心是“松弛”操作。“松弛”的意思是修正两个点之间的最短距离，使得两点之间的距离能够最终达到最小。而Bellman-Ford算法的整体就是由多次“松弛”操作来完成的。
时间复杂度：$O(|V|\cdot|E|)$。
伪代码：
function BellmanFord(list vertices, list edges, vertex source) is
// This implementation takes in a graph, represented as
// lists of vertices (represented as integers [0..n-1]) and edges,
// and fills two arrays (distance and predecessor) holding
// the shortest path from the source to each vertex
distance := list of size n
predecessor := list of size n
// Step 1: initialize graph
for each vertex v in vertices do
distance[v] := inf // Initialize the distance to all vertices to infinity
predecessor[v] := null // And having a null predecessor
distance[source] := 0 // The distance from the source to itself is, of course, zero
// Step 2: relax edges repeatedly
repeat |V|−1 times:
for each edge (u, v) with weight w in edges do
if distance[u] + w < distance[v] then
distance[v] := distance[u] + w
predecessor[v] := u
// Step 3: check for negative-weight cycles
for each edge (u, v) with weight w in edges do
if distance[u] + w < distance[v] then
// Step 4: find a negative-weight cycle
negativeloop := [v, u]
repeat |V|−1 times:
u := negativeloop[0]
for each edge (u, v) with weight w in edges do
if distance[u] + w < distance[v] then
negativeloop := concatenate([v], negativeloop)
find a cycle in negativeloop, let it be ncycle
// use any cycle detection algorithm here
error "Graph contains a negative-weight cycle", ncycle
return distance, predecessor
上面的算法中，其中$|V-1|$次的遍历是用于找到最短路径，而第$|V|$次的遍历则是用于判断整个图中是否存在负权回路。因为如果没有负权回路出现，理论上前$|V|-1$次的循环中，已经能够完成单源最短路径的查找。而此时如果还能够继续松弛，则说明其中出现了负权回路。
Shortest Path Faster Algorithm(SPFA)算法
SPFA算法的思想实际上类似于广度优先搜索。相比于Bellman-Ford算法中对于所有边进行松弛的操作，SPFA算法则是维护了一个队列，仅当进行松弛操作的时候，一个顶点到源点的距离被更新之后，才会把新顶点加入队列（如果其原本不在）并且进行更新。其算法的伪代码如下：
procedure Shortest-Path-Faster-Algorithm(G, s)
for each vertex v ≠ s in V(G)
d(v) := ∞
d(s) := 0
push s into Q
while Q is not empty do
u := poll Q
for each edge (u, v) in E(G) do
if d(u) + w(u, v) < d(v) then
d(v) := d(u) + w(u, v)
if v is not in Q then
push v into Q其最差的时间复杂度与Bellman-Ford一致，为$O(|V|\cdot|E|)$，不过经过实践，对于随机图，其平均的时间复杂度接近于$O(|E|)$。而对于稀疏图，于Bellman-Ford类似，其能够有时间复杂度$\Omega(|V|^2)$。
//算法的正确性还在鸽子中，稍后再进行补充