算法设计与分析多段图最短路径问题

关于多段图最短路径问题的探讨摘要：

本⽂主要描述的是分别⽤动态规划法、贪⼼法和分⽀限界法来解决多段图最短路径问题时的情况，并在附录中附有实际问题的程序来辅助阐述观点。⽂章⾸先阐述了各个⽅法的原理，主要的思路是通过输⼊⼀组数据，⽐较三者的输出结果的准确性以及运⾏时间，以之为基础来分析、讨论三者的性能区别。另外，众所周知，多段图是有向图的⼀个简单的模型，它在有向图的基础上忽略了两点之间的线的双向性的问题，并且对点与点之间的线有很多的要求，从⽽把图简化为可分为⼏段的模式，⽂章最后讲述了若这⼏种⽅法运⾏到有向图中的情况，⼏种⽅法的对⽐和它们⽐较适应的使⽤情况的讨论，并给出了⾃⼰的建议。关键字：

多段图最短路径问题动态规划法分⽀限界法多段图与有向图的关系有向图最短路径算法引⾔：

当前社会，关于最短路径的问题屡屡出现。例如在开车⾃驾游的⼀个过程中，排除其他影响因素，从⼀个地点到另⼀点，这个时候必然是希望有⼀条距离最短的路程来尽量减少消耗的时间以及花费的（它们在模型中被称为代价），市场上对该问题的解决有很⼤的需求，因此，这⾥我将讨论多段图的最短路径的问题。

在早些时间的课程中，我们学习过数据结构这门课程，其中就包括最短路径这⽅⾯的讨论。当时⽼师给我们介绍了分别⾯向单源（Dijkstra算法）与⾮单源（Floyd算法）两种问题的算法法---，这是我们最早的对最短路径⽅⾯的理解，也是我们接触的⽐较早的关于图的问题。在这学期的

算法课程中，我们学习了许多了⽅法，包括贪⼼法、动态规划法等算法，

它们把以前学习的许多⽅法都命名并归纳分类起来，其中有许多算法都是可以⽤来解决这个最短路径的问题的，并且该问题作为⼀个图的问题，对该问题的继续探讨优化的需求很⼤，本⽂将就不同算法在解决该最短路径问题时的不同⽅法进⾏对⽐并给出该问题在不同基础上不同的最终解决

⽅案。由于时间的，本⽂将重点分析动态规划法下的情况，并会对图的情况加以简化、，最后会对其他的图做⼀些拓展。

⾸先，对多段图最短路径问题进⾏介绍，设图G=(V, E)是⼀个带权有向连通图，如果把顶点集合V划分成k个互不相交的⼦集Vi

（2≤k≤n, 1

≤i≤k），使得E中的任何⼀条边(u, v)，必有u∈Vi ，v∈Vi+m（1≤i＜k, 1

＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈Vk

为终点。多段图

的最短路径问题是求从源点到终点的最⼩代价路径。由于多段图将顶点划分为k个互不相交的⼦集，所以，多段图划分为k段，每⼀段包含顶点的⼀个⼦集。不失⼀般性，将多段图的顶点按照段的顺序进⾏编号，同⼀段内顶点的相互顺序⽆关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何⼀条边(u, v)，顶点u 的编号⼩于顶点v的编号。

这⾥我们讨论的多段图是可以分段的，各段之间的关系最好是单向的，即对该有向图来说，图中是没有环的存在的。

1.贪⼼法

贪⼼法在解决问题的策略上⽬光短浅，只根据当前已有的信息就做出选择，⽽且⼀旦做出了选择，不管将来有什么结果，这个选择都不会改变。换⾔之，贪⼼法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。

本例中利⽤的贪⼼算法，是每当要选择下⼀个结点时，总是选择与当前结点间代价最⼩的点，这就叫做总是优先局部最优解。以此得到最终的解序列。这⾥举⼀个贪⼼法的拓展例⼦Dijkstra算法。

Dijkstra算法是⼀种最短路径算法，⽤于计算⼀个节点到其它所有节点的最短路径，动态路由协议OSPF中就⽤到了Dijkstra算法来为路由计算最短路径。

