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

栏目: JavaScript · 发布时间: 5年前

内容简介:迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959以上图为例

Javascript算法系列 - 单源最短路径 - Dijkstra算法

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959

ps: Dijkstra算法是一种贪心算法

【你该懂一点Javascript算法系列】之单源最短路径 - 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: 邻接矩阵的意思是: 用一个二数组表示个顶点间的关系,来确定各顶点间的关系,因为图为有向图,所以上图的邻接矩阵如上

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

先放出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算法的过程,有些简短,有问题可以留言交流


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

程序的力量

程序的力量

甄贞 / 法律出版社 / 2002-3 / 21.00元

本书所谈及的话题概括了刑诉法学研究领域的方方面面,既有对每性、广泛性、前瞻性的宏观学科前沿问题的把握;又有实践性、直观性、详细性的个案分析和具体程序操作问题之探讨等。一起来看看 《程序的力量》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

html转js在线工具
html转js在线工具

html转js在线工具