求最短路径(迪杰斯特拉算法)

1. #include<iostream.h>

2. #include<string.h>

3. /*邻接矩阵的类型定义*/

4. #define MAX 10000000

5. #define MAX_VERTEX_NUM 20

6. typedef struct

7. {

8. string vexs[MAX_VERTEX_NUM];//用一维数组存储顶点信息

9. int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//用二维数组充当

矩阵，来存储顶点边的信息

10. int vexnum,edgenum;//顶点树和边数

11. }MGraph;

12. /*构造有向网的邻接矩阵*/

13. void CreateDN_AM(MGraph &G,int n,int e)

14. {

15. G.vexnum=n;

16. G.edgenum=e;

17.

18. int i,j,k;

19. int weight;

20. for(i=0;i<n;i++)

21. cin>>G.vexs[i];//输入顶点信息

22. for(i=0;i<n;i++)

23. for(j=0;j<n;j++)

24. G.edges[i][j]=MAX;//将矩阵初始化为MAX

25. for(k=0;k<e;k++)

26. {

27. cin>>i>>j>>weight;

28. G.edges[i][j]=weight;

29. }

30. }

31. /*迪杰斯特拉算法求某个顶点到其余顶点的最短路径*/

32. void ShortestPath_DJ(MGraph &G,int v)

33. {

34. int i,j,k,min;

35. int final[MAX_VERTEX_NUM];//该数组用来标识顶点是否已确定了最短路

径

36. int dist[MAX_VERTEX_NUM];

37. string path[2*MAX_VERTEX_NUM];

38. for(i=0;i<G.vexnum;i++)

39. {//初始化工作

40. dist[i]=G.edges[v][i];//dist数组用来存储当前找到的v到其他各顶点的最

短路径

41. if(dist[i]<MAX)

42. path[i]=G.vexs[v]+G.vexs[i];//如果v到i有边的话，把顶点字符存到

path字符数组中，表示路径

43. else

44. path[i]="";

45. final[i]=0;//初始化标识数组为0

46. }

47. dist[v]=0;

48. final[v]=1;

49. for(j=1;j<G.vexnum;j++)

50. {

51. min=MAX;

52. for(i=0;i<G.vexnum;i++)

53. if(dist[i]<min && final[i]==0)

54. {

55. min=dist[i];

56. k=i;

57. }//找到dist数组中最小值的位置k

58. cout<<path[k]<<" "<<dist[k]<<endl;//输出最短路径

59. final[k]=1;//设置标志位

60. for(i=0;i<G.vexnum;i++)

61. {//遍历每个顶点i和当前的已求出的最短路径的顶点k作比较，若从源点

经过顶点k到顶点i的路径，比dist[i]小，

62. //则更新顶点dist[i]

63. if(dist[i]>dist[k]+G.edges[k][i] && final[i]==0)

64. {

65. dist[i]=dist[k]+G.edges[k][i];

66. path[i]=path[k]+G.vexs[i];

67. }

68. }//从整体上来看就是算出k的邻接点的当前最短路径

69. }

70. }

71. void main()

72. {

73. freopen("in.txt","r",stdin);

74. MGraph G;

75. CreateDN_AM(G,7,11);

76. ShortestPath_DJ(G,0);

77. }

迪杰斯特拉算法主要是采用了一个dist一维数组，来存储源点到其它顶点的最短路径，然后不断更新。

迪杰斯特拉算法求最短路径 C++代码实现