数据结构求图中任意两点短路径.docx
- 文档编号:4986795
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:12
- 大小:36.92KB
数据结构求图中任意两点短路径.docx
《数据结构求图中任意两点短路径.docx》由会员分享,可在线阅读,更多相关《数据结构求图中任意两点短路径.docx(12页珍藏版)》请在冰点文库上搜索。
数据结构求图中任意两点短路径
数据结构求图中任意两点短路径
————————————————————————————————作者:
————————————————————————————————日期:
《数据结构》实验报告
◎实验题目:
求最短路径。
◎实验内容:
求图中任意两点间的最短路径。
一、需求分析
程序目的是求有向图中任意两点间的最短路径。
1、由用户指定图中任意两点。
2、输出结果为指定两点间的最短路径。
二概要设计
1、定义结构体
typedefstructArcNode//节点类型
{
intadjvex;
structArcNode*nextarc;
InfoType_Costcost;
InfoType_Lengthlength;
}ArcNode;
typedefstructVNode//城市编号
{
intNo;
VertexTypecity[15];
ArcNode*firstarc;
}VNode,AdjList[MAX_VERTX_NUM];
typedefstructALGraph//图
{
AdjListvertices;
intvexnum;
intarcnum;
}ALGraph;
typedefstructstr1
{
intvalue_D;
intflag_S;
}D[20];
typedefstructstr2
{
intfather;
}P[20];
2.定义函数
voidAnalyse_Info()
操作结果:
读入文件,将信息存入数组
ALGraphCreate_Graph()
操作结果:
创建一个图
voidShortPath_DIJ(ALGraphG,intv_sou)
初始条件:
已知图G;
操作结果:
用Dijkstra算法求任意两点之间最短路径。
voidInfoCustomer(ALGraphG,str2p[],str1d[],intv_sou,intv_des,intmethod)
操作结果:
将最短路径结果呈现给用户。
三详细设计
#defineINT_MAX65534
#defineINFINITYINT_MAX
#defineMAX_VERTX_NUM20
#defineFALSE-1
#defineTRUE1
typedefcharVertexType;
typedefintInfoType_Cost;
typedefintInfoType_Length;
typedefstructArcNode//节点类型
{
intadjvex;
structArcNode*nextarc;
InfoType_Costcost;
InfoType_Lengthlength;
}ArcNode;
typedefstructVNode//城市编号
{
intNo;
VertexTypecity[15];
ArcNode*firstarc;
}VNode,AdjList[MAX_VERTX_NUM];
typedefstructALGraph
{
AdjListvertices;
intvexnum;
intarcnum;
}ALGraph;
typedefstructstr1
{
intvalue_D;
intflag_S;
}D[20];
typedefstructstr2
{
intfather;
}P[20];
intarcnum=0,vexnum=0;
charcity[20][15];
intpath[52],cost[52];
charcity_1[52][20],city_2[52][20];
PPath_cost,Path_len;
DDear_cost,Dear_len;
voidAnalyse_Info()//读入文件,将信息存入数组
{
FILE*fp;
inti=0,j=0,k=0;
intflag_1=0,flag_2=0;
intCityCounter=0,LineCounter=0;
fp=fopen("data.txt","r");
while(!
feof(fp))
{
fscanf(fp,"%s%s%d%d\n",city_1[i],city_2[i],&cost[i],&path[i]);
LineCounter++;
i++;
}
arcnum=LineCounter;
for(i=0;i<20;)
{
for(k=0;k<52;k++)
{
for(j=0,flag_1=0,flag_2=0;j<=i;j++)//剔除重复出现的城市
{
if(strcmp(city[j],city_1[k])==0)
flag_1=1;
if(strcmp(city[j],city_2[k])==0)
flag_2=1;
}
if(flag_1==0)
{
strcpy(city[i],city_1[k]);
CityCounter++;
i++;
}
if(flag_2==0)
{
strcpy(city[i],city_2[k]);
CityCounter++;
i++;
}
}
if(strlen(city[i])==0)i++;
}
vexnum=CityCounter;
fclose(fp);
}
ALGraphCreate_Graph()//创建图
{
ALGraphG;
inti=0,j,k;
ArcNode*p,*q,*e;
Analyse_Info();
G.arcnum=arcnum;
G.vexnum=vexnum;
for(i=0;i<20;i++)
{
G.vertices[i].firstarc=(ArcNode*)malloc(sizeof(ArcNode));
G.vertices[i].firstarc->nextarc=NULL;
}
printf("******序号————城市名********\n");
for(i=0;i { G.vertices[i].No=i; strcpy(G.vertices[i].city,city[i]); printf("%d————%s\n",G.vertices[i].No,G.vertices[i].city); } for(i=0;i<52;i++) for(j=0;j<20;j++) if(strcmp(city[j],city_1[i])==0) { for(k=0;k<20;k++) if(strcmp(city[k],city_2[i])==0) { p=G.vertices[j].firstarc; while(p! =NULL) { q=p; p=p->nextarc; } e=(ArcNode*)malloc(sizeof(ArcNode)); e->adjvex=k; e->cost=cost[i]; e->length=path[i]; e->nextarc=NULL; q->nextarc=e; } } returnG; } voidShortPath_DIJ(ALGraphG,intv_sou)//用Dijkstra算法求最短路径 { inti,j,no_cost,no_path; intmin_cost,min_len; ArcNode*p,*p1,*p2; for(i=0;i<20;i++)//初始化辅助向量 { Path_cost[i].father=i; Path_len[i].father=i; } for(i=0;i<20;i++) { Dear_cost[i].value_D=INFINITY; Dear_len[i].value_D=INFINITY; Dear_cost[i].flag_S=FALSE; Dear_len[i].flag_S=FALSE; } p=G.vertices[v_sou].firstarc; p=p->nextarc; Dear_len[v_sou].flag_S=TRUE; Dear_cost[v_sou].flag_S=TRUE; while(p) { Dear_len[p->adjvex].value_D=p->length; Dear_cost[p->adjvex].value_D=p->cost; Path_len[p->adjvex].father=v_sou; Path_cost[p->adjvex].father=v_sou; p=p->nextarc; } for(i=1;i { min_len=INFINITY; min_cost=INFINITY; for(j=0;j { if(Dear_len[j].value_D { min_len=Dear_len[j].value_D; no_path=j; } if(Dear_cost[j].value_D { min_cost=Dear_cost[j].value_D; no_cost=j; } } Dear_len[no_path].flag_S=TRUE; Dear_cost[no_cost].flag_S=TRUE; p1=G.vertices[no_path].firstarc; for(p1=p1->nextarc;p1! =NULL;p1=p1->nextarc)//更新 { if(Dear_len[p1->adjvex].value_D>(min_len+p1->length) &&Dear_len[p1->adjvex].flag_S==FALSE) { Dear_len[p1->adjvex].value_D=min_len+p1->length; Path_len[p1->adjvex].father=no_path; } } p2=G.vertices[no_cost].firstarc; for(p2=p2->nextarc;p2! =NULL;p2=p2->nextarc) { if(Dear_cost[p2->adjvex].value_D>(min_cost+p2->cost) &&Dear_cost[p2->adjvex].flag_S==FALSE) { Dear_cost[p2->adjvex].value_D=min_cost+p2->cost; Path_cost[p2->adjvex].father=no_cost; } } } } voidInfoCustomer(ALGraphG,str2p[],str1d[],intv_sou,intv_des,intmethod)//通知用户所按要求所寻得的最优路径 { inti,len=1; intcity; charcities[20][15]; city=p[v_des].father; strcpy(cities[0],G.vertices[v_des].city); while(city! =v_sou) { strcpy(cities[len++],G.vertices[city].city); city=p[city].father; } strcpy(cities[len],G.vertices[v_sou].city); len++; for(i=len-1;i>=0;i--) { printf("%s",cities[i]); if(i! =0)printf("-->"); } printf("\n"); if(method==1) { if(d[v_des].value_D==INFINITY)printf("length=%d\n",0); elseprintf("length=%d\n",d[v_des]); } if(method==2) { if(d[v_des].value_D==INFINITY)printf("cost=%d\n",0); elseprintf("cost=%d\n",d[v_des]); } } 四使用说明、测试分析及结果 根据提示输入任意两个地点的编号,选择一种权重求最短路径 结果如下图所示:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 求图中 任意 两点 路径