最短路径---Dijkstra迪杰特斯拉算法---《数据结构》严蔚敏

前端之家收集整理的这篇文章主要介绍了最短路径---Dijkstra迪杰特斯拉算法---《数据结构》严蔚敏前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
  1. // exam1.cpp : 定义控制台应用程序的入口点。
  2. //
  3.  
  4. #include "stdafx.h"
  5. #include <iostream>
  6. #include <stack>
  7. using namespace std;
  8.  
  9. #define MAXVEX 20
  10. #define INT_MAX 10000
  11.  
  12. typedef struct ArcNode
  13. {
  14. int adj;
  15. void* info;
  16. }ArcNode;
  17.  
  18. typedef ArcNode AdjMat[MAXVEX][MAXVEX];
  19.  
  20. typedef struct
  21. {
  22. int vexnum;
  23. int arcnum;
  24. AdjMat am;
  25. }Graph;
  26.  
  27. void InitGraph(Graph& G)
  28. {
  29. cout<<"Please enter the number of vertex:"<<endl;
  30. cin>>G.vexnum;
  31. cout<<"Please enter the Arc of the graph:"<<endl;
  32. cout<<"head tail weight"<<endl;
  33.  
  34. for(int i=0;i<G.vexnum;i++)
  35. {
  36. for(int j=0;j<G.vexnum;j++)
  37. {
  38. if(i==j)
  39. {
  40. G.am[i][j].adj=0;
  41. }
  42. else
  43. {
  44. G.am[i][j].adj=INT_MAX;
  45. }
  46. }
  47. }
  48.  
  49. int vex1,vex2,w;
  50. while(cin>>vex1>>vex2>>w)
  51. {
  52. G.am[vex1][vex2].adj=w;
  53. }
  54. }
  55.  
  56. void ShortestPath_DIJ(Graph G,bool** path)
  57. {
  58. int *D;
  59. D=(int*)malloc(G.vexnum*sizeof(int));
  60. bool *final;
  61. final=(bool*)malloc(G.vexnum*sizeof(bool));
  62. memset(final,G.vexnum*sizeof(bool));
  63.  
  64. for(int i=0;i<G.vexnum;i++)
  65. {
  66. D[i]=INT_MAX;
  67. if(G.am[0][i].adj<INT_MAX)
  68. {
  69. D[i]=G.am[0][i].adj;
  70. }
  71. path[i][i]=true; //terminal point
  72. path[i][0]=true; //starting point
  73. }
  74. final[0]=true;
  75.  
  76. for(int i=1;i<G.vexnum;i++)
  77. {
  78. int min=INT_MAX;
  79. int min_indx=-1;
  80. for(int j=0;j<G.vexnum;j++)
  81. {
  82. if(final[j]==false)
  83. {
  84. if(D[j]<min)
  85. {
  86. min=D[j];
  87. min_indx=j;
  88. }
  89. }
  90. }
  91. final[min_indx]=true;
  92. if(min_indx!=-1)
  93. {
  94. for(int j=1;j<G.vexnum;j++)
  95. {
  96. if(final[j]==false)
  97. {
  98. if(D[j]>D[min_indx]+G.am[min_indx][j].adj)
  99. {
  100. D[j]=D[min_indx]+G.am[min_indx][j].adj;
  101.  
  102. for(int k=0;k<G.vexnum;k++)
  103. {
  104. path[j][k]=path[min_indx][k];
  105. }
  106. path[j][j]=true;
  107. }
  108. }
  109. }
  110. }
  111. }
  112.  
  113. cout<<"The shortest path from v0 to "<<endl;
  114. for(int j=0;j<G.vexnum;j++)
  115. {
  116. cout<<"v"<<j<<":"<<D[j]<<endl;
  117. for(int i=0;i<G.vexnum;i++)
  118. {
  119. cout<<path[j][i]<<" ";
  120. }
  121. cout<<endl;
  122. }
  123. }
  124.  
  125. int main(void)
  126. {
  127. Graph G;
  128. InitGraph(G);
  129. bool **path;
  130. path=(bool**)malloc(G.vexnum*sizeof(bool*));
  131. for(int i=0;i<G.vexnum;i++)
  132. {
  133. path[i]=(bool*)malloc(G.vexnum*sizeof(bool));
  134. memset(path[i],false,G.vexnum*sizeof(bool));
  135. }
  136.  
  137. ShortestPath_DIJ(G,path);
  138.  
  139. system("pause");
  140. return 0;
  141. }

猜你在找的数据结构相关文章