《算法与数据结构设计题与源代码》由会员分享，可在线阅读，更多相关《算法与数据结构设计题与源代码（8页珍藏版）》请在金锄头文库上搜索。
1、算法与数据结构设计题与源代码关于最短路径的问题该最短路径算法主要以南京市的道路交通为模板（具体见附录图），简单实现任 意两个地点之间最短路径查询（例如三牌楼新街口），该最短路径剔除了那些 由于某些原因堵塞不通的路径。具体要求:1、编程实现，数据结构选用邻接矩阵或邻接表来实现2、输出最短路径的完整信息（起点、终点、中间遍历点、路径总长度）3、有较好的出错处理机制，算法高效4、有较好的图形界面便于人机交互，路径长度和道路编号明晰【可选】附录如下一一三牌嗖山西ISwn中夬门长赫姑解仙林箕金山Rae月牙UWD总辯赫公井夫子庙雨花台tr宁长江大桥三戕013、27XX3XX00XXX00XXXX山西路10
2、2XXXX0000XX007XX00XXX332()XXrz0003X4XXX00XXXX草场仃500X000XXX00XX00XXX00XXXoc中央门200XX0XXX00XX00XXX00XXXX南京西姑7XXXX05X00XX00XXX00XX4X000XX05074XX00XXX00XXXoc辭血林g00XXcoz707ocX00ocXcc00ocXXoc紫金山300XX00X4706X00XXX00XXXX00003XooXXoo60300XXX00XXXoc月牙朝0000XXXXXX003000XXX00XXXX00004XXXXX00XX0XX300XXX3真粉M007XXzX
3、XX00XX000zX00XXXXAWffX00XXXrT000XX00X0200XXX2&公井0000XXz00XX00XX3X2034XXX夫子庖0000XXX00XX00XX00XX30XXXX甫花台000XX0XXX00XX00XX40005Xoc0：宁000XX0zXX00XX00XXX0050Xoc长江大桥0000XX004X0000XX00XXX00XX(1X003XXXXX0000XX3X2X00XXXII表1道路交通矩阵说明：戈标识没有直接路径到达或者堵塞isn中央门mi賞金山JtiTR月牙MOn夫子蔺購花台江宁騷大林RW三MS4#5#3#2#1#7#6#tliBtt4#18
4、#16#17#ft#5#18#19#20#3#中知2#8#ma1#10#9#7#10#11#12#11#13#養金山6#12#13#14#19#14#15#28#月牙湖15#加口20#28#24#22#16#23#21#馳井24#23#25#26#夫子庙25#26#27#江宁27#长江大桥8#9#17#22#21#表2道路交通路编號阵说明：空格表械有直接通路# include#include # iiiclude# iiicludeusing namespace std;const iiit in=65535;const mt MAXVEX=20; 地点的个数stack a; 声明1个存储in
5、t型元素的栈，栈名是astmct node/创建节点类，保存地点编号和地点名称mt size;地点编号strmg name; 地点名称locat20;void Floyd(int costMAXXTX jnt njnt mjnt x) /刃：洛伊德算法，求最短路线和最短路线长度mt ANIAXVEXMAXVEX,pathMAXEXMAXVEX; 数组 A 保存最短路线的长度, 数组path保存最短路线mt ijkpre;fbi(i=O;in;i-H-)for(j=0jnj+)Ai|j=costij; 初始化数组 A 和数组 pathpatliij=i;for (i=0;in;i+)求最短路径和
6、最短路径长度for(j=Ojnj+)for(k=O;kAik+Akj)Aij=Aik+Ak|j;/最短路径长度patlii|j=pathkj; 最短路径if(m!=x) /起始地点与终止地点不同时，用栈存储最短路径，进行以卞操作cout ”您所查询的最短路径长度是:Amx 咪5”；cout 具体路径为: locatm.name;a.push(x);终点的编号入栈pie=pathmx;wlule(l)最短路径的地点入栈，一直到pre为起始地点的编号，才结束a.push(pre);pre=pathmpre;if (pie=m) break;i=l；while (!a.emptyQ) 栈为非空时，数
7、据出栈cout H ” locata.topQ.name;a.pop();讦+；唤=5)coutendl:cout endl;else coutn您还是在原点！ ”endl; /起始地点与终止地点相同void Place()/地址函数, locat0.size=0; locatl.size=l; locat2.size=2; locat3.size=3; locat4.size=4; locat5.size=5; locat6.size=6; locat7.size=7;locat8.size=8; locat9.size=9; locat10.size=10; locatll.size=ll
8、; locat12.size=12; locat13.size=13; locat14.size=14; locatfl 5.size=15; locat16.size=16; locat17.size=17; locat18.size=18; locat19.size=19;初始化地点编号、地点名称locat0 name=n 三牌楼”； locatl.name=n 山西 路”； locat2.name=n 鼓楼； locat3.name=n 草场门”； locat4.name=n 中央门； locat5.name=n 南京西站”; locat6 name=” 长途东站 locat7 .nam
9、e=n 南邮仙林”; locat8.name=n 紫金山； locat9 name=n 珠江路”； locat10.naine=H 月牙湖: locatll.name=,r新街I I”； locat 12.iiaine=H 莫愁湖; locat13.naine=H 总统府； locat 14 .naine=H 杨公井； locat15.naine=H 夫子庙； locat16.naine=H 雨花台”； locatfl 7 .naine=H 江宁”； locat18 .naine=H 长江人桥”; locat19.naine=H 四牌楼:mt Value(int p.mt q) 数值函数，初始化权值，并输出从p点到达q点的路径长度 mt wNIAXVEX MAXVEX;mtij;foi(i=O;iNIAXVEX;i+)foi(j=
