2。2。2最短路径问题

如果在赋权图中给定一个顶点（称为始点）还有一个顶点（称为终点）那么，最短路径问题就是在的道路集合中，找出长为最小的道路，这样的最小的道路被称为从到的最短路径。从到的最短道路径的长记为。

最短路径问题是图论中的一个基本问题。在赋权图中，每条边都有一个数值(长度、时间、成本等)，找出的两个节点之间总权和最小的路径就是要求的最短路径。

最短路径问题，通常归属为三类：

(1)单源最短路径问题：分为确定起点的最短路径问题和确定终点的最短路径问题两类。确定终点的最短路径问题和确定起点的最短路径问题相反，这个问题是已知终点，求最短路径问题。在无向图中和确定起点的问题完全等同。但是在有向图中则相当于把所有路径方向反转的（终点视为起点）确定起点的最短路径问题。

(2)确定起点和终点的最短路径问题：已经知道起点和终点，求这两个结点之间的最短路径。

(3)全局最短路径问题：求图中所有的最短路径。

  2。2。3最短路问题算法的基本思想及基本步骤

目前，求解交通运输网络上各个节点之间的最短路径的方法中,国内外一致认为的比较好的算法有迪杰斯特拉(Dijkstra)算法和弗罗伊德(Floyd)算法两种。在这两种算法中,交通运输网络都先被抽象为一个在图论中定义的有向图或者无向图,再利用图的节点的邻接矩阵来记录点间的关联信息。在通过图的遍历的方法来搜索最短路径时,以邻接矩阵为基础不断进行最小性判别,直到得到最优化路径为止。来.自^优+尔-论,文:网www.youerw.com +QQ752018766-

图论中确定最短路的基本方法是Dijkstra算法,同时，它也是其它算法的基础。求赋权图中任意两结点之间的最短路径的问题中,我们通常采用两种方法。第一种方法是以一个结点为源点,一直重复执行Dijkstra算法n次，直到获得最优路径。第二种方法是Floyd在1962年提出的Floyd算法,这种算法的时间复杂度与重复执行Dijkstra算法n次的时间复杂度相同，都是为。

1） Dijkstra算法

当赋权图中的所有的权数时，我们一般使用Dijkstra算法。Dijkstra算法的基本思想是从设置的起点开始，逐一向外发展。再探索过程中，每到一个点，都记录下从起点开始的路径与路程，称为这个点的标号。所以Dijkstra算法也被称为标号法。

具体的标号通常由两部分组成，第一部分是一个字母或者数字，来表示前面的一个点的符号，说明当前路径从哪里来；第二部分是一个数字，通常表示从起点到当前结点的距离，说明当前路径的长度。利用标号法，最多经过次，就可以求出从起点到终点的最短路径和最短路径长度。