17|选路算法:Dijkstra是如何解决最短路问题的?
黄清昊
该思维导图由 AI 生成,仅供参考
你好,我是微扰君。
在掌握操作系统中的一些经典算法之后,我们来学习计算机的另一大基础课——计算机网络中的算法。计算机网络,当然也是一个历史悠久的科研方向,可以说之所以现在计算机世界如此繁荣,计算机网络发挥着巨大的作用,是整个互联网世界的基石。
复杂的计算机网络中自然也产生了许多算法问题,比如许多经典的图论算法都是在计算机网络的研究背景中诞生的。在这一章我们会挑选几个有趣的问题一起讨论,主要涉及两种场景,计算机网络网络层的选路算法、传输层协议 TCP 中的滑动窗口思想。
今天我们先来学习选路算法,有时它也被称为路由算法,“路由”这个词相信你应该很熟悉,没错,说的就是路由器里的路由。
路由
我们知道,计算机网络的作用,就是通过把不同的节点连接在一起从而交换信息、共享资源,而各个节点之间也就通过网络形成了一张拓扑关系网。
比如在一个局域网下,节点 A 要给节点 B 发送一条消息,如果 A 和 B 并没有直接通过网络相连,可能就需要经过其他路由设备的几次转发,这时我们需要在整个网络拓扑图中找到一条可到达的路径,才能把消息发送到目的地。
每台路由器都是一台网络设备,也就是网络中的一个节点,在其中就保存有一张路由表,每次网卡收到包含目标地址的数据包(packet)时,就会根据路由表的内容决定如何转发数据。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
Dijkstra算法是解决最短路问题的经典算法之一,主要用于计算机网络中的选路算法。该算法通过贪心思想逐步找出距离源点最近、次近的点,构建最短路径树,从而求出源点到所有节点的最短距离和路径。然而,Dijkstra算法有一个限制,即只能用于没有权重为负的边的图。文章通过引入“松弛”操作来描述Dijkstra算法的过程,并给出了相关的代码实现。此外,文章还提到了Dijkstra算法的时间复杂度为O(N^2),并引出了对更快写法的思考。总的来说,本文介绍了Dijkstra算法的原理、实现和应用,对于想要深入了解最短路算法的读者来说,是一篇值得阅读的文章。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《业务开发算法 50 讲》,新⼈⾸单¥59
《业务开发算法 50 讲》,新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(3)
- 最新
- 精选
- Paul ShanDijkstra 算法是逐步构建最短路径树,树中的节点的最短距离不依赖于树外节点,这样才可以一个节点加入最短路径树之后,距离不再改变。负权节点的存在会让加入最短路径树的节点的真实最短路径会因为不在树中的节点而改变,整个算法也就无效了。 如果用最小堆作为数据结构选择最短路径,可以让内存循环的复杂度降为lg V,最终的复杂度可以降为(V+E)lg V
作者回复: 说的非常好耶! 大佬加个wx吧: constant_variation
2022-01-183 - ZeroIce有时候在想:负权边的意义是什么? 应用场景在哪里?🤪
作者回复: 非常不错的问题。 事实上,在现实生活中有许多能用图抽象的问题都会用到负权边。比如,我们将边定义成到达某个状态所需要的开销;有时候我们需要花费一定的费用到达某个状态;而有的时候会有人支付我们一定的费用。一个很好的例子就是某个司机开往某些地方能赚到一定钱或者支付一定的公路费用。 如果我们为了求出从A点出发到B点的最小成本;当走过某段路可以获得收入的时候,该边就可以被抽象为负权边。
2022-02-141 - 到道可道Dijkstra的Java实现 private int dijkstra(List<int[]>[] graph, int src, int k, int dst) { // 从起点src到达节点i的最短路径权重为distTo[i] int[] distTo = new int[graph.length]; // 定义:从起点src到节点i,至少要经过nodeNumTo[i]个节点 int[] nodeNumTo = new int[graph.length]; Arrays.fill(distTo, Integer.MAX_VALUE); Arrays.fill(nodeNumTo, Integer.MAX_VALUE); // base case distTo[src] = 0; nodeNumTo[src] = 0; // 优先队列,costFromSrc较小的排在前面 Queue<State> pq = new PriorityQueue<>((a, b) -> a.costFromSrc - b.costFromSrc); // 从起点src开始进行BFS pq.offer(new State(src, 0, 0)); while (!pq.isEmpty()) { State curState = pq.poll(); int curId = curState.id; int curCostFromSrc = curState.costFromSrc; int curNodeNumFromSrc = curState.nodeNumFromSrc; if (curId == dst) { // 找到最短路径 return curCostFromSrc; } if (curNodeNumFromSrc == k) { // 中转次数耗尽 continue; } // 将curId 的相邻节点装入队列 for (int[] neighbor : graph[curId]) { int nextId = neighbor[0]; int costToNextNode = curCostFromSrc + neighbor[1]; // 中转次数 int nextNodeNumFromSrc = curNodeNumFromSrc + 1; // 更新dp table if (distTo[nextId] > costToNextNode) { distTo[nextId] = costToNextNode; nodeNumTo[nextId] = nextNodeNumFromSrc; } // 剪枝 if (costToNextNode > distTo[nextId] && nextNodeNumFromSrc > nodeNumTo[nextId]) { continue; } pq.offer(new State(nextId, costToNextNode, nextNodeNumFromSrc)); } } return -1; }
作者回复: 写得很好 感兴趣可以来 github.com/wfnuser/Algorithms 提个 pr
2022-03-06
收起评论