最短路径问题手抄报

发布网友发布时间：2022-10-26 10:48

共1个回答

热心网友时间：2023-09-14 07:10

最短路径问题是组合优化领域的经典问题之一，它广泛应用于计算机科学、交通工程、通信工程、系统工程、运筹学、>信息论、控制理论等众多领域。>Dijkstra算法是经典的最短路径算法。

一、相关算法

1、Dijkstra算法

Dijkstra算法是经典的最短路径算法，其基本思想是:设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径，重复上述过程，直到集合V中全部顶点加入到集合S中。使用该算法找到的是全局最优的最短路径，在网络节点数量大、网络边数较多时，存在内存占用大、时间复杂度高等不足，并且Dijkstra算法不能很好地解决含必经点约束的最短路径问题。

2、Floyd算法

算法的特点：

弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。

通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵S中的元素a[j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[j]，表示顶点i到顶点j经过了b[j]记录的值所表示的顶点。

假设图G中顶点个数为N，则需要对矩阵D和矩阵P进行N次更新。初始时，矩阵D中顶点a[j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[j]=∞，矩阵P的值为顶点b[j]的j的值。接下来开始，对矩阵D进行N次更新。第1次更新时，如果”a[j]的距离” > “a+a[j]”(a+a[j]表示”i与j之间经过第1个顶点的距离”)，则更新a[j]为”a+a[j]”,更新b[j]=b。同理，第k次更新时，如果”a[j]的距离” > “a[k-1]+a[k-1][j]”，则更新a[j]为”a[k-1]+a[k-1][j]”,b[j]=b[k-1]。[1]

3、蚁群算法

>蚁群算法是由Dorigo、Maniezzo和Colorni等于1991 年首先提出来的，它来源于蚂蚁寻食的行为。通过研究发现，蚂蚁个体之间是通过一种叫做信息素的外激素进行信息传递的。蚂蚁在行走过程中能感知周围信息素的强度，并朝着信息素浓度高的方向移动，当某只蚂蚁发现食物时，它在回巢的过程当中，会在返回的路上释放信息素作为标记，同伴发现后会沿着此路寻找到食物。当同伴中多只蚂蚁都发现了食物但路径长短不同时，因为蚂蚁在短的路径上往返所需要的时间相对较小，所以单位时间内走过的蚂蚁越来越多，在这条路径上的信息素浓度就会越强，因此，该路径上的蚂蚁就会越来越多，逐渐选出一条最优的道路。

二、分类

可分成两个子问题，即单源最短路径问题和所有顶点对之间的最短路径问题。前者是找出从某一顶点出发到图中所有其他顶点的最短路径，主要算法有迪克斯彻算法等;后者是求图中每一对顶点之间的最短路径，主要算法有弗洛伊德算法等。

三、应用

1、通信领域

互联网技术和应用的不断发展，对当今网络通信流量的要求不断增大。流量大、速度快、费用低的传输方式是网络传输的关键。路径最短、代价最低的网络路由能够大大降低通信成本、节约网络资源，提高网络资源的利用率。

2、交通运输

最短路径问题是交通分配中最基本的问题，是指一对节点之间的路径中总阻抗最小的路径，几乎所有交通流分配方法都是以它作为一个基本子过程反复调用。