0033算法笔记 - 分支限界法分支限界法与单源最短路径问题(2)

[cpp] view plain copy

1. #include 2.

3. template 4. class Graph; 5.

6. template 7. class MinHeap 8. {

9. template 10. friend class Graph; 11. public:

12. MinHeap(int maxheapsize = 10); 13. ~MinHeap(){delete []heap;} 14.

15. int Size() const{return currentsize;} 16. T Max(){if(currentsize) return heap[1];} 17.

18. MinHeap& Insert(const T& x); 19. MinHeap& DeleteMin(T &x); 20.

21. void Initialize(T x[], int size, int ArraySize); 22. void Deactivate(); 23. void output(T a[],int n); 24. private:

25. int currentsize, maxsize; 26. T *heap; 27. }; 28.

29. template

30. void MinHeap::output(T a[],int n) 31. {

32. for(int i = 1; i <= n; i++) 33. cout << a[i] << \; 34. cout << endl; 35. } 36.

37. template

38. MinHeap::MinHeap(int maxheapsize) 39. {

40. maxsize = maxheapsize; 41. heap = new T[maxsize + 1]; 42. currentsize = 0; 43. }

44.

45. template

46. MinHeap& MinHeap::Insert(const T& x) 47. {

48. if(currentsize == maxsize) 49. {

50. return *this; 51. }

52. int i = ++currentsize;

53. while(i != 1 && x < heap[i/2]) 54. {

55. heap[i] = heap[i/2]; 56. i /= 2; 57. } 58.

59. heap[i] = x; 60. return *this; 61. } 62.

63. template

64. MinHeap& MinHeap::DeleteMin(T& x) 65. {

66. if(currentsize == 0) 67. {

68. cout<<\<

72. x = heap[1]; 73.

74. T y = heap[currentsize--]; 75. int i = 1, ci = 2; 76. while(ci <= currentsize) 77. {

78. if(ci < currentsize && heap[ci] > heap[ci + 1]) 79. {

80. ci++; 81. } 82.

83. if(y <= heap[ci]) 84. {

85. break; 86. }

87. heap[i] = heap[ci];

88. i = ci; 89. ci *= 2; 90. } 91.

92. heap[i] = y; 93. return *this; 94. } 95.

96. template

97. void MinHeap::Initialize(T x[], int size, int ArraySize) 98. {

99. delete []heap; 100. heap = x;

101. currentsize = size; 102. maxsize = ArraySize; 103.

104. for(int i = currentsize / 2; i >= 1; i--) 105. {

106. T y = heap[i]; 107. int c = 2 * i;

108. while(c <= currentsize) 109. {

110. if(c < currentsize && heap[c] > heap[c + 1]) 111. c++;

112. if(y <= heap[c]) 113. break;

114. heap[c / 2] = heap[c]; 115. c *= 2; 116. }

117. heap[c / 2] = y; 118. } 119. } 120.

121. template

122. void MinHeap::Deactivate() 123. {

124. heap = 0; 125. }

2、6d2.cpp

[cpp] view plain copy

1. //单源最短路径问题 分支 限界法求解 2. #include \ 3. #include \

4. #include 5. #include 6. using namespace std; 7.

8. ifstream fin(\); 9.

10. template 11. class Graph 12. {

13. friend int main(); 14. public:

15. void ShortesPaths(int); 16. private:

17. int n, //图G的顶点数 18. *prev; //前驱顶点数组 19. Type **c, //图G的领接矩阵 20. *dist; //最短距离数组 21. }; 22.

23. template 24. class MinHeapNode 25. {

26. friend Graph; 27. public:

28. operator int ()const{return length;} 29. private:

30. int i; //顶点编号 31. Type length; //当前路长 32. }; 33.

34. template

35. void Graph::ShortesPaths(int v)//单源最短路径问题的优先队列式分支限界法 36. {

37. MinHeap> H(1000); 38. MinHeapNode E; 39.

40. //定义源为初始扩展节点 41. E.i=v; 42. E.length=0; 43. dist[v]=0; 44.

45. while (true)//搜索问题的解空间 46. {

47. for (int j = 1; j <= n; j++)

48. if ((c[E.i][j]!=0)&&(E.length+c[E.i][j]

50. // 顶点i到顶点j可达，且满足控制约束 51. dist[j]=E.length+c[E.i][j]; 52. prev[j]=E.i; 53.

54. // 加入活结点优先队列 55. MinHeapNode N; 56. N.i=j;

57. N.length=dist[j]; 58. H.Insert(N); 59. }` 60. try 61. {

62. H.DeleteMin(E); // 取下一扩展结点 63. } 64. catch (int) 65. {

66. break; 67. }

68. if (H.currentsize==0)// 优先队列空 69. {

70. break; 71. } 72. } 73. } 74.

75. int main() 76. {

77. int n=11;

78. int prev[12] = {0,0,0,0,0,0,0,0,0,0,0,0}; 79.

80. int dist[12]={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,100

0}; 81.

82. cout<<\单源图的邻接矩阵如下：\<

85. for(int i=1;i<=n;i++) 86. {

87. c[i]=new int[n+1]; 88. for(int j=1; j<=n; j++) 89. {

90. fin>>c[i][j];