【你该懂一点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算法的过程,有些简短,有问题可以留言交流


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

查看所有标签

猜你喜欢:

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

PHP for the World Wide Web, Second Edition (Visual QuickStart Gu

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》 这本书的介绍吧!

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

各进制数互转换器

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换