本章关键词
最短路径、最优解、动态规划
问题解析
地图软件你一定用过，如果我想从 A 点走到 B 点，只需要输入相应的起止地点，软件就会帮你计算出最短的路径。你有没有想过这个功能是如何实现的？它的底层又是依赖什么算法呢？
算法解析
这个问题比较复杂，我们需要表现力比较强的数据结构支持，这里，毫无疑问我们选择图，我们将一个分岔路口当做一个点，一条路当做一条边，路的行程距离是这条边的权重。综上，我们选择有向有权图这种数据结构。
选择好了数据结构，我们要分析一下使用什么样的算法来实现。先说结论，这个问题适合使用动态规划的思想解决，接下来我们来分析一下我们是如何一步一步确定使用动态规划的：
1.分析模型
任何问题都可以拆分成小问题来解决，如果各个小问题之间的独立性较强，我们使用分治思想；如果各个问题之间有很强的依赖关系，我们需要考虑贪婪、回溯、动态规划的思想。
很明显，一个路径不断延伸的路径就是根据上一步路径扩展而来，这是一个多阶段的决策模型。
对于各个到达终点的路径来说，总存在一个最优路径，所以这个问题存在最优解。
没错，这就是一个多阶段最优解模型，对于这种模型，我们需要选择贪婪、回溯、动态规划的思想，而不能使用分治。
2.特点分析
根据问题的特点，我们可以判断它是否适合用某种思想解决：
贪婪：贪婪最大的特点是需要满足局部最优解可以组成全局最优解，很明显，在这个问题中全局最优解并不一定是局部最优解的组合。所以不能使用贪婪。
回溯：基本上符合多阶段最优解模型的问题就可以使用回溯的思想解决，这个问题也不例外。实际上，我们之前学了两种非常简单且暴力的搜索算法：广度优先搜索 和 深度优先搜索，其中后者就是使用了回溯的思想。但是他的时间复杂度是比较高的。
当然，我们可以考虑使用“剪枝”的技巧减少计算量，这种技巧配合广度优先搜索可以提升一些执行效率。动态规划：动态规划需要问题具备三个特点：重复子问题、最优子结构、无后效性。后者是显而易见的，在这里就不多说了，我们着重聊聊前两个特点。
重复子问题：到达一个点不一定只有一种解法，所以这个问题具有重复子问题的特点。对于有重复子问题的问题，关键是分析同一子问题可能出现的不同状态，并从中选取一个最佳状态。对于这个问题，最佳状态就是使用最小的代价到达这个顶点，对应到求解过程中，就可以剪掉非最小代价的路径。
最优子结构：通过上面的讲解，你已经了解了如何选取最优解，所以自然而然地，你也知道该如何选取子结构的最优解。总结这样的求解过程，我们可以用状态转移方程描述：
min_distance(X) = min( min_distance(X-a) + distance(a->X) ,min_distance(X-b) + distance(b->X)，... )
其中 X 代表目的地，a，b 代表上一个路口，distance(a->X) 代表从 a走到X 的路程。
3.算法实现
知道了如何选择最优状态，知道了状态转移方程，我们就可以很轻松地实现最短路径算法了。这里介绍一个最出名的最短路径算法：Dijkstra算法。
算法就不多解释了，我直接复制专栏作者的话给大家，相信你很容易就能看懂：
首先是定义的结构体（类）的代码：
public class Graph { // 有向有权图的邻接表表示
private LinkedList<Edge> adj[]; // 邻接表
private int v; // 顶点个数
public Graph(int v) {
this.v = v;
this.adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
this.adj[i] = new LinkedList<>();
}
}
public void addEdge(int s, int t, int w) { // 添加一条边
this.adj[s].add(new Edge(s, t, w));
}
private class Edge {
public int sid; // 边的起始顶点编号
public int tid; // 边的终止顶点编号
public int w; // 权重
public Edge(int sid, int tid, int w) {
this.sid = sid;
this.tid = tid;
this.w = w;
}
}
// 下面这个类是为了dijkstra实现用的
private class Vertex {
public int id; // 顶点编号ID
public int dist; // 从起始顶点到这个顶点的距离
public Vertex(int id, int dist) {
this.id = id;
this.dist = dist;
}
}
}
然后是算法实现的代码：
// 因为Java提供的优先级队列，没有暴露更新数据的接口，所以我们需要重新实现一个
private class PriorityQueue { // 根据vertex.dist构建小顶堆
private Vertex[] nodes;
private int count;
public PriorityQueue(int v) {
this.nodes = new Vertex[v+1];
this.count = v;
}
public Vertex poll() { // TODO: 留给读者实现... }
public void add(Vertex vertex) { // TODO: 留给读者实现...}
// 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度O(logn)。
public void update(Vertex vertex) { // TODO: 留给读者实现...}
public boolean isEmpty() { // TODO: 留给读者实现...}
}
public void dijkstra(int s, int t) { // 从顶点s到顶点t的最短路径
int[] predecessor = new int[this.v]; // 用来还原最短路径
Vertex[] vertexes = new Vertex[this.v];
for (int i = 0; i < this.v; ++i) {
vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
}
PriorityQueue queue = new PriorityQueue(this.v);// 小顶堆
boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
vertexes[s].dist = 0;
queue.add(vertexes[s]);
inqueue[s] = true;
while (!queue.isEmpty()) {
Vertex minVertex= queue.poll(); // 取堆顶元素并删除
if (minVertex.id == t) break; // 最短路径产生了
for (int i = 0; i < adj[minVertex.id].size(); ++i) {
Edge e = adj[minVertex.id].get(i); // 取出一条minVetex相连的边
Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
if (minVertex.dist + e.w < nextVertex.dist) { // 更新next的dist
nextVertex.dist = minVertex.dist + e.w;
predecessor[nextVertex.id] = minVertex.id;
if (inqueue[nextVertex.id] == true) {
queue.update(nextVertex); // 更新队列中的dist值
} else {
queue.add(nextVertex);
inqueue[nextVertex.id] = true;
}
}
}
}
// 输出最短路径
System.out.print(s);
print(s, t, predecessor);
}
private void print(int s, int t, int[] predecessor) {
if (s == t) return;
print(s, predecessor[t], predecessor);
System.out.print("->" + t);
}
我们用 vertexes 数组，记录从起始顶点到每个顶点的距离（dist）。起初，我们把所有顶点的 dist 都初始化为无穷大（也就是代码中的 Integer.MAX_VALUE）。我们把起始顶点的 dist 值初始化为 0，然后将其放到优先级队列中。
我们从优先级队列中取出 dist 最小的顶点 minVertex，然后考察这个顶点可达的所有顶点（代码中的 nextVertex）。如果 minVertex 的 dist 值加上 minVertex 与 nextVertex 之间边的权重 w 小于 nextVertex 当前的 dist 值，也就是说，存在另一条更短的路径，它经过 minVertex 到达 nextVertex。那我们就把 nextVertex 的 dist 更新为 minVertex 的 dist 值加上 w。然后，我们把 nextVertex 加入到优先级队列中。重复这个过程，直到找到终止顶点 t 或者队列为空。
以上就是 Dijkstra 算法的核心逻辑。除此之外，代码中还有两个额外的变量，predecessor 数组和 inqueue 数组。
predecessor 数组的作用是为了还原最短路径，它记录每个顶点的前驱顶点。最后，我们通过递归的方式，将这个路径打印出来。打印路径的 print 递归代码我就不详细讲了，这个跟我们在图的搜索中讲的打印路径方法一样。如果不理解的话，你可以回过头去看下那一节。
下面的图展示了算法的具体执行过程：inqueue 数组是为了避免将一个顶点多次添加到优先级队列中。我们更新了某个顶点的 dist 值之后，如果这个顶点已经在优先级队列中了，就不要再将它重复添加进去了。
我自己使用python实现了这个算法，代码比较长，但是写了详细的注释，应该能帮助你理解：
class heap:
def __init__(self, L=[], key=None):
'''
堆的构造函数，这个函数可以将一个列表改造成堆（小顶堆）
:param L: 数据列表，可以为空
:param key: 一个元素中用于表示优先级的值
'''
if key == None: # 如果没有指定优先值，就默认元素为数字，以数字的大小为优先级
self.key = lambda x: x
else:
self.key = key
self.data = [None] + L.copy() # 列表第一项设置为空，使用这种方法可以方便后续计算
# （如l_child = n * 2,r_childd = n * 2 + 1,parent = n // 2 )
self.last_index = len(self.data) - 1
# 这个属性本来是为了简化代码用的，但是后来发现维护这个属性反而很麻烦，但是我又懒得修改代码，所以将就着看吧。
self.creat_heap()
def insert(self, node):
'''
进行插入操作，具体行为：将value放到数组的最后（将value添加为最后一个节点），随后从下往上堆化
:param node: 插入的结点
:return:None
'''
self.data.append(node)
self.last_index = len(self.data) - 1
added = self.last_index
while True:
parent = added // 2
if parent == 0:
break
if self.key(self.data[added]) < self.key(self.data[parent]):
self.data[added], self.data[parent] = self.data[parent], self.data[added]
added = parent
else:
break
def creat_heap(self):
'''
对已有的数据进行建堆，建堆有两种方法：不断插入数据建堆 和 从后往前堆化。
:return:
'''
# 下面是使用插入的方法建堆
# temp = self.data.copy()
# self.data = []
# self.last_index = 1
# self.data.append(temp.pop(0))
# for i in temp:
# self.insert(i)
# 下面是使用从后往前堆化建堆
root = self.last_index // 2 # 这是 第一个元素为空的完全二叉树的性质：最后一个节点(n)的父节点为 n//2
while True:
if root == 0:
break
self.heapify(root)
root -= 1
def heapify(self, x, last=None):
'''
从 x 节点开始进行堆化（从上往下），注意，条件是它的子树已经符合堆的定义
:param x: 节点索引
:return:None
'''
if not last:
last = self.last_index
n = x
while True:
l = n * 2
r = n * 2 + 1
min_index = n
if last >= l and self.key(self.data[l]) < self.key(self.data[n]):
min_index = l
if last >= r and self.key(self.data[r]) < self.key(self.data[min_index]):
min_index = r
if min_index == n:
break
self.data[min_index], self.data[n] = self.data[n], self.data[min_index]
n = min_index
def pop(self):
'''
抛出堆顶元素，具体行为：将堆顶元素抛出，然后将最后一个节点移动放到第一个节点上，随后从第一个节点开始堆化
:return: 堆顶元素
'''
if self.last_index == 0: # 堆为空
return None
elif self.last_index == 1: # 堆只有一个元素
res = self.data.pop()
self.last_index = len(self.data) - 1
return res
else: # 堆有两个及以上元素
res = self.data[1]
self.data[1] = self.data.pop()
self.last_index = len(self.data) - 1
self.heapify(1)
return res
def update(self, vertex, dist):
'''
当到达某个顶点的最小距离更新的时候，使用这个函数对堆更新
:param vertex: 图的节点
:param dist: 到这个图的最小距离
:return: None
'''
# print('进行update，data为',self.data)
for data_index, V_node in enumerate(self.data):
if data_index == 0:
continue
if vertex == V_node.vid:
V_node.dis = dist
self.heapify(data_index)
def isEmpty(self):
if len(self.data) == 1:
return True
else:
return False
class Edge:
'''
描述了一条边
'''
def __init__(self, s, e, w):
self.start = s
self.end = e
self.weight = w
class Vertex:
def __init__(self, vid, dis):
'''
描述了一个顶点
:param vid: 顶点值
:param dis: 到达这个顶点的最短距离，也就是算法分析中的“状态”
'''
self.vid = vid
self.dis = dis
class Graph:
def __init__(self, n):
self.v_list = [[] for i in range(n)] # self.v是一个邻接表,保存的元素为 Edge
def addEdge(self, s, e, w):
'''
添加一条边
:param s: 起点
:param e: 终点
:param w: 权重
:return: None
'''
new_Edge = Edge(s, e, w)
self.v_list[s].append(new_Edge)
def __repr__(self):
return str(self.v_list)
def dijkstra(self, s, e):
'''
dijkstra算法的实现
:param s: 起点
:param e: 终点
:return: None
'''
# 这里我需要初始化一些需要用到的辅助变量
dist_heap = heap([], key=lambda x: x.dis) # 优先队列（小顶堆）
vertex_and_dis = [Vertex(vid, 1024) for vid, edge_list in enumerate(self.v_list)] # 创建一个列表，这个列表用于记录从起始点到该点的距离
predecessor = [None for i in self.v_list] # 记录前驱节点
inqueue = [False for i in self.v_list] # 记录一个点是否进入过队列
start_vertex = vertex_and_dis[s] # 为起点的设置距离，0
start_vertex.dis = 0
dist_heap.insert(start_vertex)
while not dist_heap.isEmpty():
'''
1.从队列中取出一个节点，这个节点的含义：到达 vid 需要 dis 的距离，注意，根据代码逻辑，出队列的 dis 必定是最短距离
2.求这个节点的所有可达节点，求到达这些节点的路径。如果可达节点在队列中，进行update，如果不在，进行添加
3.重复2，直到终点节点出队列
'''
minVertex = dist_heap.pop()
if minVertex.vid == e:
break # 已经到达最终节点
for i in self.v_list[minVertex.vid]: # i 为 minVertex 可以到达的所有节点，即 nextVertex
nextVertex = vertex_and_dis[i.end]
if minVertex.dis + i.weight < nextVertex.dis:#如果可以构成更短的路径，更新节点信息
nextVertex.dis = minVertex.dis + i.weight
predecessor[nextVertex.vid] = minVertex.vid
if inqueue[nextVertex.vid] == True:
dist_heap.update(nextVertex.vid, nextVertex.dis)
else:
dist_heap.insert(nextVertex)
inqueue[nextVertex.vid] = True
self.print_path(predecessor, s, e)
def print_path(self, path, s, e):
'''
输出路径信息
:param path: 记录路径信息的数组
:param s: 起始位置
:param e: 结束位置
:return: None
'''
if e == s: # 到头了
print(e, end='')
return
else:
self.print_path(path, s, path[e])
print('->' + str(e), end='')
if __name__ == '__main__':
g = Graph(6)
g.addEdge(0, 1, 10)
g.addEdge(1, 2, 15)
g.addEdge(2, 5, 5)
g.addEdge(1, 3, 2)
g.addEdge(3, 2, 1)
g.addEdge(3, 5, 12)
g.addEdge(0, 4, 15)
g.addEdge(4, 5, 10)
g.dijkstra(0, 5)
4.复杂度分析
在刚刚的代码实现中，最复杂就是 while 循环嵌套 for 循环那部分代码了。while 循环最多会执行 V 次（V 表示顶点的个数），而内部的 for 循环的执行次数不确定，跟每个顶点的相邻边的个数有关，我们分别记作 E0，E1，E2，……，E(V-1)。如果我们把这 V 个顶点的边都加起来，最大也不会超过图中所有边的个数 E（E 表示边的个数）。for 循环内部的代码涉及从优先级队列取数据、往优先级队列中添加数据、更新优先级队列中的数据，这样三个主要的操作。我们知道，优先级队列是用堆来实现的，堆中的这几个操作，时间复杂度都是 O(logV)（堆中的元素个数不会超过顶点的个数 V）。
所以，综合这两部分，再利用乘法原则，整个代码的时间复杂度就是 O(E*logV)。
总结
这个算法的思想来源于动态规划，所以在这里，我想结合动态规划聊一聊感想：
- 能否使用动态规划，要看他是否符合一个模型，三个特点
- 动态规划存在最优解，这个最优解就是最理想的状态，在规划到不同阶段时，都会有不同的状态，选择最理想状态是获取最优解的关键
- 根据动态规划的最优解，和它的子问题，可以得出状态转移公式。
- 有了状态转移公式，你可以从前往后构造状态转移表，或者根据状态转移公式从后向前推导。当然，这不是绝对的，但是不论怎样，在使用动态规划中你必须要注意状态转移 和 转移公式！！！
- 由于不知道哪个执行状态最终能构成最优解（或子问题的最优解），所以我们必须保持这些未知状态，只有遇到重复子问题的时候，才可以根据最优原则进行剪枝。
- 在Dijkstra算法中，最有趣的是那个作为辅助变量的优先级队列。堆可以很快速地求得最大值（最小值），而动态规划中的最优解常常是状态值最大（最小）。这可以为动态规划算法的变形提供思路。
以上就是最短路径算法的全部内容，希望你能够有所收获
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间
