00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00014
00015
00016
00017
00019
00020
00021 #ifndef SHORTEST_PATH_CALCULATOR_HH
00022 #define SHORTEST_PATH_CALCULATOR_HH
00023
00024
00025
00030 class ShortestPathCalculator {
00031
00032 public:
00033
00034
00035
00036
00037
00050 ShortestPathCalculator(int nNodes, int nEdges, int* adjPtr, int* adjList,
00051 double* edgeWeight, double bound, double tol);
00052
00056 ~ShortestPathCalculator();
00057
00067 double calculateShortestPath(int startNode, int endNode, int* predNode);
00068
00069
00070 private:
00071
00072
00073
00074
00075
00081 void buildHeap(int startNode);
00082
00088 int extractMin();
00089
00096 void changeKey(int node, double label);
00097
00098
00099
00100
00101
00102
00106 int m_nNodes;
00107
00111 int m_nEdges;
00112
00116 int* m_adjPtr;
00117
00121 int* m_adjList;
00122
00126 double* m_edgeWeight;
00127
00131 double m_bound;
00132
00136 double m_tol;
00137
00141 int m_heapSize;
00142
00146 int* m_heap;
00147
00151 int* m_invHeap;
00152
00156 double* m_nodeLabel;
00157
00158 };
00159
00160 #endif
00161
00162