算法本⾝并不是按照我们的正常思维习惯，我们⼀般会，从原点遍历所有与之相连的节点，找到最短路径，再从最短路径上的那个点遍历与之相连的所有其它点（原点除外），然后依次类推。这样做虽然可以算出⼀个树形，但是在⼤多数情况下，这种算法会产⽣很多次优路径，也就是说⾮最短路径。Dijkstra算法的⼤概过程：

假设有两个集合或者说两个表，表A和表B表A表⽰⽣成路径，表B表⽰最后确定的路径

1.从原点出发，遍历检查所有与之相连的节点，将原点和这些节点存放到表A中，并记录下两节点之间的代价。2.将代价最⼩的代价值和这两节点移动到表B中（其中⼀个是原点）。3.把这个节点所连接的⼦节点找出，放⼊到表A中，算出⼦节点到原点的代价

4.重复第⼆步和第三步直到表A为空。然后根据表B中的数据算出最优树。维基百科中还有另⼀种说法，Dijkstra算法的输⼊包含了⼀个有权重的有向图G，以及G中的⼀个来源顶点S。?我们以V表⽰G中所有顶点的集合。?每⼀个图中的边，都是两个顶点所形成的有序元素对。(u,v)表⽰从顶点u到v有路径相连。?我们以E所有边的集合，⽽边的权重则由权重函数w:?E?

→?[0,?∞]定义。?因此，w(u,v)就是从顶点u到顶点v的⾮负花费值(cost)。?边的花费可以想像成两个顶点之间的距离。任两点间路径的花

费值，就是该路径上所有边的花费值总和。?已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径.?最短路径)。?这个算法也可以在⼀个图中，找到从⼀个顶点s到任何其他顶点的最短路径。具体算法见附录。2.动态规划法

