|
发表于 2018-1-14 18:35:24
|
显示全部楼层
本帖最后由 8306最硬 于 2018-1-14 18:48 编辑
- /******* main.c ********/
- #include "Graph.h"
- #include <stdio.h>
- #include <string.h>
- char *position[MAX_VEXTEX_NUM] = {
- "北门","饭堂","艺设学院","学生宿舍","英东楼","图书馆","教学楼","行政楼","南门"
- };
- void ShowShortPath(Map &G,int p1,int p2){
- int v,u,w,i;
- int D[G.vexnum][G.vexnum],p[G.vexnum][G.vexnum][G.vexnum];
- /* D为邻接矩阵副本,P为最优路径 */
- for(v=0;v<G.vexnum;v++){
- for(w=0;w<G.vexnum;w++){
- D[v][w]=G.adj[v][w].ArcVal;
- for(u=0;u<G.vexnum;u++)
- p[v][w][u]=0;
- if(D[v][w]<INFINITY){
- p[v][w][v]=1;p[v][w][w]=1;
- }//end if
- }// end for
- }// end for
-
- for(u=0;u<G.vexnum;u++)
- for(v=0;v<G.vexnum;v++)
- for(w=0;w<G.vexnum;w++)
- if(D[v][u]+D[u][w]<D[v][w]){
- D[v][w]=D[v][u]+D[u][w];
- for(i=0;i<G.vexnum;i++)
- p[v][w][i]=p[v][u][i]||p[u][w][i];
- }//end if
-
- if (p1<p2){
- /**
- * 如果键入号码为顶点顺序则正常输出
- * 如果键入号码为顶点逆序则反向输出*/
- for (i=0; i<G.vexnum;i++)
- if (p[p1][p2][i]){
- printf("%s-->",G.vexs[i]);
- }//end if
- }
- else{
- for (i=G.vexnum; i>=0; i--)
- if (p[p1][p2][i]){
- printf("%s-->",G.vexs[i]);
- }//end if
- }//end else
- /* for (int i=0;i<strlen(G.adj[p1][p2].info);i++)
- printf("\b");*/
- printf("\b\b\b 路径长度:%dm\n\n",D[p1][p2]);
- }
- int main(){
- Map MySchool;
- int position_1,position_2;
- CreateMap(MySchool);
- for (int i = 0; i < MAX_VEXTEX_NUM; i++)
- /* 初始化顶点 */
- AddVertex(MySchool, position[i]);
-
- AddArc(MySchool, "学生宿舍", "饭堂", 134);
- AddArc(MySchool, "北门", "艺设学院", 132);
- AddArc(MySchool, "饭堂", "艺设学院", 64);
- AddArc(MySchool, "艺设学院", "英东楼", 220);
- AddArc(MySchool, "艺设学院", "学生宿舍", 79);
- AddArc(MySchool, "艺设学院", "图书馆", 300);
- AddArc(MySchool, "英东楼", "图书馆", 93);
- AddArc(MySchool, "英东楼", "教学楼", 84);
- AddArc(MySchool, "图书馆", "教学楼", 61);
- AddArc(MySchool, "行政楼", "南门", 113);
- AddArc(MySchool, "教学楼", "行政楼", 63);
- AddArc(MySchool, "图书馆", "行政楼", 108);
- AddArc(MySchool, "英东楼", "行政楼", 147);
- /* 初始化边 */
- for (int i=0; i < MySchool.vexnum; i++)
- /* 打印各地点 */
- printf("/* %d:%s \n",i,position[i]);
-
- while(1){
- printf("输入当前地址号码:");
- scanf("%d",&position_1);
- printf("输入目的地址号码:");
- scanf("%d",&position_2);
- /* 等待键入地点编码 */
-
- if ( position_1 >= 0 &&
- position_2 >= 0 &&
- position_1 <= MySchool.vexnum &&
- position_2 <= MySchool.vexnum &&
- position_1 != position_2 )
- /* 判断键入范围 */
-
- ShowShortPath(MySchool,position_1,position_2);
- /* 输出最优路径和距离 */
-
- else printf("\n别乱来\n");
- }// end while
-
- return 0;
- }
复制代码
两个函数
一个是计算最短距离ShowShortPath
一个是main函数,用于输入顶点和边,计算距离,输出结果
程序到这大致就写好了(我的程序),你的就多了输入文件和输出文件两步咯
但要详细解释还真不好说啊..不管怎样,兄弟加油吧.. |
|