Javascript 算法系列 – 单源最短路径 – Dijkstra 算法
迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于 1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止
ps: Dijkstra 算法是一种贪心算法
以上图为例 我们要求出顶点 A 到其余各顶点间的最短路径
首先我们先定义出上图的邻接矩阵
let graph = [[0,2,4,0,0,0],
[0,0,1,4,2,0],
[0,0,0,0,3,0],
[0,0,0,0,0,2],
[0,0,0,3,0,2],
[0,0,0,0,0,0]]
ps: 邻接矩阵的意思是：用一个二数组表示个顶点间的关系，来确定各顶点间的关系，因为图为有向图，所以上图的邻接矩阵如上
先放出 Dijkstra 算法的全部代码再来结合慢慢解析
let index = ‘ABCDEF’
let INF = Number.MAX_SAFE_INTEGER //1
function dijkstra(src) {
let dist = [],//2
visited = [],//3
length = graph.length//4
for (let i = 0; i < length; i++) {
dist[i] = INF
visited[i] = false
}//5
dist[src] = 0
for (let i = 0; i < length – 1; i++) {
let u = minDistance(dist, visited)
visited[u] = true
for (let v = 0; v < length; v++) {
if (!visited[v] && dist[u] !== INF && graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v]
}
}
}
return dist
}
function minDistance(dist, visited) {
let min = INF,
minIndex = -1
for (let v = 0; v < dist.length; v++) {
if (visited[v] === false && dist[v] <= min) {
min = dist[v]
minIndex = v
}
}
return minIndex
}
1. 初始化数据定义 dist 数组来储存当前 A 顶点到其它各个顶点间的距离定义 visited 数组来储存 ABCDEF 顶点是否被访问过，以免重复访问，形成环定义 length 来储存所有顶点的数量定义 INF 为 javascript 的最大整数 Number.MAX_SAFE_INTEGER
for (let i = 0; i < length; i++) {
dist[i] = INF
visited[i] = false
}//5
dist[src] = 0
初始化 dist visted 数组，把所有顶点距离初始化为无限大，所有顶点定义为为访问把顶点 A 到自己的距离初始化为 0
2. 过程解析
// 顶点探索函数
for (let i = 0; i < length – 1; i++) {
let u = minDistance(dist, visited)
visited[u] = true
for (let v = 0; v < length; v++) {
if (!visited[v] && dist[u] !== INF && graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v]
}
}
}
// 寻找最短路径函数
function minDistance(dist, visited) {
let min = INF,
minIndex = -1
for (let v = 0; v < dist.length; v++) {
if (visited[v] === false && dist[v] <= min) {
min = dist[v]
minIndex = v
}
}
return minIndex
}
具体探索逻辑如下
第一次循环找到最短顶点 A 遍历 A 到其他顶点的距离，如果和其他顶点有直接联系，则判断 A 到其他顶点的距离，是否是 A 目前到 X 顶点的距离 + X 到新顶点的距离 < A 新顶点的距离 如果小于，则更新到该顶点最短距离
第一次循环完后相应输出值发现 A 遍历发现 A -> B 为 2 A->C 为 4 均小于无穷大，所以更新 A 点到 B，C 的最短距离
visited -> [true, false, false, false, false, false]
dist -> [0, 2, 4, 9007199254740991, 9007199254740991, 9007199254740991]
第二次循环找到最短的那个边，除 A 以外 所以探索 B 点遍历发现 B->C,B->E, B->D 分别为 1，2，4 则 A - C 距离为 A -B + B-C = 3 小于直接到 C 的距离 4 所以更新 A - C 最短距离
visited -> [true, true, false, false, false, false]
dist -> [0, 2, 3, 6, 4, 9007199254740991]
剩下三次探索输出为 dist -> [0, 2, 3, 6, 4, 9007199254740991]visited -> [true, true, true, false, true, false]dist -> [0, 2, 3, 6, 4, 6]visited -> [true, true, true, false, true, true][0, 2, 3, 6, 4, 6]
这样就会获得 A 到所有边的最短距离 [0, 2, 3, 6, 4, 6]
这就是 js 实现 Dijkstra 算法的过程，有些简短，有问题可以留言交流