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

#define MAX 20 __int64 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(\G.vexnum=10; //顶点数 G.arcnum=18; //边的数 }

G.vexs[i]=i;

for(i=0;i

for(i=0;i

printf(\请按以下格式输入边的代价（顶点1 顶点2 两点之间边的代价，顶点标号从0for(k=0;k

scanf(\

开始）：\\n\

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++){ } j=0;

for(i=0;i

initial[0][j++]=i;

if(G.arcs[0][i]

}

}

Part=1;

down+=min[i];

i=0;

while(initial[i++][0]!=G.vexnum-1){ n=0;j=0;min[i]=INFINITY;

while(initial[i-1][j++]!=0){

k=0;n0=n;

while((k++)

if(G.arcs[initial[i-1][j-1]][k-1]

min[i]=G.arcs[initial[i-1][j-1]][k-1];

}

if(min[i]

down+=min[i]; Part++;

}

return down;

}

int Greedy(Graph G,int flag,int up){//贪心法 }

int min=INFINITY,m=flag; printf(\

for(int i=0;i

if(G.arcs[m][i]

min=G.arcs[m][i]; flag=i;

if(flag

up=Greedy(G,flag,up);

else printf(\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(\若用分支限界法，该题的结果取值范围为[%d,%d]。\\n\PT=NULL;end=NULL;ST=NULL,End=NULL;//PT用来存储合格的点，ST表用来存储由

于拓展被删除的点 i=1;u=0; //求解第i段,u表示顶点，u是那个已确定的顶点 径

if(mini>G.arcs[u][j]){ for(k=0;k

if(G.arcs[j][k]

while(flag){

// 5.1对顶点u的所有邻接点v

// //

5.1.1 根据式9.3计算目标函数值lb;

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

for(j=0;j

}

lb=G.arcs[u][j]+mini;

for(int l=i+1;l

if(U>0){//计算lb

lb+=G.arcs[Previous][U]; while(Previous!=0){

p=PT;

while(p!=NULL)

if(p->node1==Previous&&p->node2==U){ lb+=G.arcs[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\\n\

}

if(PT==NULL) PT=p; else end->next=p; end=p;

end->next=NULL;

价%d,上一个结点

}

}

q=PT;lb=INFINITY; while(q!=NULL){

if(q->lblb; } q=q->next;

}printf(\

if(p==q && G.arcs[end->node2][G.vexnum-1]

}

int dist=0,array[6]={0,0,0,0,0,0}; array[Part]=G.vexnum-1; 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(\

if(i

printf(\

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;