【你该懂一点Javascript算法系列】之单源最短路径 - Dijkstra算法

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 //1function 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_INTEGERfor (let i = 0; i < length; i++) { dist[i] = INF visited[i] = false }//5 dist[src] = 0初始化dist visted 数组，把所有顶点距离初始化为无限大，所有顶点定义为为访问把顶点A到自己的距离初始化为02.过程解析//顶点探索函数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算法的过程，有些简短，有问题可以留言交流