最短路径算法,最短路径算法例题

最短路径 | 深入浅出Dijkstra算法（一）

上次我们介绍了神奇的只有 五行的 Floyd-Warshall 最短路算法 ，它可以方便的求得 任意两点的最短路径， 这称为 “多源最短路”。

这次来介绍 指定一个点（源点）到其余各个顶点的最短路径， 也叫做 “单源最短路径”。

例如求下图中的 1 号顶点到 2、3、4、5、6 号顶点的最短路径。

与 Floyd-Warshall 算法一样，这里仍然 使用二维数组 e 来存储顶点之间边的关系， 初始值如下。

我们还需要用 一个一维数组 dis 来存储 1 号顶点到其余各个顶点的初始路程， 我们可以称 dis 数组为 “距离表”， 如下。

我们将此时 dis 数组中的值称为 最短路的“估计值”。

既然是 求 1 号顶点到其余各个顶点的最短路程， 那就 先找一个离 1 号顶点最近的顶点。

通过数组 dis 可知当前离 1 号顶点最近是 2 号顶点。

当选择了 2 号顶点后，dis[2]的值就已经从“估计值”变为了“确定值”， 即 1 号顶点到 2 号顶点的最短路程就是当前 dis[2]值。

为什么呢？你想啊， 目前离 1 号顶点最近的是 2 号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 1 号顶点到 2 号顶点的路程进一步缩短了。

因此 1 号顶点到其它顶点的路程肯定没有 1 号到 2 号顶点短，对吧 O(∩_∩)O~ 既然选了 2 号顶点，接下来再来看 2 号顶点 有哪些 出边 呢。

有 2->
3 和 2->
4 这两条边。

先讨论 通过 2->
3 这条边能否让 1 号顶点到 3 号顶点的路程变短。

也就是说现在来比较 dis[3] 和 dis[2]+e[2][3] 的大小。

其中 dis[3]表示 1 号顶点到 3 号顶点的路程，dis[2]+e[2][3]中 dis[2]表示 1 号顶点到 2 号顶点的路程，e[2][3]表示 2->
3 这条边。

所以 dis[2]+e[2][3]就表示从 1 号顶点先到 2 号顶点，再通过 2->
3 这条边，到达 3 号顶点的路程。

我们发现 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>
dis[2]+e[2][3]，因此 dis[3]要更新为 10。

这个过程有个专业术语叫做 “松弛” 。

即 1 号顶点到 3 号顶点的路程即 dis[3]，通过 2->
3 这条边 松弛成功。

这便是 Dijkstra 算法的主要思想： 通过 “边” 来松弛 1 号顶点到其余各个顶点的路程。

同理通过 2->
4（e[2][4]），可以将 dis[4]的值从 ∞ 松弛为 4（dis[4]初始为 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>
dis[2]+e[2][4]，因此 dis[4]要更新为 4）。

刚才我们对 2 号顶点所有的出边进行了松弛。

松弛完毕之后 dis 数组为： 接下来，继续在剩下的 3、4、5 和 6 号顶点中，选出离 1 号顶点最近的顶点。

通过上面更新过 dis 数组，当前离 1 号顶点最近是 4 号顶点。

此时，dis[4]的值已经从“估计值”变为了“确定值”。

下面继续对 4 号顶点的所有出边（4->
3，4->
5 和 4->
6）用刚才的方法进行松弛。

松弛完毕之后 dis 数组为： 继续在剩下的 3、5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 3 号顶点。

此时，dis[3]的值已经从“估计值”变为了“确定值”。

对 3 号顶点的所有出边（3->
5）进行松弛。

松弛完毕之后 dis 数组为： 继续在剩下的 5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 5 号顶点。

此时，dis[5]的值已经从“估计值”变为了“确定值”。

对5号顶点的所有出边（5->
4）进行松弛。

松弛完毕之后 dis 数组为： 最后对 6 号顶点的所有出边进行松弛。

因为这个例子中 6 号顶点没有出边，因此不用处理。

到此，dis 数组中所有的值都已经从“估计值”变为了“确定值”。

最终 dis 数组如下，这便是 1 号顶点到其余各个顶点的最短路径。

OK，现在来总结一下刚才的算法。

Dijkstra算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

基本步骤如下： 在 博客 中看到两个比较有趣的问题，也是在学习Dijkstra时，可能会有疑问的问题。

当我们看到上面这个图的时候，凭借多年对平面几何的学习，会发现在“三角形ABC”中，满足不了 构成三角形的条件(任意两边之和大于第三边)。

纳尼，那为什么图中能那样子画？ 还是“三角形ABC”，以A为起点，B为终点，如果按照平面几何的知识， “两点之间线段最短”， 那么，A到B的最短距离就应该是6(线段AB)，但是，实际上A到B的最短距离却是3+2=5。

这又怎么解释？ 其实，之所以会有上面的疑问，是因为 对边的权值和边的长度这两个概念的混淆， 。

之所以这样画，也只是为了方便理解（每个人写草稿的方式不同，你完全可以用别的方式表示，只要便于你理解即可）。

PS：数组实现邻接表可能较难理解，可以看一下 这里 参考资料： Dijkstra算法是一种基于贪心策略的算法。

每次新扩展一个路程最短的点，更新与其相邻的点的路程。

