狄克斯特拉算法

概念

迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止

理解

假设给定一个二维数组，里面存储着各个相邻点之间的距离，

比如第一个['a', 'b', 20]，表示着从A点到B点的距离为20，以此类推

let data = [
  ['a', 'b', 20],
  ['a', 'e', 20],
  ['a', 'c', 3],
  ['b', 'c', 20],
  ['c', 'd', 5],
  ['c', 'e', 30],
  ['d', 'e', 6],
  ['e', 'a', 20],
]

而我们的需求则是，以某个确定的点为起点，得出其到其余点的最短距离，比如以a为起点，我们想得到其到b、c、d、e的最短距离

那么这个算法该如何在js上实现

单纯从这个数组来看，好像有点想不出解法，我们先试着把它转化成图形关系，从而更加容易理解点

从这个图，我们可以更加直观的理解每个点之间的位置距离关系，比如A，可以直接到达B、C、E，但却不能直接到达D，要想过去，还得通过一些“中介点”

接着，我们来简略介绍下狄克斯特拉算法的使用步骤

(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。

(2) 更新该节点的邻居的开销。

(3) 重复这个过程，直到对图中的每个节点都这样做了。

(4) 计算最终路径。

在默认初始化条件下：我们用一个表来记录默认起点下到其他点的最短距离

次数	S	b	c	d	e
1	{a}	20	3	∞	20
2	{a,c}	20	3	8	20
3	{a,c,b}	20	3	8	20
4	{a,c,b,d}	20	3	8	14

用一个表格记录更新完最短距离表格后的目标地点的上一个节点

次数	b	c	d	e
1	a	a	a	a
2	a	a	c	a
3	a	a	c	a
4	a	a	c	d

阐述下这个过程

首先，我们将A到各个其他点的距离记录进去，接着按初始距离从短到长的顺序将a,b、a,c、a,d这三个当作一个整体去更新表格(注意：这里不是简单的就是a→b，而是他们之间的最短路径)

记住，每次我们都从最短的路径入手，比如a到c的距离最短，那么我们就从该点c入手，其次就是在b和d中选择

比如在接下来，我们把a→c当作一个整体，它的默认权重为3，然后去对比其他各个点，注意看图，根据结果去刷新最短距离，比如c到e的距离是30，加上默认权重（a→c）3，是33，比a直接到达e还远，所以我们不更新该距离，以及c的最短距离的上一个节点还是a，其他类似，每一步更新完，即可得出起点到达该点的最短距离了

我们重点看下第三次和第四次，在第三次，a到b，c还是不变，但是c可以直接到d了,也就是说，在原先的基础a到c的距离3上加5，得出该距离为8，同时途径点可以更新为c

第四次，我们发现d到e的距离为6，加上a到d的最短距离8可以达到14，比a直接过去还短，所以我们更新表格，最短距离为14，上个节点为e

我们可以看到这样的规律，如果当前节点pass到终点end的距离(passEnd)加上起点start到当前节点pass的距离(startPass)小于默认起点start到终点end的距离(startEnd)，那么就更新表格

1 2	如果startPass + passEnd < startEnd 则startEnd = startPass + passEnd（更新）

代码实现

我们用一个对象来存储当个点到其他点的距离，比如下面

{
  b: {
    instance: 20,
    process: a
  },
  c: {
    instance: 3,
    process: a
  }
    ...
}

用一个函数来格式化该操作，data为数组数据，startPoint为起点，targetPoint为终点集合（数组），格式完数据后，我们把起点到起点的数据删掉，因为该点并没有什么用

// 初始化单个数据的散列表
function init(data, startPoint, targetPoint) {
  let res = {}
    // 初始化每条数据，默认距离为无穷大，上一节点为起始点startPoint
  targetPoint.forEach(i => {
      res[i] = {
        instance: 99999,
        process: startPoint,
        target: i
      }
    })
    // 遍历数据，赋值已有最近临点初始距离
  data.forEach(i => {
    if (res[i[1]] && i[0] == startPoint) {
      res[i[1]].instance = i[2]
    }
  })
  res[startPoint] && delete res[startPoint] //删除起点（无用）
  return res
}

接着，我们用另一个对象把所有数据包裹起来，

{
   起点1:{
     目标地点1:{
       instance: 距离,
       process: [途径地点]
     },
     目标地点2: {
       instance: 距离,
       process: [途径地点]
     }
...
   },
   起点2:{
     目标地点1:{
       instance: 距离,
       process: [途径地点]
     },
     目标地点2:{
       instance: 距离,
       process: [途径地点]
     }...
   } 
 }

实现该操作的函数

// 建立全部数据的散列表
function pointDistanceHashTable(data, targetPoint) {
  let res = {}
    // 对所有点进行遍历并初始化
  targetPoint.forEach((i, index) => {
    res[i] = init(data, i, targetPoint)
  })
  return res
}

对比长度的函数，通过前面的介绍我们可以知道这个过程的实现，无需多言，直接看代码，入参含义为（数组数据，起点名称，当前点名称，终点名称）

// 对比两者距离长度，会改变data，返回最新结果
// 参数：数据initData, 起点名称，当前点名称，终点名称
function longer(initData, start, pass, end) {
  let newDistance = initData[start][pass].instance + initData[pass][end].instance
  if (newDistance < initData[start][end].instance) {
    initData[start][end].instance = newDistance
    initData[start][end].process = pass
  }
  return initData[start]
}

按距离从小到大进行排序，传入对象（数组），返回数组，会改变原数据

function sortData(data) {
  if (!(data instanceof Array)) {
    let arr = []
    for (key in data) {
      arr.push(data[key])
    }
    return arr.sort((a, b) => {
      return a.instance - b.instance
    })
  }
  return data.sort((a, b) => {
    return a.instance - b.instance
  })
}

主函数入口：最主要的就是迭代，对每个点进行迭代执行analyse函数，再对每个点下的终点距离进行遍历判断

function dijkstra(data, startPoint, targetPoint) {
  let allPoint = new Set([...targetPoint, startPoint])
    // 获取全部点的散列表
  let initData = pointDistanceHashTable(data, allPoint);
  // 将起点单独提取出来，用于遍历, 大小比较
  let startPointData = initData[startPoint];

  // 按初始路径长短顺序进行路径分析
  return (analyse = function() {
    if (startPointData.length == 0) {
      initData[startPoint].start = startPoint //给他一个名字
      return initData[startPoint]
    } else {
      startPointData = sortData(startPointData) //排序
      // 遍历更新数据
      for (next in initData[startPointData[0].target]) {
        // 排除掉绕圈
        if (next != startPoint) {
          // 更新掉initData的数据
          longer(initData, startPoint, startPointData[0].target, next)
        }
      }
      startPointData.shift() //移除当前数据
      // 继续迭代
      return analyse()
    }
  })()
}

将结果进行描述的函数，在这里对于算法来说没啥用处，主要就是结果的文字展示

// 途径函数，传入算法计算结果的数据，以及要到达的终点，返回文字提示
function roadPoint(data, end) {
  if(!data[end]) return '无到达该点的最短距离数据'
  let pass = [end]
  let instanceText = '从' + data.start + '到' + end + '的距离为' + data[end].instance

  // 迭代
  return (get = function(end) {
    if (data[end].process == data.start) {
      pass.unshift(data.start)
      return instanceText + ',完整路径为' + pass
    } else {
      pass.unshift(data[end].process)
      return get(data[end].process)
    }
  })(end)
}

测试

拿前面的数据进行测试

let res1 = dijkstra(data, 'a', ['d', 'c', 'e', 'b'])
console.log(res1)
let res1Text = roadPoint(res1, 'e') //文字描述
console.log(res1Text);

结果

完整代码

// 初始化单个数据的散列表
function init(data, startPoint, targetPoint) {
  let res = {}
    // 初始化每条数据，默认距离为无穷大，上一节点为起始点startPoint
  targetPoint.forEach(i => {
      res[i] = {
        instance: 99999,
        process: startPoint,
        target: i
      }
    })
    // 遍历数据，赋值已有最近临点初始距离
  data.forEach(i => {
    if (res[i[1]] && i[0] == startPoint) {
      res[i[1]].instance = i[2]
    }
  })
  res[startPoint] && delete res[startPoint] //删除起点（无用）
  return res
}

// 建立全部数据的散列表
function pointDistanceHashTable(data, targetPoint) {
  let res = {}
    // 对所有点进行遍历并初始化
  targetPoint.forEach((i, index) => {
    res[i] = init(data, i, targetPoint)
  })
  return res
}

// 对比两者距离长度，会改变data，返回最新结果
// 参数：数据initData, 起点名称，当前点名称，终点名称
function longer(initData, start, pass, end) {
  let newDistance = initData[start][pass].instance + initData[pass][end].instance
  if (newDistance < initData[start][end].instance) {
    initData[start][end].instance = newDistance
    initData[start][end].process = pass
  }
  return initData[start]
}

// 按距离从小到大进行排序，传入对象（数组），返回数组，会改变原数据
function sortData(data) {
  if (!(data instanceof Array)) {
    let arr = []
    for (key in data) {
      arr.push(data[key])
    }
    return arr.sort((a, b) => {
      return a.instance - b.instance
    })
  }
  return data.sort((a, b) => {
    return a.instance - b.instance
  })
}

// 迪杰斯特拉
function dijkstra(data, startPoint, targetPoint) {
  let allPoint = new Set([...targetPoint, startPoint])
    // 获取全部点的散列表
  let initData = pointDistanceHashTable(data, allPoint);
  // 将起点单独提取出来，用于遍历, 大小比较
  let startPointData = initData[startPoint];

  // 按初始路径长短顺序进行路径分析
  return (analyse = function() {
    if (startPointData.length == 0) {
      initData[startPoint].start = startPoint //给他一个名字
      return initData[startPoint]
    } else {
      startPointData = sortData(startPointData) //排序
      // 遍历更新数据
      for (next in initData[startPointData[0].target]) {
        // 排除掉绕圈
        if (next != startPoint) {
          // 更新掉initData的数据
          longer(initData, startPoint, startPointData[0].target, next)
        }
      }
      startPointData.shift() //移除当前数据
      // 继续迭代
      return analyse()
    }
  })()
}

// 途径函数，传入算法计算结果的数据，以及要到达的终点，返回文字提示
function roadPoint(data, end) {
  if(!data[end]) return '无到达该点的最短距离数据'
  let pass = [end]
  let instanceText = '从' + data.start + '到' + end + '的距离为' + data[end].instance

  // 迭代
  return (get = function(end) {
    if (data[end].process == data.start) {
      pass.unshift(data.start)
      return instanceText + ',完整路径为' + pass
    } else {
      pass.unshift(data[end].process)
      return get(data[end].process)
    }
  })(end)
}