TOC
最短路径
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
假设我们拥有一条路径 P P 经过一些节点 v1 v2 v3 …. vk 并且每条边都拥有的自己的权重（可以认为是他的长度），而所谓最短路径，就是寻找出总权重 W(P) 最小的一条路径,一般来说 最短路径的题目就是 给你开始节点和结束节点，求出一条最短路径。
接下来我们需要一些代号来帮助我们进行分析
δ(u,v) 代表从节点 U 到 V 的最短路径（之一）的权重值
值得注意的我们的 最短路径在某些情况下是不存在的，比如在我们的路径中出现了某个内总权重为负数的环，那么我们将不断的在环中循环。或者 UV 之间根本没有路径将他们链接起来，这种情况下的δ(u,v) 为 +infinity
单源最短路径算法
前置知识点
δ(u,vx) <= δ(u,x) + δ(x,v) // 既然是最短路径的总权重 必然小于或等于用某个未知节点进行拆分的两条路径之和。
所谓单源最短路径，就是求从源点 S 到图中所有节点 V 的最短路径。在计算之前，我们先设立一个条件：所有的边都不为负，先让我们忽视负权重闭环的问题，其实只要求出了到所有点的问题，那么我们也就等于解决了到某个点的最短路径
接下来，我们将使用贪心的思想来解决这个问题。先来描述前提条件
- S 是已知最短路径的顶点都集合 从源节点 s 到该集合中每个节点之间的最短路径已被找到。最初的 S 中必然有源点 s
- 贪心策略：寻找与 S 中的元素连接 并且权重值最小的节点（本身不在集合 S 中）将其放入到集合 S 中
- 更新某些点的估算距离
再初步了解该算法的情况下，我认为这个算法有点像贪吃蛇，从 S 中去判断距离，每一步就将一个与 s 最短距离的节点放到集合 S 中，并不断扩张,修正最短选择。书中把不断修正的过程称之为 松弛。
松弛是一个非常重要的概念，我在此贴出松弛的伪代码,针对于有向图 u 是出发点，v 是结束点，两者 uv 代表一条边 ，w 是权重函数,v 的 d 属性代表源点 s 到该节点的最短路径估计，而 v 的 π 属性则代表了该节点的前驱节点。
RELAX(u,v,w){
if(v.d) > u.d + w(u,v)
v.d = u.d + w(u,v)
v.π = u
}
接下来是基本的初始化代码 遍历所有节点
INIT(G,s){
for each vertex v of G.V
v.d = +infinity
v.π = null
s.d = 0
}
bellman-ford 算法
该算法是解决单源最短路径的一种方式，其算法复杂度为O(VE).他的最大特点是能够检测该图中是否存在闭环，如果存在就返回 false。以下是我参照书中伪代码的实现，还是比较简单的。
// 邻接矩阵 记录连通与路径权重
const G = [
[0, 6, 0, 7, 0],
[0, 0, 5, 8, -4],
[0, -2, 0, 0, 0],
[0, 0, -3, 0, 9],
[0, 0, 7, 0, 0]
]
// 辅助表 帮助记录额外的信息 如前置元素 最短路径估计d
const nodes = [
{ name: 's' },
{ name: 't' },
{ name: 'x' },
{ name: 'y' },
{ name: 'z' }
]
// 松弛操作
const relax = (u, v, nodes, g) => {
if (nodes[v].d > nodes[u].d + g[u][v]) {
nodes[v].d = nodes[u].d + g[u][v]
nodes[v].π = nodes[u]
}
}
// 初始化
const init = (nodes, s) => {
nodes.forEach(v => {
v.π = null
v.d = Infinity
})
nodes[s].d = 0
}
// 求单源最短路径
const bellman_ford = (g, s, table) => {
init(table, s)
// 三层循环 可简化成两层 外层为G.V 即所有节点 内层为G.E即图内所有边
for (let i = 0; i < g.length; i++) {
for (let j = 0; j < g.length; j++) {
for (let n = 0; n < g.length; n++) {
if (g[j][n] !== 0) {
relax(j, n, table, g)
}
}
}
}
// 闭环检测
for (let j = 0; j < g.length; j++) {
for (let n = 0; n < g.length; n++) {
if (g[j][n] !== 0) {
if (table[n].d > table[j].d + g[j][n]) {
return false
}
}
}
}
return true
}
console.log(bellman_ford(G, 0, nodes))
console.log(nodes)
图片版
Dijkstra 算法
这是一种贪心算法，他对图有更加严格的要求，不允许闭环，且所有边的权重都必须大于 0
这种算法的核心在于不断的将当前最近的节点加入到最终集合 S 中，并且利用到了优先队列。这个算法会稍微复杂一些，主要是用了优先队列，并对其进行了一些改造，松弛算法也进行了一些改造。
他需求权重大于 0 的原因就是因为他的贪心策略不允许他回头重新计算某条边的新权重。
他的时间复杂相比上面的算法更加快速,其实他从逻辑上就是断定当前未加入集合 S 的节点中，预计D最小的节点他的 D必然是真实确定的，可以被认为是已知最短路径。一个节点一旦被认为是正确答案加入到集合 S 中，那么他的 属性将永远不会改变。
// 优先队列
const left = i => 2 * i
const right = i => 2 * i + 1
const parent = i => Math.floor(i / 2)
/**
* @param {Array} A 堆数组
* @param {number} i 处理下标
*/
function MIN_HEAPIFY(A, i) {
let l = left(i)
let r = right(i)
let cur = A[i]
let minimum = i
if (l <= A.heapSize && cur.key > A[l].key) {
minimum = l
}
if (r <= A.heapSize && A[minimum].key > A[r].key) {
minimum = r
}
// 以上总结一句话 我 左 右 三个里面找最小
if (minimum !== i) {
;[A[i], A[minimum]] = [A[minimum], A[i]] // es6语法 解构 互换值
MIN_HEAPIFY(A, minimum)
}
}
function BUILD_MIN_HEAP(A) {
A.heapSize = A.length - 1
if (A.heapSize < 0) return
for (let i = Math.floor(A.heapSize / 2); i >= 0; i--) {
MIN_HEAPIFY(A, i)
}
}
class Q {
constructor(arr = []) {
this.heap = arr
BUILD_MIN_HEAP(this.heap)
this.heapSize = arr.length - 1
}
isEmpty() {
return this.heap.length <= 0 || this.heap.heapSize < 0
}
getMinimum() {
return this.heap[0]
}
extHeapMin() {
if (this.heap.heapSize < 0) {
return false
}
let min = this.heap[0]
this.heap[0] = this.heap[this.heap.heapSize]
this.heap.heapSize--
MIN_HEAPIFY(this.heap, 0)
return min
}
reMinHeapify() {
MIN_HEAPIFY(this.heap, 0)
}
incrHeapKey(i, key) {
if (key < this.heap[i].key) {
return false
}
this.heap[i].key = key
// 修改权重可能会破坏本身的特性 不断向上修复这个问题。
while (i > 0 && this.heap[parent(i)].key > this.heap[i].key) {
;[this.heap[i], this.heap[parent(i)]] = [
this.heap[parent(i)],
this.heap[i]
]
i = parent(i)
}
}
insert(value) {
this.heap.heapSize++
this.heap[this.heap.heapSize] = value
this.incrHeapKey(this.heap.heapSize, value.key)
}
find(name) {
let index = -1
for (let i = 0; i <= this.heap.heapSize; i++) {
if (this.heap[i].name === name) {
index = i
}
}
return index
}
}
// 邻接矩阵 记录连通与路径权重
const G = [
[0, 10, 0, 5, 0],
[0, 0, 1, 2, 0],
[0, 0, 0, 0, 4],
[0, 3, 9, 0, 2],
[7, 0, 6, 0, 0]
]
// 辅助表 帮助记录额外的信息 如前置元素 最短路径估计d
const nodes = [
{ name: 's', sub: 0 },
{ name: 't', sub: 1 },
{ name: 'x', sub: 2 },
{ name: 'y', sub: 3 },
{ name: 'z', sub: 4 }
]
// 松弛操作
const relax = (u, v, nodes, g, q) => {
if (nodes[v].key > nodes[u].key + g[u][v]) {
nodes[v].key = nodes[u].key + g[u][v]
nodes[v].π = nodes[u]
// 额外内容 更新队列中的key
let qindex = q.find(nodes[v].name)
if (qindex === -1) return
q.incrHeapKey(qindex, nodes[u].key + g[u][v])
}
}
// 初始化
const init = (nodes, s) => {
nodes.forEach(v => {
v.π = null
v.key = Infinity
})
nodes[s].key = 0
}
function Dijkstra(G, s, table) {
// 初始化 S是已知最短路径的集合
let S = []
init(table, s)
// 建立一个镜像优先队列
let q = new Q(table.slice())
// 如果不为空
while (!q.isEmpty()) {
// 取出一个当前预计总权重最低的节点 其实也就是离s最近的节点
let u = q.extHeapMin()
// 放入已知集合中
S.push(table[u.sub])
for (let i = 0; i < G.length; i++) {
// 对改点进行松弛操作
if (G[u.sub][i] !== 0) {
relax(u.sub, i, table, G, q)
}
}
}
return S
}
console.log(Dijkstra(G, 0, nodes))
值得一提的是，如果你的图他的每条边的权重相同，那么可以利用广度优先搜索进一步的提升性能，广度优先搜索需要一个 FIFO 先进先出队列。他从源点 s 开始，不断的发现节点并松弛，将发现的节点加入到队列之中，每次循环都从先进先出队列里进行松弛操作，并把它的 u 加入到集合 S中。他的重要断定是当一个节点的 d 改变时，接下来他的 d 将不会再改变。实际的改变大致就是本来从优先队列拿的变成从 FIFO 里拿，拿出一个节点 u,然后对 uv进行松弛的同时，如果 v 从没被观察过，设置他的 d = u.d + 1 然后讲他放入队列的末尾。因为广度优先的搜索特性，其 d 越近的元素必然会更早的被遍历到。具体算法可查阅书中22章。