当所有边权都为正时，由于不会存在一个路程更短的没扩展过的点，所以这个点的路程永远不会再被改变，因而保证了算法的正确性。

根据这个原理， 用Dijkstra算法求最短路径的图不能有负权边， 因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路径不会发生改变的性质。

那么，有没有可以求带负权边的指定顶点到其余各个顶点的最短路径算法（即“单源最短路径”问题）呢？答案是有的， Bellman-Ford算法 就是一种。

（我们已经知道了 Floyd-Warshall 可以解决“多源最短路”问题，也要求图的边权均为正） 通过 邻接矩阵 的Dijkstra时间复杂度是 。

其中每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N)，这里我们可以用 优先队列（堆） 来优化，使得这一部分的时间复杂度降低到 。

这个我们将在后面讨论。

图遍历算法之最短路径Dijkstra算法

最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。

根据问题的不同，算法的具体形式包括： 常用的最短路径算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改进版本），Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。

本文将重点介绍Dijkstra算法的原理以及实现。

Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的 单源最短路径问题 。

所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决著名的旅行商问题。

问题描述 ：在无向图 中， 为图节点的集合， 为节点之间连线边的集合。

假设每条边 的权重为 ，找到由顶点 到其余各个节点的最短路径（单源最短路径）。

为带权无向图，图中顶点 分为两组，第一组为已求出最短路径的顶点集合（用 表示）。

初始时 只有源点，当求得一条最短路径时，便将新增顶点添加进 ，直到所有顶点加入 中，算法结束。

第二组为未确定最短路径顶点集合（用 表示），随着 中顶点增加， 中顶点逐渐减少。

以下图为例，对Dijkstra算法的工作流程进行演示（以顶点 为起点）： 注： 01） 是已计算出最短路径的顶点集合；
02） 是未计算出最短路径的顶点集合；
03） 表示顶点 到顶点 的最短距离为3 第1步 ：选取顶点 添加进 第2步 ：选取顶点 添加进 ，更新 中顶点最短距离 第3步 ：选取顶点 添加进 ，更新 中顶点最短距离 第4步 ：选取顶点 添加进 ，更新 中顶点最短距离 第5步 ：选取顶点 添加进 ，更新 中顶点最短距离 第6步 ：选取顶点 添加进 ，更新 中顶点最短距离 第7步 ：选取顶点 添加进 ，更新 中顶点最短距离 示例：node编号1-7分别代表A,B,C,D,E,F,G (s.paths <
- shortest.paths(g, algorithm = "
dijkstra"
))输出结果： (s.paths <
- shortest.paths(g,4, algorithm = "
dijkstra"
))输出结果： 示例： 找到D（4）到G（7）的最短路径： [1] 维基，最短路径问题： https:/
/
zh.wikipedia.org/
wiki/
%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra算法原理： https:/
/
blog.csdn.net/
yalishadaa/
article/
details/
55827681 ;
[3]RDocumentation: https:/
/
rdocumentation.org/
packages/
RNeo4j/
versions/
1.6.4/
topics/
dijkstra ;
[4]RDocumentation: https:/
/
rdocumentation.org/
packages/
igraph/
versions/
0.1.1/
topics/
shortest.paths ;
[5]Pypi: https:/
/
pypi.org/
project/
Dijkstar/
。

计算机网络中的距离向量算法（RIP）的基本原理？

RIP协议采用距离向量算法，在实际使用中已经较少适用。

在默认情况下，RIP使用一种非常简单的度量制度：距离就是通往目的站点所需经过的链路数，取值为1~15，数值16表示无穷大。

RIP进程使用UDP的520端口来发送和接收RIP分组。

RIP分组每隔30s以广播的形式发送一次，为了防止出现“广播风暴”，其后续的的分组将做随机延时后发送。

在RIP中，如果一个路由在180s内未被刷，则相应的距离就被设定成无穷大，并从路由表中删除该表项。

RIP分组分为两种：请求分组和响应分组。

计算机算法指的是什么

计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述。

无论算法有多么复杂，都必须在有限步之后结束并终止运行；
即算法的步骤必须是有限的。

在任何情况下，算法都不能陷入无限循环中。

算法必须是由一系列具体步骤组成的，并且每一步都能够被计算机所理解和执行，而不是抽象和模糊的概念。

算法首先必须是正确的，即对于任意的一组输入，包括合理的输入与不合理的输入，总能得到预期的输出。

如果一个算法只是对合理的输入才能得到预期的输出，而在异常情况下却无法预料输出的结果，那么它就不是正确的。

扩展资料特点1、有穷性。

一个算法应包含有限的操作步骤，而不能是无限的。

事实上“有穷性”往往指“在合理的范围之内”。

如果让计算机执行一个历时1000年才结束的算法，这虽然是有穷的，但超过了合理的限度，人们不把他视为有效算法。

2、 确定性。

算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。

算法中的每一个步骤应当不致被解释成不同的含义，而应是十分明确的。

也就是说，算法的含义应当是唯一的，而不应当产生“歧义性”。

3、有零个或多个输入。

所谓输入是指在执行算法是需要从外界取得必要的信息。

4、 有一个或多个输出。

算法的目的是为了求解，没有输出的算法是没有意义的。

5、有效性。

算法中的每一个 步骤都应当能有效的执行。

并得到确定的结果。

参考资料来源：-计算机算法。