一、最短路径问题
最短路径问题是一个基于开销的图搜索问题，指求解从图中的某一节点出发到达另一个节点经过所有边的开销和最小的路径。解决该问题的算法有：
- Dijkstra算法
- A*算法
- SPFA算法
- Floyd算法
二、SPFA
概述
和Dijkstra算法一样，SPFA也是用于解决图的单源最短路径问题，它是Bellman-Ford算法的改良版本。相比于Dijkstra算法，其优点是可以处理权值为负的图，缺点是时间复杂度比Dijkstra高，高达O(VE)。
思路
和Dijkstra类似，首先我们需要记录已经找到最短路径的节点以及待优化的节点。
不同点在于，Dijkstra算法运用了贪心的思想，每次从待优化节点中取出开销最小的节点，进入下一次循环；而SPFA算法采用的是动态规划的思想，使用一个队列保存待优化的节点，每一次循环取出队首节点P，并对该节点相邻的节点进行松弛操作，对于某一个相邻节点Q，若进行了松弛，且P不在队列中，则P节点会加入到队列中。这样不断循环直至队列为空。
- 需要注意的是若图中存在负环，则算法会进入死循环，因此需要对负环进行判断，只需要记录每个点进入队列的次数，若次数超过图的顶点数，则存在负环。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| public static class SPFA<T>
{
private class Distance
{
public float value = float.MaxValue;
public int times;
public List<Node<T>> path = new List<Node<T>>();
}
public static List<Node<T>> SPFASearch(Graph<T> graph, Node<T> start, Node<T> end)
{
if (graph == null || start == null || !graph.IsNode(start)) return new List<Node<T>>();
Dictionary<Node<T>, Distance> dis = new Dictionary<Node<T>, Distance>();
Queue<Node<T>> queue = new Queue<Node<T>>();
foreach (var vn in graph)
{
dis[vn.Data] = new Distance();
}
dis[start].value = 0;
dis[start].times++;
queue.Enqueue(start);
while (queue.Count > 0)
{
Node<T> fNode = queue.Dequeue();
var adjNode = graph[fNode].FirstAdjNode;
while (adjNode != null)
{
var d = dis[adjNode.Data];
if (adjNode.Cost + dis[fNode].value < d.value)
{
d.value = adjNode.Cost + dis[fNode].value;
d.path = new List<Node<T>>(dis[fNode].path) {fNode};
if (!queue.Contains(adjNode.Data))
{
if (dis[adjNode.Data].times > graph.NodeNum)
{
Debug.LogError("图中存在负环，无最短路径！");
return new List<Node<T>>();
}
dis[adjNode.Data].times++;
queue.Enqueue(adjNode.Data);
}
}
adjNode = adjNode.Next;
}
}
if (dis[end].path.Count > 0) dis[end].path.Add(end);
return dis[end].path;
}
}
|
优化
和Dijkstra算法类似，我们优化的切入点也是待优化节点的数据结构，在Dijkstra算法中我们采用优先队列进行优化，而SPFA也可以用类似的思想来提高队列中节点排列的质量，从而提升平均性能（无法提升最坏情况下的性能），优化方法主要有SLF和LLL，都是通过调整队列中元素的顺序使得更靠近源节点的节点能够被更早地处理，两种方法可以结合。
SLF (Small Label First)
此优化针对队列加入节点时。使用双端队列实现，在节点加入队列时，判断待加入节点和队首节点的路径开销，若待加入节点的路径开销较小，则加入到队首，否则加入到队尾。
LLL(Large Label Last)
此优化针对的则是节点出队时，出队时需要比较队首节点的路径开销和队列中所有节点的路径开销平均值，若小于则正常出队，否则将出队节点加入到队尾，继续判断下一个队首节点，直到找到符合条件的节点。
DFS优化
DFS优化主要在找负环上有优势，由于原始算法使用的是BFS的思想，不会在某一条路径上持续深入，因此需要当一个节点被加入队列N(节点总是)次后才知道图中存在负环，而DFS只需要一个节点出现两次以上，就知道存在负环，因此可以避免大量的遍历。
参考资料：
Demo地址：https://github.com/Luciano-0/Graph.git