二 最短路径问题

在研究的过程中会出现最短路径问题，它在图论中占有非常重要的地位。也是图论中重要的一个研究课题，是在现实生活中运用较广的一类优化问题之一，其目的就是要求一个网络图中，给定的一个起点到另一个顶点的权的最小距离。旅游线路，管道，交通线路铺运行轨道预测等问题都涉及到了最短路径问题，可以说最短路径问题在实际生活中具有广泛的运用。

2.1基本概念与基本定理

定义9-12:设已给定了一个赋权有向图G(V,A,)。对每一条弧a(vi,vj)相应的有权(a)ij，又有vs，vt是G(V,A,)中任意取定的两个点，若p是G中从vs到vt的一条路，则称p中所以弧的权之和为路p的权(或称为路长)，记为:(p)ij最短路径问题就是要在所以从vs到vt的路中，求一条权最小的路，即求一条从vs到vt的路p，使得(p)min{(p)|p则称p为从vs到vt的最短路径。路径p的权称为从顶点vs到vt的距离，记为d(vs,vt)，显然，d(vs,vt)不等于d(vt,vs)。对于最短路径，显然有下列定理成立:

定理9-5：设赋权有向图G(V,A,)，V{v1,v2,....vn}记d(vj)为点v1到点vj的最短路径的路长，且不妨设当1<i<j时，有0<d(vi)<d(vj)<，则有的弧的权数。该定理体现了如下最优性原理:若p是从点vi到vj的最短路，vi是p上某一点，那么从点v1沿p到点vi的路是从v1到vj的最短路径。

2.2最短路径的Dijkstra算法

Dijkstra算法是由狄克斯特拉(E.M.Dijkstra)于1959年提出的求网络最短路径的标号法，通过给顶点记标号(T,P标号)来逐步形成起点到各点的最短路径及其距离值，它被公认为目前相关领域中较好的一种算法。该算法只适合用于求所以弧的权数均为非负(即所以ij0)的网络最短路径问题，并能给出从指定顶点到图中每个顶点的最短路径及其距离。当赋权有向图中存在负权数时，该算法失效，此时采用别的方法来寻求最短路径。

2.2.1算法基本思想

Dijkstra算法基本思想源于动态规划原理，首先vs从出发，逐步的向外探索最短路径。在执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路径的权(称为p标号)，或者是从vs到该点的最短路径的权的上界(称为T标号)。算法的每一步是去修改T标号，把某一个具有T标号的点改为具有p标号的点，当终点l得到p标号时，全部计算结束。