【你该懂一点Javascript算法系列】之单源最短路径 - Dijkstra算法
栏目: JavaScript · 发布时间: 5年前
内容简介:迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959以上图为例
Javascript算法系列 - 单源最短路径 - Dijkstra算法
迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959
ps: Dijkstra算法是一种贪心算法
以上图为例
首先我们先定义出上图的邻接矩阵
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 数组,把所有顶点距离初始化为无限大,所有顶点定义为为访问
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算法的过程,有些简短,有问题可以留言交流
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 单源最短路径:Dijkstra算法(堆优化)
- 漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条
- HDFS短路读详解
- 动态规划之最短路径和
- 漫画:如何求图的最短路径? | 技术头条
- ArangoDB 3.5:流事务 API、蒙面数据、搜索性能大幅提升、最短路径功能
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
PHP for the World Wide Web, Second Edition (Visual QuickStart Gu
Larry Ullman / Peachpit Press / 2004-02-02 / USD 29.99
So you know HTML, even JavaScript, but the idea of learning an actual programming language like PHP terrifies you? Well, stop quaking and get going with this easy task-based guide! Aimed at beginning ......一起来看看 《PHP for the World Wide Web, Second Edition (Visual QuickStart Gu》 这本书的介绍吧!