数据结构求图中任意两点短路径Word文档格式.docx
- 文档编号:7082511
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:12
- 大小:36.92KB
数据结构求图中任意两点短路径Word文档格式.docx
《数据结构求图中任意两点短路径Word文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构求图中任意两点短路径Word文档格式.docx(12页珍藏版)》请在冰点文库上搜索。
}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;
typedefstructALGraph
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]);
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++)
G.vertices[i].firstarc=(ArcNode*)malloc(sizeof(ArcNode));
G.vertices[i].firstarc->
nextarc=NULL;
printf("
******序号————城市名********\n"
G.vexnum;
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(j=0;
j++)
if(strcmp(city[j],city_1[i])==0)
{
for(k=0;
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];
length=path[i];
q->
nextarc=e;
}
}
returnG;
voidShortPath_DIJ(ALGraphG,intv_sou)//用Dijkstra算法求最短路径
{
inti,j,no_cost,no_path;
intmin_cost,min_len;
ArcNode*p,*p1,*p2;
i++)//初始化辅助向量
Path_cost[i].father=i;
Path_len[i].father=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->
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->
cost;
Path_len[p->
adjvex].father=v_sou;
Path_cost[p->
p=p->
}
for(i=1;
i++)//开始主循环,每次求得v0到某个顶点的最短路径
min_len=INFINITY;
min_cost=INFINITY;
for(j=0;
j++)//找最小的D[j]=min{D[i]}
if(Dear_len[j].value_D<
min_len&
&
Dear_len[j].flag_S==FALSE)
min_len=Dear_len[j].value_D;
no_path=j;
if(Dear_cost[j].value_D<
min_cost&
Dear_cost[j].flag_S==FALSE)
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->
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->
Path_len[p1->
adjvex].father=no_path;
p2=G.vertices[no_cost].firstarc;
for(p2=p2->
p2!
p2=p2->
nextarc)
if(Dear_cost[p2->
(min_cost+p2->
cost)
Dear_cost[p2->
Dear_cost[p2->
adjvex].value_D=min_cost+p2->
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--)
%s"
cities[i]);
if(i!
=0)printf("
-->
"
\n"
if(method==1)
if(d[v_des].value_D==INFINITY)printf("
length=%d\n"
0);
elseprintf("
d[v_des]);
if(method==2)
cost=%d\n"
四使用说明、测试分析及结果
根据提示输入任意两个地点的编号,选择一种权重求最短路径
结果如下图所示:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 求图中 任意 两点 路径