【你该懂一点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、蒙面数据、搜索性能大幅提升、最短路径功能
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
挑战程序设计竞赛
秋叶拓哉、岩田阳一、北川宜稔 / 巫泽俊、庄俊元、李津羽 / 人民邮电出版社 / 2013-7-1 / CNY 79.00
世界顶级程序设计高手的经验总结 【ACM-ICPC全球总冠军】巫泽俊主译 日本ACM-ICPC参赛者人手一册 本书对程序设计竞赛中的基础算法和经典问题进行了汇总,分为准备篇、初级篇、中级篇与高级篇4章。作者结合自己丰富的参赛经验,对严格筛选的110 多道各类试题进行了由浅入深、由易及难的细致讲解,并介绍了许多实用技巧。每章后附有习题,供读者练习,巩固所学。 本书适合程序设计......一起来看看 《挑战程序设计竞赛》 这本书的介绍吧!