求图中受限制的所有最短路径算法的分析与研究

摘要

最短路径算法是图论、计算机网络、地理信息系统、交通咨询等诸多领域中研究的热门课题。它主要应用于路径搜索、网络寻优等方面。最短路径算法中较经典的有Dijkstra、Floyd等算法,这些算法只涉及到单目标优化,即只求出一条从一个顶点到另外一个顶点的最短路径及长度。随着科学技术的发展,单一目标往往很难准确地描述和解决现实生活中的问题,因此,带限制条件的最短路径算法具有较强的实用价值和更广泛的应用领域。本文就是基于此背景,展开对受限制的最短路径算法的讨论和研究的。本文提出了受限制条件的最短路径算法。这些算法在物流运输、交通路线的确定上起着重要的作用。本文首先介绍了最短路径算法的研究现状、研究意义。其次介绍了图以及常用算法的相关知识。接着对受限制最短路径算法以及本文提出的算法进行了详细地阐述。
　　本文重点在于第三章。一共提出了三种相关算法。1、提出了一个求图中一个顶点到另外一个顶点间所有最短路径的算法。该算法是从终点开始对邻接到该点的结点出度减1,求出终点到该结点的当前最短路径长度,保存其有效直接后继结点,对出度为0的结点做同样的操作,依次类推,直到出度为0的结点都被处理完时,可以求出源点到终点的最短路径长度以及最短路径上各个结点的有效直接后继结点序列。本算法较以前的同类算法有易于理解,时间复杂度低等优点,其时间复杂度为O(n~2×(sh1(G,i,j))(n为图中结点总数,sh1(G,i,j)为图中实际的最短路径条数)。2、提出了一个受费用和顶点数限制的最短路径算法,该算法为每个结点各设置了一个状态链表,从源点状态开始求出其邻接点的满足限制条件的状态,并将状态存放在该结点的状态链表中,依此类推,直到终点为止。此时,终点的状态链表中存放的是满足限制条件的状态,路径长度最小的一个或者多个状态是满足限制条件的最短路径的终点状态,也可以求出满足限制条件的次短和再次短路径。其时间复杂度为O(n~2×N)(n为图中顶点个数,N为结点的状态数目的最大值)。3、提出了一个改进的受费用和顶点数限制的最短路径算法。该算法利用顶点数限制为树高,费用限制作为判断条件,建立一棵满足限制条件的最短路径树,求出满足限制条件的所有最短路径。其时间复杂度为O(k×n×sh2(G,k,1))(k为受限制的顶点数,sh2((G,k,1)为图中满足费用和顶点数限制的实际最短路径条数)。每个算法针对实例图做了仿真实验,并分析了实验结果,验证了算法的正确性与高效性。最后对本文提出的算法进行了总结与展望。

目录

摘要

Abstract

第一章 绪论

1.1 研究背景及研究意义

1.2 国内外研究现状

1.3 本文的主要工作

1.4 本论文的内容安排

第二章 图和最短路径算法

2.1 图的基本概念

2.2 图的表示

2.3 常用算法

2.3.1 递归法

2.3.2 回溯法

2.3.3 分治法

2.3.4 动态规划法

2.3.5 分支限界法

2.4 常用的最短路径算法

2.4.1 单源最短路径算法

2.4.2 每对顶点间的最短路径算法

2.5 受限制的最短路径算法及模型

2.5.1 受单一限制的最短路径算法及模型

2.5.2 受多种限制的最短路径算法及模型

2.6 所有最短路径算法

2.7 本文提出的受限制的最短路径算法及模型

2.8 其它相关最短路径算法

2.9 小结

第三章 本文提出的求解算法

3.1 引言

3.2 求图中顶点间的所有最短路径的算法

3.2.1 存储结构

3.2.2 算法思想及可行性分析

3.2.3 算法实现

3.2.4 算法分析

3.2.5 实验仿真

3.2.7 本节小结

3.3 求受顶点数限制和费用限制的最短路径的算法

3.3.1 存储结构

3.3.2 算法思想及可行性分析

3.3.3 算法实现

3.3.4 算法分析

3.3.5 实验仿真

3.3.6 本节小结

3.4 求受费用限制和顶点数限制的最短路径改进算法

3.4.1 存储结构

3.4.2 算法思想及可行性分析

3.4.3 算法实现

3.4.4 算法分析

3.4.5 实验仿真

3.4.6 本节小结

3.5 本章小结

第四章 总结与展望

4.1 本文总结

4.2 算法展望

参考文献

攻读学位期间发表的论文

致谢