单源最短路径(两种方法)

1、单源最短路径计科一班 李振华 20120407111、 问题描述给定带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。2、 问题分析推导过程（最优子结构证明，最优值递归定义）1、 贪心算法对于图G，如果所有Wij0的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。Dijkstra方法的

2、基本思想是从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs 到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具 P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。在叙述Dijkstra方法的具体步骤之前，说明一下这个方法的基本思想。s=1。因为所有Wij0，故有d(v1, v1)=0。这时，v1是具P标号的点。现在考察从v1发出的三条弧，(v1, v2), (v1, v3

3、)和(v1, v4)。（1）如果某人从v1出发沿(v1, v2)到达v2，这时需要d(v1, v1)+w12=6单位的费用；（2）如果他从v1出发沿(v1, v3)到达v3，这时需要d(v1, v1)+w13=3单位的费用；（3）若沿(v1, v4)到达v4，这时需要d(v1, v1)+w14=1单位的费用。因为min d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v1)+w14= d(v1, v1)+w14=1，可以断言，他从v1到v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1, v4)，d(v1, v4)=1。这是因为从v1到v4的任一条路P，如果不

4、是(v1, v4)，则必是先从v1沿(v1, v2)到达v2，或者沿(v1, v3)到达v3。但如上所说，这时他已需要6单位或3单位的费用，不管他如何再从v2或从v3到达v4，所需要的总费用都不会比1小(因为所有wij0)。因而推知d(v1, v4)=1，这样就可以使v4变成具P标号的点。（4）现在考察从v1及v4指向其余点的弧，由上已知，从v1出发，分别沿(v1, v2)、(v1, v3)到达v2, v3，需要的费用分别为6与3，而从v4出发沿(v4, v6)到达v6所需的费用是d(v1, v4)+w46=1+10=11单位。因min d(v1, v1)+w12，d(v1, v1)+w13，

5、d(v1, v4)+w46= d(v1, v1)+w13=3。基于同样的理由可以断言，从v1到v3的最短路是(v1, v3)，d(v1, v3)=3。这样又可以使点v3变成具P标号的点，如此重复这个过程，可以求出从v1到任一点的最短路。在下述的Dijstra方法具体步骤中，用P，T分别表示某个点的P标号、T标号，si表示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从Vs到各点的最短路，给每个点v以一个值，算法终止时(v)=m，表示在Vs到v的最短路上，v的前一个点是Vm；如果(v)= ，表示图G中不含从Vs到v的路；(Vs)=0。Dijstra方法的具体步骤：初始化i

6、=0S0=Vs，P(Vs)=0 (Vs)=0对每一个vVs，令T(v)=+ ，(v)=+ ，k=s开始如果Si=V，算法终止，这时，每个vSi，d(Vs,v)=P(v)；否则转入考察每个使(Vk,vj)E且vj Si的点vj。如果T(vj)P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把(vj)修改为k。令 如果，则把的标号变为P标号，令 ，k=ji，i=i+1，转，否则终止，这时对每一个vSi，d(vs,v)=P(v)，而对每一个。在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。2、分支限界法算法从图G的源顶点s和空优先队列开始。

7、结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应

8、的树中的结点为根的子树剪去。3、 计算求解过程、算法实现（源代码实现相关功能）1、 贪心算法#include #include using namespace std;#define MAX 1000000/充当无穷大#define LEN sizeof(struct V_sub_S)#define N 5#define NULL 0int s;/输入的源点int DN;/记录最短路径int SN;/最短距离已确定的顶点集const int GNN = 0, 10, MAX, 30, 100,MAX, 0, 50, MAX, MAX,MAX, MAX, 0, MAX, 10,MAX, MAX,

9、 20, 0, 60,MAX, MAX, MAX, MAX, 0 ;typedef struct V_sub_S/V-S链表int num;struct V_sub_S *next;struct V_sub_S *create()struct V_sub_S *head, *p1, *p2;int n = 0;head = NULL;p1 = (V_sub_S *)malloc(LEN);p1-num = s;head = p1;for(int i = 0; i next = p1;p2 = p1;p1 = (V_sub_S *)malloc(LEN);p1-num = i;p1-next =

10、 NULL;free(p1);return head;struct V_sub_S *DelMin(V_sub_S *head, int i) /删除链表中值为 i 的结点V_sub_S *p1, *p2;p1 = head;while(i != p1-num & p1-next !=NULL)p2 = p1;p1 = p1-next;p2-next = p1-next;return head;void Dijkstra(V_sub_S *head, int s)struct V_sub_S *p;int min;S0 = s;for(int i = 0; i N; i +)Di = Gsi;

11、for(int i = 1; i next;min = p-num;while(p-next != NULL)if(Dp-num D(p-next)-num)min = (p-next)-num;p = p-next;Si = min;head = DelMin(head, min);p = head-next;while(p != NULL)if(Dp-num Dmin + Gminp-num)Dp-num = Dmin + Gminp-num;p = p-next;void Print(struct V_sub_S *head)struct V_sub_S *p;p = head-next

12、;while(p != NULL)if(Dp-num != MAX)cout D num : num next;elsecout D num : next;int main()struct V_sub_S *head;cout s;head = create();Dijkstra(head, s);head = create();Print(head);system(pause);return 0;2、 分支限界法#include #include using namespace std;#define MAX 9999#define N 60int n,distN,aNN;class Hea

13、pNodepublic: int i,length; HeapNode() HeapNode(int ii,int l) i=ii; length=l; bool operator(const HeapNode& node)const return lengthnode.length; ;void shorest(int v) priority_queue heap; HeapNode enode(v,0); for(int i=1; i=n; i+) disti=MAX; distv=0; while(1) for(int j=1; j=n; j+) if(aenode.ijMAX & en

14、ode.length+aenode.ijn; for(int i=1; i=n; i+) for(int j=1; jaij; if(aij=-1) aij=MAX; shorest(1); for(int i=2; in; i+) coutdisti ; coutdistnO（E*lgV）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V2） 。可以用优先队列进行优化，优化后时间复杂度变为0（v*lgn）。5、 算法改进Dijkstra算法的运行时间要低，但它要求所有边的权值非负。Dijkstra算法中设置了一个顶点集合S，从源点s到集合中的顶点的最终最短路径的权值均已确定。算法反复选择具有最短路径估计的顶点uV-S，并将u加入S中，对u的所有出边进行松弛。由于总是在V-S中选择“最近”的顶点插入集合S中，可以说Dijkstra算法使用了贪心策略。可以想象，在Dijkstra算法的执行过程中，最短路径估计