最短路径问题求解以及近似最短路径

最短路径问题求解以及近似最短路径

Tags
位图算法
Dijkstra算法
队列
CreatedTime
Aug 21, 2022 07:46 AM
Slug
2021-09-12-dijkstra
UpdatedTime
Last updated August 21, 2022

dijkstra应用场景

深度优先和广度优先,主要针对无权图的搜索。
针对有向有权图,也就是图中的每条边都有一个权重,使用的是dijkstra算法。

dijkstra建模

点(GraphNode)

注意dist属性,它是距离开始节点的最短路径距离。
class GraphNode { constructor(key) { this.key = key; // 节点的标识 this.edges = []; // 节点的边 this.dist = 0; // 距离开始节点的最短路径距离 } }

边(GraphEdge)

class GraphEdge { // 边:skey -> tkey constructor(skey, tkey, weight) { this.skey = skey; // 边的开始节点 this.tkey = tkey; // 边的结束节点 this.weight = weight; // 边的权重 } }

图(Graph)

class Graph { constructor() { this.nodes = {}; // 图中所有节点 } /** * 新增一条边:skey -> tkey * @param {string} skey 开始节点标识 * @param {string} tkey 结束节点标识 * @param {number} w 边的权重 */ addEdge(skey, tkey, w) { this.nodes[skey].edges.push(new GraphEdge(skey, tkey, w)); } }

最小堆

这里的最小堆主要用于实现优先队列,它能在O(1) 时间内,快速得到当前距离源点最近的节点。
堆使用heap.js实现:
const { Heap } = require("heap-js"); class DistPriorityQueue { constructor() { this.minHeap = new Heap(this.heapComparator); } // 小顶堆,主要用于快速计算目前哪个未被访问的、距离开始节点最近的节点 heapComparator(a, b) { return a.dist - b.dist; } }

dijkstra算法实现

notion image

实现思路

这里简单记录大体的思路,具体可见上图。
初始化所有的节点,除了开始节点本身dist设置为0,其他节点的dist均为最大值(方便之后比较)。同时将开始节点入优先队列。
从优先队列中取出距离开始节点最近的节点,检查此节点是否是目标节点,如果是,那么说明已经到达目的地,此时为最短距离,结束算法。
否则,开始尝试往下继续走,访问此节点的邻居节点:
  • 当前节点的dist +邻边长度 < 邻边节点的dist,那么说明从当前节点过来距离更短,更新邻边节点的dist值。
    • 如果队列中存在邻居节点,那么就更新update(其实就是更新节点的dist之后,对堆重新排序);如果不存在,那么就将其放入队列中。
  • 当前节点的dist +邻边长度 ≥ 邻边节点的dist,那么说明这条路更长,没有必要走,不做任何处理。
一直持续,直到走到目的节点。
🌟🌟🌟**优先队列的作用 **能够快速拿到目前距离开始节点最近的节点(堆顶元素),从而每次都从最近的节点出发,一步步遍历到目的节点。

实现代码

/** * @param {Graph} graph 图 * @param {string} skey 开始节点的标识 * @param {string} tkey 结束节点的标识 */ function dijkstra(graph, skey, tkey) { // step0: 用来保存最短路径,用于输出打印 // key和value代表路径方向,从value走到key:key <- value const pathNodes = {}; // step1: 初始化每个节点距离开始节点的距离(dist属性) // 除了自己设置为0,其它都是最大值 for (const key in graph.nodes) { const node = graph.nodes[key]; node.dist = key === skey ? 0 : Number.MAX_VALUE; } // step2: 优先队列(小顶堆),用于取出dist属性最小的点,也就是距离开始节点最近的点 const queue = new DistPriorityQueue(); queue.minHeap.push(graph.nodes[skey]); // step3: 防止同一个节点,被多次添加到queue中(环),造成无限循环 const visited = {}; visited[skey] = true; // step4: 每次都取出未遍历到的,最近的点 // 然后遍历最近的点的邻居节点 // 如果邻居节点满足条件(具体看内循环),则增加到queue中 while (queue.minHeap.size()) { // 每次拿到的都是距离开始节点最近的点 // 最小堆可以保证在O(logN)内拿到 const minDistNode = queue.minHeap.pop(); // 到达目的地 if (minDistNode.key === tkey) { break; } for (const edge of minDistNode.edges) { const linkedNode = graph.nodes[edge.tkey]; // 当前距离开始节点最近的点,继续往邻居节点“走” // 如果距离+走的距离,比邻居节点到开始节点距离还小的话 // 那么更新邻居节点的dist属性,更新pathNodes,并且更新queue if (minDistNode.dist + edge.weight < linkedNode.dist) { linkedNode.dist = minDistNode.dist + edge.weight; pathNodes[linkedNode.key] = minDistNode.key; if (visited[linkedNode.key]) { queue.minHeap.remove(linkedNode); queue.minHeap.push(linkedNode); } else { queue.minHeap.push(linkedNode); visited[linkedNode.key] = true; } } } } console.log(">>> 路径是", pathNodes); }

测试代码

// 测试代码 const a = new GraphNode("a"); const b = new GraphNode("b"); const c = new GraphNode("c"); const d = new GraphNode("d"); const e = new GraphNode("e"); const graph = new Graph(); graph.nodes = { a, b, c, d, e, }; graph.addEdge("a", "b", 3); graph.addEdge("a", "c", 1); graph.addEdge("b", "e", 2); graph.addEdge("c", "d", 1); graph.addEdge("d", "e", 2); // 输出:>>> 路径是 { b: 'a', c: 'a', d: 'c', e: 'd' } // 逆序排列下就是路径顺序了:e <- d <- c <- a dijkstra(graph, "a", "e");

实际地图项目-近似最短路径

实际工程应用中的取舍

对于实际地图,考虑全部的点和边固然可以得到最有解,但是计算复杂度高O(E*logV)
一般在实际工程中,只要取个近似解即可。

如何取近似解?

我们发现,最优路径一般在两个点之间的连线,不会向“外”绕。
分2种情况:
  • 两个点距离比较近(比如5公里),那么根据2个点做直线,并且点是直线中点。 然后勾出一个矩形,根据规律只考虑矩形内的路径和点即可
  • 两个点距离比较远(比如500公里),那么按照方法1,也会有很多的路径和点。 此时,只考虑国道、省道等主干道即可。 类似高德地图,当地图缩小到一定比例,无关紧要的点和路径,都不再显示。当行驶过程中,动态加载计算附近的路径和点即可(详细地)。
这两种处理思路的主旨是忽略一些不重要的路径和点。

参考

极客时间-数据结构与算法之美