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

SoapEye 发布于2019-08-23 15:04 / 1495人阅读

摘要：算法系列单源最短路径算法迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

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 //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 数组，把所有顶点距离初始化为无限大，所有顶点定义为为访问
把顶点A到自己的距离初始化为0

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

云服务器 GPU云服务器最短路算法dijkstra 最短路径算法程序最短路径算法大全最短路径算法合集

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101454.html

图算法

摘要：最小距离相关算法算法单源最短路径算法路径大于零定义概览迪杰斯特拉算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。注意该算法要求图中不存在负权边。算法可视化代码最小距离相关算法 Dijkstra算法单源最短路径算法路径大于零 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点...

chavesgu 2019-08-19 10:29 评论0 收藏0
面试算法实践与国外大厂习题指南

摘要：面试算法实践与国外大厂习题指南翻译自维护的仓库，包含了在线练习算法概述与大厂习题实战等内容。面试算法实践与国外大厂习题指南在线练习在线面试编程数据结构链表即是由节点组成的线性集合，每个节点可以利用指针指向其他节点。面试算法实践与国外大厂习题指南翻译自 Kevin Naughton Jr. 维护的仓库 interviews，包含了在线练习、算法概述与大厂习题实战等内容。笔者发现正好和...

genedna 2019-08-14 17:46 评论0 收藏0
【你该懂一点Javascript算法系列】之【图类】的定义及深度优先与广度优先搜索算法

摘要：邻接矩阵在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连如果相连这个值表示的是相连边的权重。直到返回到顶点完成探索具体还有版的深度和广度优先的算法，具体代码奉上直达地址图github直达地址 https://github.com/fanshyiis/... 在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆...

qqlcbb 2019-08-23 15:17 评论0 收藏0
最短路径算法总结

摘要：对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过，边数不会超过。我会说只有三个吗适用于任何图，不管有向无向，边权正负，但是最短路必须存在。定义（还记得这些定义吗？如果对图的概念和存储不了解请点击链接）路径最短路有向图中的最短路、无向图中的最短路单源最短路、每对结点之间的最短路性质对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。对于边权为正的图，任意...

Tecode 2022-06-28 19:00 评论0 收藏0
【程序员必会十大算法】之弗洛伊德算法

摘要：学习资料迪杰斯特拉计算的是单源最短路径，而弗洛伊德计算的是多源最短路径代码不能设置为，否则两个相加会溢出导致出现负权创建顶点和边学习资料迪杰斯特拉计算的是单源最...

JellyBool 2021-09-30 09:47 评论0 收藏0