標(biāo)題: 有關(guān)數(shù)據(jù)結(jié)構(gòu)的C++程序-城市交通最短路徑問(wèn)題 [打印本頁(yè)]
作者: kid4869    時(shí)間: 2019-5-21 18:31
標(biāo)題: 有關(guān)數(shù)據(jù)結(jié)構(gòu)的C++程序-城市交通最短路徑問(wèn)題
設(shè)計(jì)一個(gè)交通查詢(xún)系統(tǒng)，能讓游客查詢(xún)從任一城市頂點(diǎn)到另一城市頂點(diǎn)之間的最短路徑或最低花費(fèi)或最少時(shí)間等問(wèn)題。對(duì)于不同查詢(xún)要求，可輸入城市間的路程或所需時(shí)間或所需費(fèi)用。
本程序共分三個(gè)部分：
（1）建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)；
（2）單源最短路徑；
（3）實(shí)現(xiàn)兩個(gè)城市頂點(diǎn)之間的最短路徑。


單片機(jī)源程序如下:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MVNum  100
  4. #define Maxint 32767
  5. enum  boolean{FALSE,TRUE};
  6. typedef char VertexType;
  7. typedef int  Adjmatrix;
  8. typedef struct {
  9. VertexType vexs[MVNum];
  10. Adjmatrix arcs[MVNum][MVNum];
  11. }MGraph;
  12. int D1[MVNum],P1[MVNum];
  13. int D[MVNum][MVNum],P[MVNum][MVNum];
  14. //文件名CreateMGraph.c
  15. void CreateMGraph(MGraph *G,int n,int e)
  16. {//采用鄰接矩陣表示法構(gòu)造有向圖G，n，e表示圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)
  17. int i,j,k,w;
  18. for(i=1;i<=n;i++)
  19. G->vexs[i]=(char)i;
  20. for(i=1;i<=n;i++)
  21.         for(j=1;j<=n;j++)
  22.                 G->arcs[i][j]=Maxint;//初始化鄰接矩陣
  23. printf("輸入%d條邊的i、j及w:\n",e);
  24. for(k=1;k<=e;k++)
  25. {
  26. scanf("%d,%d,%d,",&i,&j,&w);
  27. G->arcs[i][j]=w;
  28. }
  29. printf("有向圖的存儲(chǔ)結(jié)構(gòu)建立完畢\n");
  30. }

  32. //文件dijkstra.c
  33. void Dijkstra(MGraph *G ,int v1,int n)
  34. {
  35. int D2[MVNum],P2[MVNum];
  36. int v,i,w,min;
  37. enum boolean S[MVNum];
  38. for(v=1;v<=n;v++)
  39. {
  40. S[v]=FALSE;
  41. D2[v]=G->arcs[v1][v];
  42. if(D2[v]<Maxint)
  43. P2[v]=v1;
  44. else
  45. P2[v]=0;
  46. }
  47. D2[v1]=0;
  48. S[v1]=TRUE;
  49. for(i=2;i<n;i++)
  50. {
  51. min=Maxint;
  52. for(w=1;w<=n;w++)
  53. if(!S[w]&& D2[w]<min)
  54. {
  55. v=w;
  56. min=D2[w];
  57. }
  58. S[v]=TRUE;
  59. for(w=1;w<=n;w++)
  60. if(!S[w] && (D2[v]+G->arcs[v][w]<D2[w]))
  61. {
  62. D2[w]=D2[v]+G->arcs[v][w];
  63. P2[w]=v;
  64. }
  65. }
  66. printf("路徑長(zhǎng)度路徑\n");
  67. for(i=1;i<=n;i++)
  68. {
  69. printf("%5d",D2[i]);
  70. printf("%5d",i);
  71. v=P2[i];
  72. while(v!=0)
  73. {
  74. printf("<-%d",v);
  75. v=P2[v];
  76. }
  77. printf("\n");
  78. }
  79. }

  81. //文件floyd.c
  82. void Floyd(MGraph *G,int n)
  83. {
  84. int i,j,k,w;
  85. for(i=1;i<=n;i++)
  86.    for(j=1;j<=n;j++)
  87.    {
  88. if(G->arcs[i][j]!=Maxint)
  89. P[i][j]=j;
  90. else
  91. P[i][j]=0;
  92. D[i][j]=G->arcs[i][j];
  93.     }
  94. for(k=1;k<=n;k++)
  95. {
  96. for(i=1;i<=n;i++)
  97. for(j=1;j<=n;j++)
  98. {
  99. if(D[i][k]+D[k][j]<D[i][j])
  100. {
  101.    D[i][j]=D[i][k]+D[k][j];
  102.    P[i][j]=P[i][k];
  103. }
  104. }
  105.   }
  106. }
  107. void main()
  108. {
  109. MGraph *G;
  110. int m,n,e,v,w,k;
  111. int xz=1;
  112. G=(MGraph *)malloc(sizeof(MGraph));
  113. printf("輸入圖中頂點(diǎn)個(gè)數(shù)和邊數(shù)n,e:");
  114. scanf("%d,%d",&n,&e);
  115. CreateMGraph(G,n,e);
  116. while(xz!=0)
  117. {
  118. printf("********求城市之間的最短路徑********\n");
  119. printf("====================================\n");
  120. printf("1.求一個(gè)城市到所有城市的最短路徑\n");
  121. printf("2.求任意的兩個(gè)城市之間的最短路徑\n");
  122. printf("====================================\n");
  123. printf("請(qǐng)選擇： 1、或 2、選擇 0、退出：");
  124. scanf("%d",&xz);
  125. if(xz==2)
  126. {
  127. Floyd(G,n);
  128. printf("輸入源點(diǎn)(或稱(chēng)起點(diǎn))和終點(diǎn):v,w:");
  129. scanf("%d,%d",&v,&w);
  130. k=P[v][w];
  131. if(k==0)
  132.    printf("頂點(diǎn)%d到%d無(wú)路徑!\n",v,w);
  133. else
  134.   {
  135.    printf("從頂點(diǎn)%d到%d的最短路徑是：%d!\n",v,w,v);
  136.    while(k!=w)
  137.    {
  138.    printf("->%d",k);
  139.    k=P[k][w];
  140.    }
  141.    printf("->%d",w);
  142.    printf("路徑長(zhǎng)度:%d\n",D[v][w]);
  143.    }
  144.   }
  145.   else
  146.      if(xz==1)
  147.      {
  148. printf("求單源路徑，輸入源點(diǎn)v:");
  149. ^^^^^限于篇幅余下內(nèi)容下載附件^^^^^^
復(fù)制代碼

全部資料51hei下載地址：
程序.rar (1.29 KB, 下載次數(shù): 11)





歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1