这⾥先讨论⽤动态规划法的解法。考虑多段图的最短路径问题的填表形式。⽤⼀个数组cost[n]作为存储⼦问题解的表格，cost[i]表⽰从顶点i到终点n-1的最短路径，数组path[n]存储状态，path[i]表⽰从顶点i到终点n-1的路径上顶点i的下⼀个顶点。则：+cost[j]} (i≤j≤n且顶点j是顶点i的邻接点) cost[i]=min{cij（式）

+cost[j]最⼩的j) path[i]=j (使cij（式）

对多段图的边(u, v)，⽤c uv表⽰边上的权值，将从源点s到终点t的最短路径记为d(s, t)，则从源点0到终点9的最短路径d(0, 9)由下式确定：d(0, 9)=min{c01+d(1, 9), c02+d(2, 9), c03+d(3, 9)}，这是最后⼀个阶段的决策，它依赖于d(1, 9)、d(2, 9)和d(3, 9)的计算结果，⽽由此模式推知，d(1, 9)=min{c14+d(4, 9), c15+d(5, 9)}，d(2,

9)=min{c24+d(4, 9), c25+d(5, 9), c26+d(6, 9)}，d(3, 9)=min{c35+d(5, 9),c36+d(6, 9)}，每⼀个d（i，n-1）都是通过min{c ik+d(k,n-1)}得到的k>i&&k

算法主要由三部分组成：第⼀部分是初始化部分，其时间性能为O(n)；第⼆部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环执⾏n-1次，内层循环对所有出边进⾏计算，并且在所有循环中，每条出边只计算⼀次。假定图的边数为m，则这部分的时间性能是O(m)；第三部分是输出最短路径经过的顶点，其时间性能是O(n)。所以，算法的时间复杂性为O(n+m)。为了实现时间的分析，在程序后添加了输出运⾏时间的函数，以便于对⽐分析。具体算法、具体代码及实验结果见附录1。3.分⽀限界法

再讨论当⽤分⽀限界法⽤来解决多段图路径问题的过程：

⾸先对该多段图应⽤贪⼼法求得近似解，并算出其代价路径。将其作为多段图最短路径问题的上界。⽽把每⼀段最⼩的代价相加，可以得到⼀个⾮常简单的下界。于是，就可以得到了⽬标函数的⼀个⼤致的范围。

由于多段图将顶点划分为k个互不相交的⼦集，所以，多段图划分为k段，⼀旦某条路径的⼀些段被确定后，就可以并⼊这些信息并计算部分

解的⽬标函数值的下界。⼀般情况下，对于⼀个正在⽣成的路径，假设已经确定了i段（1≤i≤k），其路径为(r1, r2, …, r i, ri+1)，此时，该部

分解的⽬标函数值的计算⽅法即限界函数如下：

应⽤分⽀限界法同样求解附录中图所⽰多段图的最短路径问题，具体

的搜索过程是这样进⾏的，⾸先考虑根节点，根据限界函数算出⽬标函数的值，然后下⼀个结点的选择在本例中有三种情况，这⾥每种情况下的

⽬标函数值下界都要算出来并且加以⽐较，下界的计算⽅法为除了加上选定点与初始点之间的距离外，以后的第⼀个点选择⼀选定点为初始点到下段最⼩代价的路径，以后的段与段之间的代价都按他们之间最⼩的代价来计算。这样再加上根节点与初始阶段之间的最⼩代价，就得到这种情况下的解了。在得到的代价中，找出最⼩的代价，并以之为初始结点循环往下做，直到到达⽬标结点。结论：

程序的运⾏截图如附录所⽰。分析各个⽅法的整个过程得到以下思考：

1.贪⼼法、动态规划法和分⽀限界法都可以⽤来解决多段最短路径问题，然⽽在这种情况相⽐之下，贪⼼法的运算效率⽐较⾼，因为它不像另外两种⽅法⼀样，需要涉及到许多的点。由于这⾥并没有找到函数有效地给程序计时（time函数很不精确，⽽对于⼩程序来说，就没有什么参考性）。因此这⾥我们就以本题的数据为例，⽤⼀个笨⽅法，看各个⽅法访问了多少数据，可以看到，动态规划法由于需要填表，并有⼀个相关的迭代问题，它⼏乎涉及了所有的点；⽽分⽀限界法，它通过贪⼼法设置的上下限，并以他们为依据进⾏剪枝，减少了许多的运算量。⽽贪⼼法，访问了最少的点。2.就结果准确性来看，就本题例⼦来看，贪⼼法结果为0 2 4 7 9，

路径的代价为20；动态分配法采取的路径为：0 3 5 8 9，路径的代价为16；⽽分⽀限界法，结果为0 3 5 8 9，路径的代价为16。可以看出，在这个⽅⾯，动态分配法和分⽀限界法都达到了预期的结果，相⽐直线，贪⼼法的误差就⽐较⼤了。由以上的讨论，我们可以看出分⽀限界法的综合性能⽐较好，他和动态规划法在解决多段最短路径问题时都可以得到正确解，⽽贪⼼法虽然可以省时间与空间，但结果不准确是它的缺点。各⽅法都是有利有弊的。因此在选择⽅法时，还应当根据实际情况。当只需要⼤概的⼀个解时，当然是要⽤省时省⼒的贪⼼法；如果对结果⼜⽐较⾼的要求的话，那么就要采取动态规划法或分⽀限界法。那么dijkstra算法呢，他的明显优点就是它的多⽤性，他可以求任意⼀点到其他某⼀点的距离，但是他访问的数据量很⼤，⼏乎要访问所有的边（相对于贪⼼法⽽⾔），因此这⾥来说，在单纯的解决多段最短路径问题时，他们的功能都差

不多，⽽在解决其他较复杂的图时，Dijkstra算法有明显的优越性，但当然，作为贪⼼法的⼀种，他的结果的准确性不是那么的⾼。Dijkstra算法在本质上为贪⼼算法,每⼀步的选择为当前步的最优,复杂度为O(n*n)。动态规划法是可以看作是对分⽀限界法的改进。

分⽀限界算法,每⼀步的扩散为当前耗散度的最优,复杂度为(没算)其实，他们各有各的优缺点，可以尝试将他们混合起来⽤，扬长避短，像动态规划法和分⽀限界法，我们是不是可以试着在动态规划法的过程中像分⽀限界法⾥⼀样，设置范围，并且过程中对肯定不会是最后结果的数据“剪枝”。这样就可以提⾼运⾏速率了。结论（必须精确、有条理、清晰与简要）：建议（直接从结论中得出）：附录

Dijstra算法（边的拓展）{While（!(每⼀个d[v]==最短路径)）If（存在⼀条从u到v的边）If(d[u]+w(u,v)d[v]= d[u]+w(u,v);

⽤动态规划法解决多段图的最短路径算法为：

1．初始化：数组cost[n]初始化为最⼤值，数组path[n]初始化为-1；2．for (i=n-2; i>=0; i--)对顶点i的每⼀个邻接点j，根据式计算cost[i];根据式计算path[i];

3．输出最短路径长度cost[0];4. 输出最短路径经过的顶点：i=0

循环直到path[i]=n-1输出path[i];i=path[i];

⽤分⽀限界法求解多段图的最短路径问题的算法：

1．根据限界函数计算⽬标函数的下界down；采⽤贪⼼法得到上界up； 2．将待处理结点表PT初始化为空；3．for (i=1; i<=k; i++) x[i]=0;4．i=1; u=0; //求解第i段5．while (i>=1)对顶点u的所有邻接点v根据式计算⽬标函数值lb;

若lb<=up，则将i,,lb存储在表PT中；

如果i= =k-1且叶⼦结点的lb值在表PT中最⼩，则输出该叶⼦结点对应的最优解；

否则，如果i= =k-1且表PT中的叶⼦结点的lb值不是最⼩，则up=表PT中的叶⼦结点最⼩的lb值;将表PT中⽬标函数值超出up的结点删除；

u=表PT中lb最⼩的结点的v值；i=表PT中lb最⼩的结点的i值；i++;动态规划法解决多段图最短路径问题：/*多段图最短路径问题总结:

cost[i]表⽰从顶点i到终点n-1的最短路径，path[i]表⽰从顶点i到终点n-1的路径上顶点i的下⼀个顶点；下⾯的公式重点：cost[i]=min{c(ij)+cost[j]}

path[i]=使c(ij)+cost[j]最⼩的j; c(ij)表⽰i和j顶点之间的距离*/具体代码如下：#include<>#include

#define INFINITY 32767#define MAX 20__int start,end;int min[6],Part;typedef struct{

char vexs[MAX]; //顶点信息int vexnum,arcnum;

int arcs[MAX][MAX]; //保存两个顶点之间的边长}Graph; //图的结构体struct node{

int part,node1,node2,lb,previous;struct node *next;};

void CreateGraph(Graph &G){//初始化多段图int i,j;start=clock();

printf(\"请输⼊顶点数和边数：\");//scanf(\"%d %d\=10; //顶点数=18; //边的数for(i=0;i<;i++){[i]=i;}

for(i=0;i<;i++){for(j=0;j<;j++)[i][j]=INFINITY;

}

printf(\"请按以下格式输⼊边的代价（顶点1 顶点2 两点之间边的代价，顶点标号从0开始）：\\n\");for(k=0;k<;k++){

scanf(\"%d %d %d\}

int getDown(Graph G){//分⽀限界法求下界

int j,k,i,n,n0,down=0,initial[6][20];//initial数组⽤来存储第i段有哪些结点min[0]=INFINITY;for(i=0;i<6;i++){for(j=0;j<20;j++)initial[i][j]=0;}j=0;

for(i=0;i<;i++){if[0][i]

initial[0][j++]=i;if[0][i]min[0]=[0][i];}}Part=1;down+=min[i];i=0;

while(initial[i++][0]!={n=0;j=0;min[i]=INFINITY;while(initial[i-1][j++]!=0){k=0;n0=n;while((k++)down+=min[i];Part++;}}

return down;}

int Greedy(Graph G,int flag,int up){//贪⼼法int min=INFINITY,m=flag;printf(\"%d\for(int i=0;i<;i++){if[m][i]min=[m][i];flag=i;}}if(flag<{printf(\"->\");

up=Greedy(G,flag,up);}

else printf(\"->%d\\n\return up+min;}

void path(Graph G,int up){//分⽀限界法int down,i,j,k,u,lb,flag=1,previous=0;struct node *p,*end,*PT,*q,*ST,*End,*mins;down=getDown(G);

printf(\"\\n若⽤分⽀限界法，该题的结果取值范围为[%d,%d]。\\n\

PT=NULL;end=NULL;ST=NULL,End=NULL;//PT⽤来存储合格的点，ST表⽤来存储由于拓展被删除的点i=1;u=0; //求解第i段,u表⽰顶点，u是那个已确定的顶点while(flag){// 对顶点u的所有邻接点v// 根据式计算⽬标函数值lb;

// 若lb<=up，则将i,,lb存储在表PT中；for(j=0;j<;j++){//u=3,i=2

int mini=INFINITY;//mini是⽤来存储选择的那个下个结点所连接的最短的路径if(mini>[u][j]){

for(k=0;k<;k++){//确定了结点以后找到由他出发最⼩的代价if[j][k]mini=[j][k];}

lb=[u][j]+mini;for(int l=i+1;l

lb+=min[l];//min[]数组存的是每段中最短的路径长度int Previous=previous;int U=u;if(U>0){//计算lblb+=[Previous][U];while(Previous!=0){p=PT;

while(p!=NULL)

if(p->node1==Previous&&p->node2==U){lb+=[Previous][U];U=Previous;

Previous=p->previous;break;}}}

if(lb<=up){

struct node *p=new struct node;p->part=i+1;p->node1=u;p->node2=j;p->lb=lb;p->next=NULL;p->previous=previous;

printf(\"%d->%d,代价%d,上⼀个结点为%d\\n\if(PT==NULL) PT=p;else end->next=p;end=p;

end->next=NULL;

}}}

q=PT;lb=INFINITY;while(q!=NULL){if(q->lbmins=q;lb=q->lb;}

q=q->next;

}printf(\"%d %d lb=%d\if(p==q && [end->node2][]int dist=0,array[6]={0,0,0,0,0,0};array[Part]=;

array[Part-1]=p->node2;array[Part-2]=p->node1;i=Part-3;while(i>=0){

array[i]=p->previous;i--;q=PT;

while(q->node2!=array[p->previous])q++;if(i>0)

array[i-1]=q->node1;p=q;}

printf(\"最短路径为：\");for(i=0;i

printf(\"%d->\if(i

dist+=[i][i+1];}

printf(\"%d\

printf(\"⽤分⽀限界法得到的最短路径长度为：%d\flag=0;

break;}p=PT;

if(p->node1==mins->node1&&p->node2==mins->node2){//删除PT 链表中已被拓展的结点并把他添加到ST链表中if(ST==NULL)ST=p->next;else

End->next=p->next;End=p->next;End->next=NULL;PT=PT->next;//printf(\"删除的结点

是：%d %d\\n\}/*else{

printf(\"删除的结点是：%d %d\\n\while(p->next!=NULL){

if(p->next->node1==mins->node1&&p->next->node2==mins->node2) {if(ST==NULL){ST=p->next;}else{

End->next=p->next;}

End=p->next;End->next=NULL;p->next=p->next->next;

printf(\"删除的结点是：%d %d\\n\break;}

p=p->next;}*/

previous=u;u=mins->node2;i=mins->part;

printf(\"最⼩的结点是%d,在第%d部分\\n\}}/*

如果i==k-1且叶⼦结点的lb值在表PT中最⼩，则输出该叶⼦结点对应的最优解；否则，如果i==k-1且表PT中的叶⼦结点的lb值不是最⼩，则up=表PT中的叶⼦结点最⼩的lb值;将表PT中⽬标函数值超出up的结点删除；u=表PT中lb最⼩的结点的v值；i=表PT中lb最⼩的结点的i值；i++;*/

void Path(Graph G){//动态规划法int i,j,temp=0;int n=10;

int cost[10]; //存储⼦问题表的表格cost[i]表⽰从顶点i到终点n-1的最短路径int path[10]; //存储状态,path[i]表⽰从顶点i 到终点n-1的路径上顶点i的下⼀个顶点for(i=0;i