单源最短路径-Dijkstra算法实现
记得以前学数据结构时，死活没有搞懂最短路径算法，书本上各种概念讲一大堆，没过两天全给忘了，更不用说手写一个最短路径算法出来。写这篇文章，旨在让一个算法小白能轻松的手写该算法出来。
1. 什么是单源最短路径？
首先，先简单介绍一下什么是单源最短路径。一个图(Graph)由很多顶点(Vertex)构成，顶点与顶点之间相连构成边(Edge)，每条边都有权重(Weight)，从某个起点开始到某个终点，经过的所有路径的权重和加起来最小，这个路径叫做单源最短路径。
可以想象成一副地图，从你家里到公司上班，地图导航会帮你规划出一个耗时最少的最短路径。家、公司相当于图中的两个顶点，经过每条道路时的耗时相当于边的权重。
举个例子：
这是一个有向图，共有 6 个顶点，连接2个顶点的是边，边上的数字就是权重。那么问题来了，怎么求出从顶点 v0 到其他各个顶点的最短路径？比方说从 v0->v1的路径有好几条：v0->v1: 100、v0-v2-v1: 90、v0-v4-v3-v1: 70、v0-v2-v3-v1: 60，可以发现v0-v2-v3-v1这条路径是最短的，其权重加起来只有 60，因此v0-v2-v3-v1这就是从顶点 v0 到顶点 v1 的最短路径。
2. 图的表示
图的存储有 2 种方式：一种是邻接矩阵，用一个二维数组来表示，例如 a[i][j] 表示顶点 i 与顶点 j 之间的边的权重值，但是如果顶点之间的边比较少，就会形成稀疏矩阵，浪费存储空间；另一种是邻接表，用一个数组来表示顶点，每个数组里存储的是从该顶点可达的顶点的数据集合信息，我们采用这种方式来表示图：
//图的顶点编号都从 0 开始
class MapGraph(val size: Int) {
/**
* 图中的边，这是一个带权图
*
* @param sv 起始顶点
* @param ev 终止顶点
* @param weight sv->ev的权重
*/
class Edge(var sv: Int, var ev: Int, var weight: Int)
//我们采用邻接表来存储顶点和边，节省内存空间
//顶点编号从 0 开始，adjArray[i] 表示与编号为 i 的顶点相连的顶点以及边的信息
private val adjArray = Array<MutableMap<Int, Edge>>(size) {
mutableMapOf()
}
/**
* 添加边
* @param sv 起始顶点
* @param ev 终止顶点
* @param weight 权重
*/
fun addEdge(sv: Int, ev: Int, weight: Int) {
var edge = Edge(sv, ev, weight)
adjArray[sv][ev] = edge
}
}
3. Dijkstra 算法
大名鼎鼎的Dijkstra算法是根据发明者的名字来命名的，其实看原算法分析，初学者真的很难理解，即便搞懂之后，保证过不了几天，基本上又忘记是咋回事了。
学习算法，不能死记硬背代码的写法，以前比较容易进入这种误区，结果就是几天之后全给忘了。Dijkstra算法的核心思想有以下几点，都是用我自己的理解来总结的，虽然网上都有完整的定义，但我们总是力求简单明了好理解，适合自己就行：
- 首先定义 2 个集合：S、U，S 是已求出最短路径的顶点集合(包含顶点信息以及最短路径值)，U 是未求出最短路径的顶点集合；
- 刚开始时，S 中只有一个顶点就是起始顶点，因为它到自己本身的最短路径为 0，并且这肯定是最短路径。将其当做目标顶点，将目标顶点与其直接相邻的顶点放在 U 中，不直接可达的我们认为其路径值为无穷大；
- 找出 U 中路径值最小的顶点，从 U 中移除并放入 S 中，同样将其叫做目标顶点。遍历目标顶点所有相邻的顶点，计算直接从该目标顶点到邻接顶点的路径值，如果邻接顶点在集合 U 中不存在则直接放入 U 中，如果 U 中已存在则比较新的路径值与原路径值，最终将邻接顶点的路径值更新为较小的值；
- 重复步骤 3 直到找到目标顶点或者没有找到退出循环；
以前面那个图为例，我们来求从顶点 v0 到顶点 v1 的最短路径。
代码如下(kotlin实现)：
/**
* @param v 顶点编号
* @param dist 起始顶点到该顶点的距离
*/
inner class VertexDist(var v: Int, var dist: Int)
/**
* @param sv 起始顶点编号
* @param end 目标顶点编号
* @return
*/
fun dijkstra(sv: Int, end: Int): Int {
if (sv == end) {
return 0
}
//集合s，这里的每个顶点，都已经计算出从起始顶点到该顶点的最短路径
var s = mutableListOf<VertexDist>()
//集合u，暂时记录当前能计算出的最短路径，但不一定是最短路径
var u = mutableMapOf<Int, VertexDist>()
//记录前驱节点
var predecessor = mutableMapOf<Int, Int>()
//BaseCase: 起始顶点自己到自己的距离肯定为 0
s.add(VertexDist(sv, 0))
//BaseCase：与其相邻直接可达的顶点放入集合 U 中
for (edge in adjArray[sv].values) {
u[edge.ev] = VertexDist(edge.ev, edge.weight)
predecessor[edge.ev] = edge.sv
}
while (u.isNotEmpty()) {
//从集合 u 中找出路径值最小的顶点 minVertex 放入集合 s 中
var minVertex = findMinVertex(u)
u.remove(minVertex.v)
s.add(minVertex)
//如果已经找到目标顶点
if (minVertex.v == end) {
//打印最短路径
var list = mutableListOf<Int>()
var curr = minVertex.v
list.add(curr)
while (predecessor[curr] != null) {
curr = predecessor[curr]!!
list.add(curr)
}
list.reverse()
for (i in list.indices) {
print("${list[i]}${if (i < list.size - 1) "->" else ""}")
}
println()
return minVertex.dist
}
//更新能通过顶点 minVertex 到达的所有顶点最小路径值
var nextVertexes = adjArray[minVertex.v]
for (edge in nextVertexes.values) {
var tmpDist = minVertex.dist + edge.weight
//顶点不在集合 u 中，则加入
if (u[edge.ev] == null) {
u[edge.ev] = VertexDist(edge.ev, tmpDist)
predecessor[edge.ev] = edge.sv
} else {
//顶点已经在集合 u 中了，如果经过 minVertex 到达该顶点的路径值更小，则更新
if (tmpDist < u[edge.ev]!!.dist) {
u[edge.ev]!!.dist = tmpDist
predecessor[edge.ev] = edge.sv
}
}
}
}
println("没有可达的路径")
return Int.MAX_VALUE
}
//找出路径值最小的顶点
private fun findMinVertex(map: Map<Int, VertexDist>): VertexDist {
var tmp: VertexDist? = null
for (vertex in map.values) {
if (tmp == null || vertex.dist < tmp.dist)
tmp = vertex
}
return tmp!!
}
上面代码中有个问题，findMinVertex 方法需要遍历查找所有的顶点，其时间复杂度为 O(n)，效率会比较低，那么有没什么好的方式呢？我们以前学过堆这个概念，对堆元素的增加、删除的时间复杂度均为O(logn)，小顶堆的堆顶元素就是集合里的最小值，如果我们将集合 U 设计成一个类似堆的数据结构，则可以大大提升效率，这里我就不实现了。
4. 小结
怎么记住这个算法呢，记住 2 个核心关键点：一是有2个集合 S、U，知道它分别代表的什么意思，二是怎么更新集合 U 中顶点的最短距离值。剩下手写代码的事情，无非是在这个框架之上修修补补的事情了。
