最短路径算法是图论、计算机网络、地理信息系统、交通咨询等诸多领域中研究的热门课题。它主要应用于路径搜索、网络寻优等方面。最短路径算法中较经典的有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)为图中满足费用和顶点数限制的实际最短路径条数)。每个算法针对实例图做了仿真实验,并分析了实验结果,验证了算法的正确性与高效性。最后对本文提出的算法进行了总结与展望。