当前位置：首页 > news >正文

医院网站建设报价太原seo推广外包

news 2025/11/9 19:22:01

医院网站建设报价,太原seo推广外包,asp网站知道用户名是admin,网站建设互联一、最短路径应用案例例如从北京到上海旅游#xff0c;有多条路可以到目的地#xff0c;哪条路线最短#xff0c;哪条路线最省钱#xff0c;就是典型的最短路径问题。二、最短路径问题分类最短路径问题可以分为两类#xff0c;第一类为#xff1a;两点间最短路径。第…一、最短路径应用案例例如从北京到上海旅游有多条路可以到目的地哪条路线最短哪条路线最省钱就是典型的最短路径问题。二、最短路径问题分类最短路径问题可以分为两类第一类为两点间最短路径。第二类为某源点到其他各点最短路径。不同的问题类型可以用不同的算法实现本文介绍第一类问题的Dijkstra算法实现。三、Dijkstra算法思路这次新画了一个图是时候体现一下画图技巧啦言归正传我们需要用有向图加邻接矩阵实现邻接矩阵结果如下 [2023-7]--[ Debug ]--Printf AMGraph : VertexArray : [0 ,1 ,2 ,3 ,4 ,5 ,6 ] ArcArray : [32767 ,13 ,8 ,32767 ,30 ,32767 ,32 ] [32767 ,32767 ,32767 ,32767 ,32767 ,9 ,7 ] [32767 ,32767 ,32767 ,5 ,32767 ,32767 ,32767 ] [32767 ,32767 ,32767 ,32767 ,6 ,32767 ,32767 ] [32767 ,32767 ,32767 ,32767 ,32767 ,2 ,32767 ] [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,17 ] [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,32767 ] CurVertexNum : 7 CurArcNum : 10 除此之外我们还需要维护一个最短边数组LowestEdgeArray和点到点路径长度数组PathLenArray如下 [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 32767), [ ]3 : (EndVertextIndex : 4, WeightVal : 30), [ (0,4,30) ]4 : (EndVertextIndex : 5, WeightVal : 32767), [ ]5 : (EndVertextIndex : 6, WeightVal : 32), [ (0,6,32) ] PathLenArray : [ (0,2,8) ] PathLenArrayLen : 1 PathLenArrayMaxLen : 6 我们从0点出发先解释一下上图如何理解第一行表示最短边数组LowestEdgeArray索引号0存储着顶点索引0到结束点EndVertextIndex1权值为13后面的[ (0,1,13) ]可以不关注主要是为了实现例如0-4经过了哪些点方便计算用的。第二行表示最短边数组LowestEdgeArray索引号1存储着顶点索引0到结束点EndVertextIndex2权值为8。后面几行也以此类推就是在邻接矩阵图上遍历。填写好0到5行最短边数组LowestEdgeArray数据后计算其中最小的权值8对应EndVertextIndex2并记录点到点路径长度数组PathLenArray中。2号节点被我们找到了后面遍历1-6号节点时不需要扫描2号点了。我们取到的是(0,2,8)现在我们将邻接矩阵中2号点的计算并更新到最短边数组LowestEdgeArray。 [32767 ,32767 ,32767 ,5 ,32767 ,32767 ,32767 ] 我们只需要看2-3的权值558之前取到的最小权值32767因为其他点都是无穷大但实际计算是需要挨个比较的。 2 : (EndVertextIndex : 3, WeightVal : 32767), [ ] 更新为13在开始找最小权值从13456中扫描。 2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ] 更新最短边数组LowestEdgeArray和点到点路径长度数组PathLenArray如下 [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ]3 : (EndVertextIndex : 4, WeightVal : 30), [ (0,4,30) ]4 : (EndVertextIndex : 5, WeightVal : 32767), [ ]5 : (EndVertextIndex : 6, WeightVal : 32), [ (0,6,32) ] PathLenArray : [ (0,2,8),(0,1,13) ] PathLenArrayLen : 2 PathLenArrayMaxLen : 6 PathLenArray : [ (0,2,8),(0,1,13) ] 现在只需要扫描3456节点信息上一个最小权值是在1号节点把邻接矩阵中1号点的信息写入并计算。 [32767 ,32767 ,32767 ,32767 ,32767 ,9 ,7 ] 13 13 32767LowestEdgeArray中EndVertextIndex3的权值13小于上一个最小值(0,1,13)的13加上邻接矩阵3号位权值32767不更新LowestEdgeArray。 30 13 32767LowestEdgeArray中EndVertextIndex4的权值30小于上一个最小值(0,1,13)的13加上邻接矩阵4号位权值32767不更新LowestEdgeArray。 32767 13 9LowestEdgeArray中EndVertextIndex5的权值32767 大于上一个最小值(0,1,13)的13加上邻接矩阵5号位权值9更新LowestEdgeArray的EndVertextIndex : 5的权值位22。 32 13 7LowestEdgeArray中EndVertextIndex6的权值32 大于上一个最小值(0,1,13)的13加上邻接矩阵6号位权值7更新LowestEdgeArray的EndVertextIndex : 6的权值位20。上面4个点中找出最小权值13(0,3,13)写入到PathLenArray中具体变化如下 [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ]3 : (EndVertextIndex : 4, WeightVal : 30), [ (0,4,30) ]4 : (EndVertextIndex : 5, WeightVal : 22), [ (1,5,9) ]5 : (EndVertextIndex : 6, WeightVal : 20), [ (1,6,7) ] PathLenArray : [ (0,2,8),(0,1,13),(0,3,13) ] PathLenArrayLen : 3 PathLenArrayMaxLen : 6 现在只需要扫描456节点信息上一个最小权值是在3号节点把邻接矩阵中3号点的信息写入并计算。 [32767 ,32767 ,32767 ,32767 ,6 ,32767 ,32767 ] 30 13 6LowestEdgeArray中EndVertextIndex4的权值30大于上一个最小值(0,3,13)的13加上邻接矩阵4号位权值6更新LowestEdgeArray的EndVertextIndex : 4的权值位19。 22 13 32767LowestEdgeArray中EndVertextIndex5的权值22 小于上一个最小值(0,3,13)的13加上邻接矩阵5号位权值32767不更新LowestEdgeArray。 20 13 32767LowestEdgeArray中EndVertextIndex6的权值20 小于上一个最小值(0,3,13)的13加上邻接矩阵6号位权值32767不更新LowestEdgeArray。上面3个点中找出最小权值19(0,4,19)写入到PathLenArray中具体变化如下 [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ]3 : (EndVertextIndex : 4, WeightVal : 19), [ (3,4,6) ]4 : (EndVertextIndex : 5, WeightVal : 22), [ (1,5,9) ]5 : (EndVertextIndex : 6, WeightVal : 20), [ (1,6,7) ] PathLenArray : [ (0,2,8),(0,1,13),(0,3,13),(0,4,19) ] PathLenArrayLen : 4 PathLenArrayMaxLen : 6 现在只需要扫描56节点信息上一个最小权值是在4号节点把邻接矩阵中4号点的信息写入并计算。 [32767 ,32767 ,32767 ,32767 ,32767 ,2 ,32767 ] 22 19 2LowestEdgeArray中EndVertextIndex5的权值22 大于上一个最小值(0,4,19)的19加上邻接矩阵5号位权值2更新LowestEdgeArray的EndVertextIndex : 5的权值位21。 20 19 32767LowestEdgeArray中EndVertextIndex6的权值20 小于上一个最小值(0,4,19)的19加上邻接矩阵6号位权值32767不更新LowestEdgeArray。上面2个点中找出最小权值20(0,6,20)写入到PathLenArray中具体变化如下 [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ]3 : (EndVertextIndex : 4, WeightVal : 19), [ (3,4,6) ]4 : (EndVertextIndex : 5, WeightVal : 21), [ (4,5,2) ]5 : (EndVertextIndex : 6, WeightVal : 20), [ (1,6,7) ] PathLenArray : [ (0,2,8),(0,1,13),(0,3,13),(0,4,19),(0,6,20) ] PathLenArrayLen : 5 PathLenArrayMaxLen : 6 现在只需要扫描5节点信息上一个最小权值是在6号节点把邻接矩阵中6号点的信息写入并计算。 [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,32767 ]21 20 32767LowestEdgeArray中EndVertextIndex5的权值21 小于上一个最小值(0,6,20)的20加上邻接矩阵6号位权值32767不更新LowestEdgeArray。上面1个点中找出最小权值20(0,5,21)写入到PathLenArray中具体变化如下 [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ]3 : (EndVertextIndex : 4, WeightVal : 19), [ (3,4,6) ]4 : (EndVertextIndex : 5, WeightVal : 21), [ (4,5,2) ]5 : (EndVertextIndex : 6, WeightVal : 20), [ (1,6,7) ] PathLenArray : [ (0,2,8),(0,1,13),(0,3,13),(0,4,19),(0,6,20),(0,5,21) ] PathLenArrayLen : 6 PathLenArrayMaxLen : 6 这样我们就得到0到其他节点的权值啦有什么写的不妥的大家可以多提建议。 Dijkstra的时间算法复杂度为O(n^2)。四、宏定义宏定义和部分定义结构体用的是之前的图的可以参考之前的博客《数据结构与算法基础-学习-23-图之邻接矩阵与邻接表》。五、自定义结构体 1、StAccessPath typedef struct StAccessPath {NetArcDataType* AccessArray; //存储从起始节点到目的节点的各个节点的信息。VertexIndexType AccessArrayLen; //AccessArray数组长度。VertexIndexType AccessArrayMaxLen; //AccessArray数组最大长度顶点数减一。 }StAccessPath; 2、StBaseDijkstra typedef struct StBaseDijkstra {WeightType WeightVal; //从起始节点到目的节点的权值。VertexIndexType EndVertextIndex; //结束顶点的索引号。StAccessPath* AccessPath; } StBaseDijkstra; 3、StDijkstra typedef struct StDijkstra {StBaseDijkstra* LowestEdgeArray; //用于存储最短边变化过程的数组。NetArcDataType* PathLenArray; //记录起始顶点到各个顶点的信息。 VertexIndexType PathLenArrayLen; //记录PathLenArray的使用长度。VertexIndexType PathLenArrayMaxLen; //记录PathLenArray的最大使用长度。 } StDijkstra; 4、StDijkstraAccees typedef struct StDijkstraAccees {StAccessPath** AccessPath;VertexIndexType AccessPathMaxLen; //AccessPath数组最大长度也可以说是最大行数顶点数减一。 }StDijkstraAccees; 六、函数定义 1、InitStAccessPath Status InitStAccessPath(StAccessPath** StAP, VertexIndexType ArrayLen) {JudgeAllNullPointer(StAP);*StAP (StAccessPath*)MyMalloc(sizeof(StAccessPath));(*StAP)-AccessArray (NetArcDataType*)MyMalloc(sizeof(NetArcDataType) * ArrayLen);(*StAP)-AccessArrayLen 0;(*StAP)-AccessArrayMaxLen ArrayLen;LogFormat(Debug, %s\n, Init StAccessPath OK.);return SuccessFlag; } 初始化访问路径结构体。 2、DestroyStAccessPath Status DestroyStAccessPath(StAccessPath** StAP) {JudgeAllNullPointer(StAP);free((*StAP)-AccessArray);(*StAP)-AccessArray NULL;(*StAP)-AccessArrayLen 0;(*StAP)-AccessArrayMaxLen 0;free(*StAP);*StAP NULL;LogFormat(Debug, %s\n, Destroy StAccessPath OK.);return SuccessFlag; } 销毁访问路径结构体。 3、InitStDijkstra Status InitStDijkstra(StDijkstra** StDks, VertexIndexType VertexNum, VertexIndexType StartVertexIndex) {JudgeAllNullPointer(StDks);VertexIndexType i 0;VertexIndexType j 0;*StDks (StDijkstra*)MyMalloc(sizeof(StDijkstra));(*StDks)-LowestEdgeArray (StBaseDijkstra*)MyMalloc(sizeof(StBaseDijkstra) * (VertexNum - 1));for(i 0,j 0; i VertexNum - 1; i,j){InitStAccessPath(((*StDks)-LowestEdgeArray[i].AccessPath), VertexNum - 1);if (j StartVertexIndex){j;}(*StDks)-LowestEdgeArray[i].EndVertextIndex j;(*StDks)-LowestEdgeArray[i].WeightVal 0;}(*StDks)-PathLenArray (NetArcDataType*)MyMalloc(sizeof(NetArcDataType) * (VertexNum - 1));(*StDks)-PathLenArrayLen 0;(*StDks)-PathLenArrayMaxLen VertexNum - 1;LogFormat(Debug, %s\n, Init StDijkstra OK.);return SuccessFlag; } 初始化结构体。 4、DestroyStDijkstra Status DestroyStDijkstra(StDijkstra** StDks) {JudgeAllNullPointer(StDks);VertexIndexType i 0;for(i 0; i (*StDks)-PathLenArrayMaxLen; i){DestroyStAccessPath(((*StDks)-LowestEdgeArray[i].AccessPath));(*StDks)-LowestEdgeArray[i].EndVertextIndex 0;(*StDks)-LowestEdgeArray[i].WeightVal 0;}free((*StDks)-PathLenArray);(*StDks)-PathLenArray NULL;(*StDks)-PathLenArrayLen 0;(*StDks)-PathLenArrayMaxLen 0;free(*StDks);*StDks NULL;LogFormat(Debug, %s\n, Destroy StDijkstra OK.);return SuccessFlag; } 销毁结构体。 5、InitStDijkstraAccees Status InitStDijkstraAccees(StDijkstraAccees** StDA, VertexIndexType VertexNum) {JudgeAllNullPointer(StDA);VertexIndexType i 0;*StDA (StDijkstraAccees*)MyMalloc(sizeof(StDijkstraAccees));(*StDA)-AccessPath (StAccessPath**)MyMalloc(sizeof(StAccessPath*) * (VertexNum - 1));for (i 0; i VertexNum - 1; i){InitStAccessPath(((*StDA)-AccessPath[i]), VertexNum - 1);}(*StDA)-AccessPathMaxLen VertexNum - 1;LogFormat(Debug, %s\n, Init StDijkstraAccees OK.);return SuccessFlag; } 6、DestroyStDijkstraAccees Status DestroyStDijkstraAccees(StDijkstraAccees** StDA) {JudgeAllNullPointer(StDA);VertexIndexType i 0;for (i 0; i (*StDA)-AccessPathMaxLen; i){DestroyStAccessPath(((*StDA)-AccessPath[i]));}free((*StDA)-AccessPath);(*StDA)-AccessPath NULL;(*StDA)-AccessPathMaxLen 0;free(*StDA);*StDA NULL;LogFormat(Debug, %s\n, Destroy StDijkstraAccees OK.);return SuccessFlag; } 7、JudgeVertexIsAccessed //判断这个点是否被访问过 //SuccessFlag 表示被访问。FailFlag 表示没有被访问。 Status JudgeVertexIsAccessed(StDijkstra* StDks, VertexIndexType VertexIndex) {JudgeAllNullPointer(StDks);VertexIndexType i 0;for (i 0; i StDks-PathLenArrayLen; i){if (VertexIndex StDks-PathLenArray[i].EndVertexIndex){LogFormat(Debug,Judge Vertex(%d) Is Accessed.\n,VertexIndex);return SuccessFlag;}}LogFormat(Debug,Judge Vertex(%d) Is Not Accessed.\n,VertexIndex);return FailFlag; } 8、PushData2StAccessPath //将访问路径压入到结构体StAccessPath中。 Status PushData2StAccessPath(StAccessPath* StAP, NetArcDataType Data) {JudgeAllNullPointer(StAP);LogFormat(Debug,(StartVertexIndex : %d, EndVertexIndex : %d, Weight : %d)\n,Data.StartVertexIndex,Data.EndVertexIndex,Data.Weight);if (StAP-AccessArrayLen StAP-AccessArrayMaxLen){LogFormat(Error, %s\n, StAccessPath Is Full, Exit.);exit(ExceptionExitFlag);}StAP-AccessArray[StAP-AccessArrayLen] Data;//结构体复制。(StAP-AccessArrayLen);LogFormat(Debug, %s\n, Push Data To StAccessPath OK.);return SuccessFlag; } 9、ClearData2StAccessPath //将结构体StAccessPath的数据清零。 //没有使用到此函数。 Status ClearData2StAccessPath(StAccessPath* StAP) {JudgeAllNullPointer(StAP);StAP-AccessArrayLen 0;LogFormat(Debug, %s\n, Clear Data To StAccessPath OK.);return SuccessFlag; } 10、PushData2PathLenArray //将起始节点到结束节点的权值和索引号压入到PathLenArray中。 Status PushData2PathLenArray(StDijkstra* StDks, NetArcDataType Data) {JudgeAllNullPointer(StDks);if (StDks-PathLenArrayLen StDks-PathLenArrayMaxLen){LogFormat(Error, %s\n, PathLenArray Is Full, Exit.);exit(ExceptionExitFlag);}StDks-PathLenArray[StDks-PathLenArrayLen] Data;//结构体复制。(StDks-PathLenArrayLen);PrintfStDijkstra(StDks, Debug);LogFormat(Debug, %s\n, Push Data To StAccessPath OK.);return SuccessFlag; } 11、PushData2LowestEdgeArray //将数据压入到LowestEdgeArray中选出最小的权值及其对应的索引号。 Status PushData2LowestEdgeArray(StDijkstra* StDks, AMGraph* AMG, VertexIndexType PushVertexIndex, VertexIndexType* ReturnVertexIndex, WeightType* ReturnWeightVal) {JudgeAllNullPointer(StDks);JudgeAllNullPointer(AMG);JudgeAllNullPointer(ReturnVertexIndex);JudgeAllNullPointer(ReturnWeightVal);VertexIndexType i 0;*ReturnWeightVal MAX_INT_TYPE_NUM;//返回找出的最小权值。//VertexIndexType ShortestWeightIndex 0; //最小权值在最短边数组中的索引号后续更新到访问路径StDijkstraAccees使用。NetArcDataType TmpData;if (StDks-PathLenArrayLen 0)//说明LowestEdgeArray数组中没有数据需要先加载一次数据后面才好进行数据对比。{for (i 0; i StDks-PathLenArrayMaxLen; i){ StDks-LowestEdgeArray[i].WeightVal AMG-ArcArray[PushVertexIndex][StDks-LowestEdgeArray[i].EndVertextIndex];//将访问路径信息写入到结构体StAccessPath中。if (StDks-LowestEdgeArray[i].WeightVal ! MAX_INT_TYPE_NUM){TmpData.StartVertexIndex PushVertexIndex;TmpData.EndVertexIndex StDks-LowestEdgeArray[i].EndVertextIndex;TmpData.Weight StDks-LowestEdgeArray[i].WeightVal;PushData2StAccessPath(StDks-LowestEdgeArray[i].AccessPath,TmpData);}if (*ReturnWeightVal StDks-LowestEdgeArray[i].WeightVal)//找权值最小的索引号。{*ReturnWeightVal StDks-LowestEdgeArray[i].WeightVal;*ReturnVertexIndex StDks-LowestEdgeArray[i].EndVertextIndex;//ShortestWeightIndex i;}}}else//说明LowestEdgeArray数组已经有了数据我们需要对比之前的数据比原值小的进行更新不然跳过。{for (i 0; i StDks-PathLenArrayMaxLen; i){if (JudgeVertexIsAccessed(StDks, StDks-LowestEdgeArray[i].EndVertextIndex) SuccessFlag)//访问过的点不需要更新权值{continue;}//如果邻接矩阵中的权值上一个最短边数组中的权值最短边数组中的权值进行数据更新。if (StDks-LowestEdgeArray[i].WeightVal AMG-ArcArray[PushVertexIndex][StDks-LowestEdgeArray[i].EndVertextIndex] StDks-PathLenArray[StDks-PathLenArrayLen - 1].Weight){StDks-LowestEdgeArray[i].WeightVal AMG-ArcArray[PushVertexIndex][StDks-LowestEdgeArray[i].EndVertextIndex] StDks-PathLenArray[StDks-PathLenArrayLen - 1].Weight;//将访问路径信息写入到结构体StAccessPath中。//下面这段逻辑需要改进理想中是可以直接查出起始节点到个节点的路径信息。//暂时没有想到其他好的方法。//现在是申请了顶点个数相当的数组个数其实只用了数组中的第一个空间这个先不改了想为了上面的改进做准备。if (StDks-LowestEdgeArray[i].WeightVal ! MAX_INT_TYPE_NUM){TmpData.StartVertexIndex PushVertexIndex;TmpData.EndVertexIndex StDks-LowestEdgeArray[i].EndVertextIndex;TmpData.Weight AMG-ArcArray[PushVertexIndex][StDks-LowestEdgeArray[i].EndVertextIndex];ClearData2StAccessPath(StDks-LowestEdgeArray[i].AccessPath);PushData2StAccessPath(StDks-LowestEdgeArray[i].AccessPath,TmpData);}}if (*ReturnWeightVal StDks-LowestEdgeArray[i].WeightVal)//找权值最小的索引号。{*ReturnWeightVal StDks-LowestEdgeArray[i].WeightVal;*ReturnVertexIndex StDks-LowestEdgeArray[i].EndVertextIndex;//ShortestWeightIndex i;}}}LogFormat(Debug, %s\n, Push Data To Lowest Edge Array OK.);return SuccessFlag; } 将数据压入最短边数组中。 12、PushData2StDijkstraAccees Status PushData2StDijkstraAccees(StDijkstraAccees* StDA, VertexIndexType InsertNodeIndex, VertexIndexType StartIndex, VertexIndexType EndIndex, WeightType Weight) {JudgeAllNullPointer(StDA);if (InsertNodeIndex StDA-AccessPathMaxLen){LogFormat(Error, Parameter InsertNodeIndex(%d) Need AccessPathMaxLen(%d), Exit.\n, InsertNodeIndex, StDA-AccessPathMaxLen);exit(ExceptionExitFlag);}if (StDA-AccessPath[InsertNodeIndex]-AccessArrayLen StDA-AccessPath[InsertNodeIndex]-AccessArrayMaxLen){LogFormat(Error, AccessPath[%d] Is Full, AccessArrayMaxLen : %d, Exit.\n, InsertNodeIndex, StDA-AccessPath[InsertNodeIndex]-AccessArrayMaxLen);exit(ExceptionExitFlag);}StDA-AccessPath[InsertNodeIndex]-AccessArray[StDA-AccessPath[InsertNodeIndex]-AccessArrayLen].StartVertexIndex StartIndex;StDA-AccessPath[InsertNodeIndex]-AccessArray[StDA-AccessPath[InsertNodeIndex]-AccessArrayLen].EndVertexIndex EndIndex;StDA-AccessPath[InsertNodeIndex]-AccessArray[StDA-AccessPath[InsertNodeIndex]-AccessArrayLen].Weight Weight;StDA-AccessPath[InsertNodeIndex]-AccessArrayLen;LogFormat(Debug, %s\n, Push Data To StDijkstraAccees OK.);return SuccessFlag; } 13、StatisticsStDijkstraAccees //统计起始节点到各个节点的访问路径。 Status StatisticsStDijkstraAccees(StDijkstra* StDks, StDijkstraAccees* StDA, VertexIndexType StartVertexIndex) {JudgeAllNullPointer(StDks);JudgeAllNullPointer(StDA); VertexIndexType i 0;VertexIndexType j 0;VertexIndexType x 0;VertexIndexType TmpIndex 0;//临时变量存放顶点索引信息。VertexIndexType* VisitedArray (VertexIndexType*)MyMalloc(StDks-PathLenArrayLen * sizeof(VertexIndexType));//存放已经命中的索引。for (i 0; i StDks-PathLenArrayMaxLen; i){//LogFormat(Debug,i : %d, StartVertexIndex : %d\n,i,StartVertexIndex);if (StDks-LowestEdgeArray[i].AccessPath-AccessArrayLen 0)//访问节点数组长度为0时跳过。{continue;}//LogFormat(Debug,(%d,%d,%d,%d,%d,%d)\n,VisitedArray[0],VisitedArray[1],VisitedArray[2],VisitedArray[3],VisitedArray[4],VisitedArray[5]);//取最外层的顶点信息如果起始节点等于传入的起始节点索引不需要寻找其祖先顶点。if (StDks-LowestEdgeArray[i].AccessPath-AccessArray[StDks-LowestEdgeArray[i].AccessPath-AccessArrayLen - 1].StartVertexIndex StartVertexIndex){LogFormat(Debug, No Need To Traverse, Find OK, i : %d, StartVertexIndex : %d\n,i,StartVertexIndex);PushData2StDijkstraAccees(StDA, i, StartVertexIndex, StDks-LowestEdgeArray[i].AccessPath-AccessArray[StDks-LowestEdgeArray[i].AccessPath-AccessArrayLen - 1].EndVertexIndex, StDks-LowestEdgeArray[i].AccessPath-AccessArray[StDks-LowestEdgeArray[i].AccessPath-AccessArrayLen - 1].Weight);continue;}for ( x 0; x StDks-PathLenArrayMaxLen; x)//初始化VisitedArray数据{if (StDks-LowestEdgeArray[i].AccessPath-AccessArrayLen 0){VisitedArray[x] VISITED_FLAG;}else{VisitedArray[x] NOT_VISITED_FLAG;}}PushData2StDijkstraAccees(StDA, i, StDks-LowestEdgeArray[i].AccessPath-AccessArray[StDks-LowestEdgeArray[i].AccessPath-AccessArrayLen - 1].StartVertexIndex, StDks-LowestEdgeArray[i].AccessPath-AccessArray[StDks-LowestEdgeArray[i].AccessPath-AccessArrayLen - 1].EndVertexIndex, StDks-LowestEdgeArray[i].AccessPath-AccessArray[StDks-LowestEdgeArray[i].AccessPath-AccessArrayLen - 1].Weight);VisitedArray[i] VISITED_FLAG;TmpIndex StDks-LowestEdgeArray[i].AccessPath-AccessArray[StDks-LowestEdgeArray[i].AccessPath-AccessArrayLen - 1].StartVertexIndex;j 0;while (TmpIndex ! StartVertexIndex){if (VisitedArray[j] VISITED_FLAG)//如果这个节点被访问了就不需要进行访问了{continue;}//LogFormat(Debug,(%d,%d,%d,%d,%d,%d)\n,VisitedArray[0],VisitedArray[1],VisitedArray[2],VisitedArray[3],VisitedArray[4],VisitedArray[5]);//LogFormat(Debug,j : %d, TmpIndex : %d, CmpIndex : %d,StartVertexIndex : %d\n,j,TmpIndex,StDks-LowestEdgeArray[j].AccessPath-AccessArray[StDks-LowestEdgeArray[j].AccessPath-AccessArrayLen - 1].EndVertexIndex,StartVertexIndex);if (TmpIndex StDks-LowestEdgeArray[j].AccessPath-AccessArray[StDks-LowestEdgeArray[j].AccessPath-AccessArrayLen - 1].EndVertexIndex){PushData2StDijkstraAccees(StDA, i, StDks-LowestEdgeArray[j].AccessPath-AccessArray[StDks-LowestEdgeArray[j].AccessPath-AccessArrayLen - 1].StartVertexIndex,TmpIndex,StDks-LowestEdgeArray[j].AccessPath-AccessArray[StDks-LowestEdgeArray[j].AccessPath-AccessArrayLen - 1].Weight);TmpIndex StDks-LowestEdgeArray[j].AccessPath-AccessArray[StDks-LowestEdgeArray[j].AccessPath-AccessArrayLen - 1].StartVertexIndex;VisitedArray[j] VISITED_FLAG;j 0;continue;}j;}//memset(VisitedArray, NOT_VISITED_FLAG, StDks-PathLenArrayLen * sizeof(VertexIndexType));}free(VisitedArray);VisitedArray NULL;LogFormat(Debug, %s\n, Statistics StDijkstraAccees OK.);return SuccessFlag; } 14、DijkstraAlgorithm Status DijkstraAlgorithm(AMGraph* AMG, StDijkstraAccees* StDA, VertexIndexType StartVertexIndex) {JudgeAllNullPointer(AMG);JudgeAllNullPointer(StDA);if (AMG-DirectionFlag ! NET_DIRECTION_FLAG){LogFormat(Warning, Dijkstra Algorithm Need Directed Net.\n);return FailFlag;}StDijkstra* StDks NULL;VertexIndexType ReturnVertexIndex 0;WeightType ReturnWeightVal 0;VertexIndexType TmpVertexIndex 0;NetArcDataType TmpData;InitStDijkstra(StDks, AMG-CurVertexNum, StartVertexIndex);PushData2LowestEdgeArray(StDks, AMG, StartVertexIndex, ReturnVertexIndex, ReturnWeightVal);TmpData.StartVertexIndex StartVertexIndex;TmpData.EndVertexIndex ReturnVertexIndex;TmpData.Weight ReturnWeightVal;TmpVertexIndex ReturnVertexIndex;PushData2PathLenArray(StDks, TmpData);while(StDks-PathLenArrayLen ! StDks-PathLenArrayMaxLen){PushData2LowestEdgeArray(StDks, AMG, TmpVertexIndex, ReturnVertexIndex, ReturnWeightVal);if (ReturnWeightVal MAX_INT_TYPE_NUM)//如果返回无穷大权值说明已经找到所有可访问路径。{LogFormat(Debug, ReturnWeightVal : %d, Find All Access Path Ahead Of Time.\n,MAX_INT_TYPE_NUM);break;}TmpData.StartVertexIndex StartVertexIndex;TmpData.EndVertexIndex ReturnVertexIndex;TmpData.Weight ReturnWeightVal;TmpVertexIndex ReturnVertexIndex;PushData2PathLenArray(StDks, TmpData);}StatisticsStDijkstraAccees(StDks, StDA, StartVertexIndex);DestroyStDijkstra(StDks);LogFormat(Debug, %s\n, Dijkstra Algorithm OK.);return SuccessFlag; } 15、PrintfStDijkstra Status PrintfStDijkstra(StDijkstra* StDks, int PrintLevel) {JudgeAllNullPointer(StDks);VertexIndexType i 0;VertexIndexType j 0;char* string (char*)MyCalloc(STR_TYPE_SIZE, sizeof(char));CopyStr* PS NULL;InitCopyStr(PS);ExecCopyStr(PS,Printf StDijkstra\n);ExecCopyStr(PS,LowestEdgeArray :\n);for (i 0; i StDks-PathLenArrayMaxLen; i){sprintf(string,%3d : (EndVertextIndex : %3d, WeightVal : %5d), [ ,i,StDks-LowestEdgeArray[i].EndVertextIndex,StDks-LowestEdgeArray[i].WeightVal);ExecCopyStr(PS,string);for (j 0; j StDks-LowestEdgeArray[i].AccessPath-AccessArrayLen; j){sprintf(string,(%d,%d,%d),, StDks-LowestEdgeArray[i].AccessPath-AccessArray[j].StartVertexIndex,StDks-LowestEdgeArray[i].AccessPath-AccessArray[j].EndVertexIndex,StDks-LowestEdgeArray[i].AccessPath-AccessArray[j].Weight);ExecCopyStr(PS,string);}PS-String[PS-StrEffectiveLen-1] ;ExecCopyStr(PS,]\n);}ExecCopyStr(PS,PathLenArray : [ );for (i 0; i StDks-PathLenArrayLen; i){sprintf(string,(%d,%d,%d),,StDks-PathLenArray[i].StartVertexIndex,StDks-PathLenArray[i].EndVertexIndex,StDks-PathLenArray[i].Weight);ExecCopyStr(PS,string);}PS-String[PS-StrEffectiveLen-1] ;ExecCopyStr(PS,]\n);sprintf(string,PathLenArrayLen : %d\n,StDks-PathLenArrayLen);ExecCopyStr(PS,string);sprintf(string,PathLenArrayMaxLen : %d\n,StDks-PathLenArrayMaxLen);ExecCopyStr(PS,string);Log(PS-String, PrintLevel);DestroyCopyStr(PS);free(string);string NULL;return SuccessFlag; } 16、PrintfStDijkstraAccees Status PrintfStDijkstraAccees(StDijkstraAccees* StDA, int PrintLevel) {JudgeAllNullPointer(StDA);VertexIndexType i 0;VertexIndexType j 0;char* string (char*)MyCalloc(STR_TYPE_SIZE, sizeof(char));CopyStr* PS NULL;InitCopyStr(PS);ExecCopyStr(PS,Printf StDijkstra\n);ExecCopyStr(PS,AccessPath :\n);for (i 0; i StDA-AccessPathMaxLen; i){ExecCopyStr(PS,[ );for (j 0; j StDA-AccessPath[i]-AccessArrayLen; j){sprintf(string,(%d,%d,%d),,StDA-AccessPath[i]-AccessArray[j].StartVertexIndex,StDA-AccessPath[i]-AccessArray[j].EndVertexIndex,StDA-AccessPath[i]-AccessArray[j].Weight);ExecCopyStr(PS,string);}PS-String[PS-StrEffectiveLen-1] ;ExecCopyStr(PS,]\n);}sprintf(string,AccessPathMaxLen : %d\n,StDA-AccessPathMaxLen);ExecCopyStr(PS,string);Log(PS-String, PrintLevel);DestroyCopyStr(PS);free(string);string NULL;return SuccessFlag; } 七、Linux环境编译测试 1、起点为0 [rootczg2 Graph]# ./TestGraph [2023-7]--[ Debug ]--Create Net Data : OK [2023-7]--[ Debug ]--Create Net Use AMGraph : OK [2023-7]--[ Debug ]--Printf AMGraph : VertexArray : [0 ,1 ,2 ,3 ,4 ,5 ,6 ] ArcArray : [32767 ,13 ,8 ,32767 ,30 ,32767 ,32 ] [32767 ,32767 ,32767 ,32767 ,32767 ,9 ,7 ] [32767 ,32767 ,32767 ,5 ,32767 ,32767 ,32767 ] [32767 ,32767 ,32767 ,32767 ,6 ,32767 ,32767 ] [32767 ,32767 ,32767 ,32767 ,32767 ,2 ,32767 ] [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,17 ] [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,32767 ] CurVertexNum : 7 CurArcNum : 10 [2023-7]--[ Debug ]--Create Net Use AGraph : OK [2023-7]--[ Debug ]--Printf AGraph : 0 : [ (6, 32, 0x18e68d0),(4, 30, 0x18e68b0),(2, 8, 0x18e6890),(1, 13, (nil))] 1 : [ (6, 7, 0x18e6910),(5, 9, (nil))] 2 : [ (3, 5, (nil))] 3 : [ (4, 6, (nil))] 4 : [ (5, 2, (nil))] 5 : [ (6, 17, (nil))] 6 : [] VertexNum : 7 ArcNum : 10 [2023-7]--[ Debug ]--Traverse Use AMGraph : [6 ] [2023-7]--[ Debug ]--Traverse Use AGraph : [6 ] [2023-7]--[ Debug ]--Init SqQueue Normal [2023-7]--[ Debug ]--Enter SqQueue Normal [2023-7]--[ Debug ]--Leave SqQueue Normal [2023-7]--[ Debug ]--Destroy SqQueue Normal [2023-7]--[ Debug ]--Breadth First Search Use AMGraph OK [2023-7]--[ Debug ]--Traverse Use AMGraph : [6 ] [2023-7]--[ Debug ]--Init SqQueue Normal [2023-7]--[ Debug ]--Enter SqQueue Normal [2023-7]--[ Debug ]--Leave SqQueue Normal [2023-7]--[ Debug ]--Destroy SqQueue Normal [2023-7]--[ Debug ]--Breadth First Search Use AGraph OK [2023-7]--[ Debug ]--Traverse Use AGraph : [6 ] [2023-7]--[ Debug ]--Init WeightSortList OK [2023-7]--[ Debug ]--Kluskal WeightSort OK [2023-7]--[ Debug ]--Printf WeightSortList Data : [(4, 5, 2, 0x18e6cb0),(2, 3, 5, 0x18e6cd0),(3, 4, 6, 0x18e6c70),(1, 6, 7, 0x18e6c30),(0, 2, 8, 0x18e6c90),(1, 5, 9, 0x18e6c50),(0, 1, 13, 0x18e6d10),(5, 6, 17, 0x18e6c10),(0, 4, 30, 0x18e6bf0),(0, 6, 32, 0x18e6cf0)] NodeCnt : 10 [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,-1 ,-1 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,-1 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,2 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,2 ,4 ,1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,0 ,2 ,2 ,4 ,1 } [2023-7]--[ Debug ]--Destroy WeightSortList OK [2023-7]--[ Info ]--Kluskal Create MST OK [2023-7]--[ Debug ]--Printf MST { (4,5,2),(2,3,5),(3,4,6),(1,6,7),(0,2,8),(1,5,9)} [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,8),(0,32767),(0,30),(0,32767),(0,32)} ArrayLen : 1 ArrayMaxLen : 7 [2023-7]--[ Debug ]--Init ShortestEdgeArray OK LowestEdgeVertexIndex : 2 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,5),(0,30),(0,32767),(0,32)} ArrayLen : 2 ArrayMaxLen : 7 LowestEdgeVertexIndex : 3 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,6),(0,32767),(0,32)} ArrayLen : 3 ArrayMaxLen : 7 LowestEdgeVertexIndex : 4 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,0),(4,2),(0,32)} ArrayLen : 4 ArrayMaxLen : 7 LowestEdgeVertexIndex : 5 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,0),(4,0),(5,17)} ArrayLen : 5 ArrayMaxLen : 7 LowestEdgeVertexIndex : 1 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,0),(0,0),(2,0),(3,0),(4,0),(1,7)} ArrayLen : 6 ArrayMaxLen : 7 LowestEdgeVertexIndex : 6 [2023-7]--[ Debug ]--Destroy ShortestEdgeArray OK [2023-7]--[ Info ]--Prim Create MST OK [2023-7]--[ Debug ]--Printf MST { (0,2,8),(2,3,5),(3,4,6),(4,5,2),(0,1,13),(1,6,7)} [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StDijkstraAccees OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StDijkstra OK. [2023-7]--[ Debug ]--(StartVertexIndex : 1, EndVertexIndex : 5, Weight : 9) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 1, EndVertexIndex : 6, Weight : 7) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 0, WeightVal : 32767), [ ]1 : (EndVertextIndex : 2, WeightVal : 32767), [ ]2 : (EndVertextIndex : 3, WeightVal : 32767), [ ]3 : (EndVertextIndex : 4, WeightVal : 32767), [ ]4 : (EndVertextIndex : 5, WeightVal : 9), [ (1,5,9) ]5 : (EndVertextIndex : 6, WeightVal : 7), [ (1,6,7) ] PathLenArray : [ (1,6,7) ] PathLenArrayLen : 1 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(0) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(3) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(6) Is Accessed. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 0, WeightVal : 32767), [ ]1 : (EndVertextIndex : 2, WeightVal : 32767), [ ]2 : (EndVertextIndex : 3, WeightVal : 32767), [ ]3 : (EndVertextIndex : 4, WeightVal : 32767), [ ]4 : (EndVertextIndex : 5, WeightVal : 9), [ (1,5,9) ]5 : (EndVertextIndex : 6, WeightVal : 7), [ (1,6,7) ] PathLenArray : [ (1,6,7),(1,5,9) ] PathLenArrayLen : 2 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(0) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(3) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(6) Is Accessed. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--ReturnWeightVal : 32767, Find All Access Path Ahead Of Time. [2023-7]--[ Debug ]--No Need To Traverse, Find OK, i : 4, StartVertexIndex : 1 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--No Need To Traverse, Find OK, i : 5, StartVertexIndex : 1 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Statistics StDijkstraAccees OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StDijkstra OK. [2023-7]--[ Debug ]--Dijkstra Algorithm OK. [2023-7]--[ Debug ]--Printf StDijkstra AccessPath : [ ] [ ] [ ] [ ] [ (1,5,9) ] [ (1,6,7) ] AccessPathMaxLen : 6 [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StDijkstraAccees OK. [2023-7]--[ Debug ]--Destroy Net Data : OK [2023-7]--[ Debug ]--Destroy Net Use AMGraph : OK [2023-7]--[ Debug ]--Destroy Net Use AGraph : OK [rootczg2 Graph]# vim makefile [rootczg2 Graph]# [rootczg2 Graph]# [rootczg2 Graph]# make gcc -Wall -Wextra -O3 ../Log/Log.c ../PublicFunction/PublicFunction.c ../PublicFunction/SqQueue/SqQueue.c Graph.c MinimumSpanningTree.c ShortestPath.c main.c -o TestGraph -I ../Log/ -I ../PublicFunction/ -I ../Select/ -I ../PublicFunction/SqQueue/ [rootczg2 Graph]# ./TestGraph [2023-7]--[ Debug ]--Create Net Data : OK [2023-7]--[ Debug ]--Create Net Use AMGraph : OK [2023-7]--[ Debug ]--Printf AMGraph : VertexArray : [0 ,1 ,2 ,3 ,4 ,5 ,6 ] ArcArray : [32767 ,13 ,8 ,32767 ,30 ,32767 ,32 ] [32767 ,32767 ,32767 ,32767 ,32767 ,9 ,7 ] [32767 ,32767 ,32767 ,5 ,32767 ,32767 ,32767 ] [32767 ,32767 ,32767 ,32767 ,6 ,32767 ,32767 ] [32767 ,32767 ,32767 ,32767 ,32767 ,2 ,32767 ] [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,17 ] [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,32767 ] CurVertexNum : 7 CurArcNum : 10 [2023-7]--[ Debug ]--Create Net Use AGraph : OK [2023-7]--[ Debug ]--Printf AGraph : 0 : [ (6, 32, 0x1e238d0),(4, 30, 0x1e238b0),(2, 8, 0x1e23890),(1, 13, (nil))] 1 : [ (6, 7, 0x1e23910),(5, 9, (nil))] 2 : [ (3, 5, (nil))] 3 : [ (4, 6, (nil))] 4 : [ (5, 2, (nil))] 5 : [ (6, 17, (nil))] 6 : [] VertexNum : 7 ArcNum : 10 [2023-7]--[ Debug ]--Traverse Use AMGraph : [6 ] [2023-7]--[ Debug ]--Traverse Use AGraph : [6 ] [2023-7]--[ Debug ]--Init SqQueue Normal [2023-7]--[ Debug ]--Enter SqQueue Normal [2023-7]--[ Debug ]--Leave SqQueue Normal [2023-7]--[ Debug ]--Destroy SqQueue Normal [2023-7]--[ Debug ]--Breadth First Search Use AMGraph OK [2023-7]--[ Debug ]--Traverse Use AMGraph : [6 ] [2023-7]--[ Debug ]--Init SqQueue Normal [2023-7]--[ Debug ]--Enter SqQueue Normal [2023-7]--[ Debug ]--Leave SqQueue Normal [2023-7]--[ Debug ]--Destroy SqQueue Normal [2023-7]--[ Debug ]--Breadth First Search Use AGraph OK [2023-7]--[ Debug ]--Traverse Use AGraph : [6 ] [2023-7]--[ Debug ]--Init WeightSortList OK [2023-7]--[ Debug ]--Kluskal WeightSort OK [2023-7]--[ Debug ]--Printf WeightSortList Data : [(4, 5, 2, 0x1e23cb0),(2, 3, 5, 0x1e23cd0),(3, 4, 6, 0x1e23c70),(1, 6, 7, 0x1e23c30),(0, 2, 8, 0x1e23c90),(1, 5, 9, 0x1e23c50),(0, 1, 13, 0x1e23d10),(5, 6, 17, 0x1e23c10),(0, 4, 30, 0x1e23bf0),(0, 6, 32, 0x1e23cf0)] NodeCnt : 10 [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,-1 ,-1 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,-1 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,2 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,2 ,4 ,1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,0 ,2 ,2 ,4 ,1 } [2023-7]--[ Debug ]--Destroy WeightSortList OK [2023-7]--[ Info ]--Kluskal Create MST OK [2023-7]--[ Debug ]--Printf MST { (4,5,2),(2,3,5),(3,4,6),(1,6,7),(0,2,8),(1,5,9)} [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,8),(0,32767),(0,30),(0,32767),(0,32)} ArrayLen : 1 ArrayMaxLen : 7 [2023-7]--[ Debug ]--Init ShortestEdgeArray OK LowestEdgeVertexIndex : 2 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,5),(0,30),(0,32767),(0,32)} ArrayLen : 2 ArrayMaxLen : 7 LowestEdgeVertexIndex : 3 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,6),(0,32767),(0,32)} ArrayLen : 3 ArrayMaxLen : 7 LowestEdgeVertexIndex : 4 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,0),(4,2),(0,32)} ArrayLen : 4 ArrayMaxLen : 7 LowestEdgeVertexIndex : 5 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,0),(4,0),(5,17)} ArrayLen : 5 ArrayMaxLen : 7 LowestEdgeVertexIndex : 1 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,0),(0,0),(2,0),(3,0),(4,0),(1,7)} ArrayLen : 6 ArrayMaxLen : 7 LowestEdgeVertexIndex : 6 [2023-7]--[ Debug ]--Destroy ShortestEdgeArray OK [2023-7]--[ Info ]--Prim Create MST OK [2023-7]--[ Debug ]--Printf MST { (0,2,8),(2,3,5),(3,4,6),(4,5,2),(0,1,13),(1,6,7)} [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StDijkstraAccees OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StDijkstra OK. [2023-7]--[ Debug ]--(StartVertexIndex : 0, EndVertexIndex : 1, Weight : 13) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 0, EndVertexIndex : 2, Weight : 8) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 0, EndVertexIndex : 4, Weight : 30) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 0, EndVertexIndex : 6, Weight : 32) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 32767), [ ]3 : (EndVertextIndex : 4, WeightVal : 30), [ (0,4,30) ]4 : (EndVertextIndex : 5, WeightVal : 32767), [ ]5 : (EndVertextIndex : 6, WeightVal : 32), [ (0,6,32) ] PathLenArray : [ (0,2,8) ] PathLenArrayLen : 1 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(1) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(3) Is Not Accessed. [2023-7]--[ Debug ]--Clear Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 2, EndVertexIndex : 3, Weight : 5) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(4) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(6) Is Not Accessed. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ]3 : (EndVertextIndex : 4, WeightVal : 30), [ (0,4,30) ]4 : (EndVertextIndex : 5, WeightVal : 32767), [ ]5 : (EndVertextIndex : 6, WeightVal : 32), [ (0,6,32) ] PathLenArray : [ (0,2,8),(0,1,13) ] PathLenArrayLen : 2 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(1) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(3) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Not Accessed. [2023-7]--[ Debug ]--Clear Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 1, EndVertexIndex : 5, Weight : 9) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(6) Is Not Accessed. [2023-7]--[ Debug ]--Clear Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 1, EndVertexIndex : 6, Weight : 7) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ]3 : (EndVertextIndex : 4, WeightVal : 30), [ (0,4,30) ]4 : (EndVertextIndex : 5, WeightVal : 22), [ (1,5,9) ]5 : (EndVertextIndex : 6, WeightVal : 20), [ (1,6,7) ] PathLenArray : [ (0,2,8),(0,1,13),(0,3,13) ] PathLenArrayLen : 3 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(1) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(3) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Not Accessed. [2023-7]--[ Debug ]--Clear Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 3, EndVertexIndex : 4, Weight : 6) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(5) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(6) Is Not Accessed. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ]3 : (EndVertextIndex : 4, WeightVal : 19), [ (3,4,6) ]4 : (EndVertextIndex : 5, WeightVal : 22), [ (1,5,9) ]5 : (EndVertextIndex : 6, WeightVal : 20), [ (1,6,7) ] PathLenArray : [ (0,2,8),(0,1,13),(0,3,13),(0,4,19) ] PathLenArrayLen : 4 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(1) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(3) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Not Accessed. [2023-7]--[ Debug ]--Clear Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 4, EndVertexIndex : 5, Weight : 2) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(6) Is Not Accessed. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ]3 : (EndVertextIndex : 4, WeightVal : 19), [ (3,4,6) ]4 : (EndVertextIndex : 5, WeightVal : 21), [ (4,5,2) ]5 : (EndVertextIndex : 6, WeightVal : 20), [ (1,6,7) ] PathLenArray : [ (0,2,8),(0,1,13),(0,3,13),(0,4,19),(0,6,20) ] PathLenArrayLen : 5 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(1) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(3) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(6) Is Accessed. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 1, WeightVal : 13), [ (0,1,13) ]1 : (EndVertextIndex : 2, WeightVal : 8), [ (0,2,8) ]2 : (EndVertextIndex : 3, WeightVal : 13), [ (2,3,5) ]3 : (EndVertextIndex : 4, WeightVal : 19), [ (3,4,6) ]4 : (EndVertextIndex : 5, WeightVal : 21), [ (4,5,2) ]5 : (EndVertextIndex : 6, WeightVal : 20), [ (1,6,7) ] PathLenArray : [ (0,2,8),(0,1,13),(0,3,13),(0,4,19),(0,6,20),(0,5,21) ] PathLenArrayLen : 6 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--No Need To Traverse, Find OK, i : 0, StartVertexIndex : 0 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--No Need To Traverse, Find OK, i : 1, StartVertexIndex : 0 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--(0,0,1,0,0,0) [2023-7]--[ Debug ]--j : 0, TmpIndex : 2, CmpIndex : 1,StartVertexIndex : 0 [2023-7]--[ Debug ]--(0,0,1,0,0,0) [2023-7]--[ Debug ]--j : 1, TmpIndex : 2, CmpIndex : 2,StartVertexIndex : 0 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--(0,0,0,1,0,0) [2023-7]--[ Debug ]--j : 0, TmpIndex : 3, CmpIndex : 1,StartVertexIndex : 0 [2023-7]--[ Debug ]--(0,0,0,1,0,0) [2023-7]--[ Debug ]--j : 1, TmpIndex : 3, CmpIndex : 2,StartVertexIndex : 0 [2023-7]--[ Debug ]--(0,0,0,1,0,0) [2023-7]--[ Debug ]--j : 2, TmpIndex : 3, CmpIndex : 3,StartVertexIndex : 0 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--(0,0,1,1,0,0) [2023-7]--[ Debug ]--j : 0, TmpIndex : 2, CmpIndex : 1,StartVertexIndex : 0 [2023-7]--[ Debug ]--(0,0,1,1,0,0) [2023-7]--[ Debug ]--j : 1, TmpIndex : 2, CmpIndex : 2,StartVertexIndex : 0 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--(0,0,0,0,1,0) [2023-7]--[ Debug ]--j : 0, TmpIndex : 4, CmpIndex : 1,StartVertexIndex : 0 [2023-7]--[ Debug ]--(0,0,0,0,1,0) [2023-7]--[ Debug ]--j : 1, TmpIndex : 4, CmpIndex : 2,StartVertexIndex : 0 [2023-7]--[ Debug ]--(0,0,0,0,1,0) [2023-7]--[ Debug ]--j : 2, TmpIndex : 4, CmpIndex : 3,StartVertexIndex : 0 [2023-7]--[ Debug ]--(0,0,0,0,1,0) [2023-7]--[ Debug ]--j : 3, TmpIndex : 4, CmpIndex : 4,StartVertexIndex : 0 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--(0,0,0,1,1,0) [2023-7]--[ Debug ]--j : 0, TmpIndex : 3, CmpIndex : 1,StartVertexIndex : 0 [2023-7]--[ Debug ]--(0,0,0,1,1,0) [2023-7]--[ Debug ]--j : 1, TmpIndex : 3, CmpIndex : 2,StartVertexIndex : 0 [2023-7]--[ Debug ]--(0,0,0,1,1,0) [2023-7]--[ Debug ]--j : 2, TmpIndex : 3, CmpIndex : 3,StartVertexIndex : 0 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--(0,0,1,1,1,0) [2023-7]--[ Debug ]--j : 0, TmpIndex : 2, CmpIndex : 1,StartVertexIndex : 0 [2023-7]--[ Debug ]--(0,0,1,1,1,0) [2023-7]--[ Debug ]--j : 1, TmpIndex : 2, CmpIndex : 2,StartVertexIndex : 0 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--(0,0,0,0,0,1) [2023-7]--[ Debug ]--j : 0, TmpIndex : 1, CmpIndex : 1,StartVertexIndex : 0 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Statistics StDijkstraAccees OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StDijkstra OK. [2023-7]--[ Debug ]--Dijkstra Algorithm OK. [2023-7]--[ Debug ]--Printf StDijkstra AccessPath : [ (0,1,13) ] [ (0,2,8) ] [ (2,3,5),(0,2,8) ] [ (3,4,6),(2,3,5),(0,2,8) ] [ (4,5,2),(3,4,6),(2,3,5),(0,2,8) ] [ (1,6,7),(0,1,13) ] AccessPathMaxLen : 6 [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StDijkstraAccees OK. [2023-7]--[ Debug ]--Destroy Net Data : OK [2023-7]--[ Debug ]--Destroy Net Use AMGraph : OK [2023-7]--[ Debug ]--Destroy Net Use AGraph : OK 2、起点为1 [rootczg2 Graph]# ./TestGraph [2023-7]--[ Debug ]--Create Net Data : OK [2023-7]--[ Debug ]--Create Net Use AMGraph : OK [2023-7]--[ Debug ]--Printf AMGraph : VertexArray : [0 ,1 ,2 ,3 ,4 ,5 ,6 ] ArcArray : [32767 ,13 ,8 ,32767 ,30 ,32767 ,32 ] [32767 ,32767 ,32767 ,32767 ,32767 ,9 ,7 ] [32767 ,32767 ,32767 ,5 ,32767 ,32767 ,32767 ] [32767 ,32767 ,32767 ,32767 ,6 ,32767 ,32767 ] [32767 ,32767 ,32767 ,32767 ,32767 ,2 ,32767 ] [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,17 ] [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,32767 ] CurVertexNum : 7 CurArcNum : 10 [2023-7]--[ Debug ]--Create Net Use AGraph : OK [2023-7]--[ Debug ]--Printf AGraph : 0 : [ (6, 32, 0x18e68d0),(4, 30, 0x18e68b0),(2, 8, 0x18e6890),(1, 13, (nil))] 1 : [ (6, 7, 0x18e6910),(5, 9, (nil))] 2 : [ (3, 5, (nil))] 3 : [ (4, 6, (nil))] 4 : [ (5, 2, (nil))] 5 : [ (6, 17, (nil))] 6 : [] VertexNum : 7 ArcNum : 10 [2023-7]--[ Debug ]--Traverse Use AMGraph : [6 ] [2023-7]--[ Debug ]--Traverse Use AGraph : [6 ] [2023-7]--[ Debug ]--Init SqQueue Normal [2023-7]--[ Debug ]--Enter SqQueue Normal [2023-7]--[ Debug ]--Leave SqQueue Normal [2023-7]--[ Debug ]--Destroy SqQueue Normal [2023-7]--[ Debug ]--Breadth First Search Use AMGraph OK [2023-7]--[ Debug ]--Traverse Use AMGraph : [6 ] [2023-7]--[ Debug ]--Init SqQueue Normal [2023-7]--[ Debug ]--Enter SqQueue Normal [2023-7]--[ Debug ]--Leave SqQueue Normal [2023-7]--[ Debug ]--Destroy SqQueue Normal [2023-7]--[ Debug ]--Breadth First Search Use AGraph OK [2023-7]--[ Debug ]--Traverse Use AGraph : [6 ] [2023-7]--[ Debug ]--Init WeightSortList OK [2023-7]--[ Debug ]--Kluskal WeightSort OK [2023-7]--[ Debug ]--Printf WeightSortList Data : [(4, 5, 2, 0x18e6cb0),(2, 3, 5, 0x18e6cd0),(3, 4, 6, 0x18e6c70),(1, 6, 7, 0x18e6c30),(0, 2, 8, 0x18e6c90),(1, 5, 9, 0x18e6c50),(0, 1, 13, 0x18e6d10),(5, 6, 17, 0x18e6c10),(0, 4, 30, 0x18e6bf0),(0, 6, 32, 0x18e6cf0)] NodeCnt : 10 [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,-1 ,-1 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,-1 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,2 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,2 ,4 ,1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,0 ,2 ,2 ,4 ,1 } [2023-7]--[ Debug ]--Destroy WeightSortList OK [2023-7]--[ Info ]--Kluskal Create MST OK [2023-7]--[ Debug ]--Printf MST { (4,5,2),(2,3,5),(3,4,6),(1,6,7),(0,2,8),(1,5,9)} [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,8),(0,32767),(0,30),(0,32767),(0,32)} ArrayLen : 1 ArrayMaxLen : 7 [2023-7]--[ Debug ]--Init ShortestEdgeArray OK LowestEdgeVertexIndex : 2 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,5),(0,30),(0,32767),(0,32)} ArrayLen : 2 ArrayMaxLen : 7 LowestEdgeVertexIndex : 3 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,6),(0,32767),(0,32)} ArrayLen : 3 ArrayMaxLen : 7 LowestEdgeVertexIndex : 4 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,0),(4,2),(0,32)} ArrayLen : 4 ArrayMaxLen : 7 LowestEdgeVertexIndex : 5 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,0),(4,0),(5,17)} ArrayLen : 5 ArrayMaxLen : 7 LowestEdgeVertexIndex : 1 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,0),(0,0),(2,0),(3,0),(4,0),(1,7)} ArrayLen : 6 ArrayMaxLen : 7 LowestEdgeVertexIndex : 6 [2023-7]--[ Debug ]--Destroy ShortestEdgeArray OK [2023-7]--[ Info ]--Prim Create MST OK [2023-7]--[ Debug ]--Printf MST { (0,2,8),(2,3,5),(3,4,6),(4,5,2),(0,1,13),(1,6,7)} [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StDijkstraAccees OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StDijkstra OK. [2023-7]--[ Debug ]--(StartVertexIndex : 1, EndVertexIndex : 5, Weight : 9) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 1, EndVertexIndex : 6, Weight : 7) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 0, WeightVal : 32767), [ ]1 : (EndVertextIndex : 2, WeightVal : 32767), [ ]2 : (EndVertextIndex : 3, WeightVal : 32767), [ ]3 : (EndVertextIndex : 4, WeightVal : 32767), [ ]4 : (EndVertextIndex : 5, WeightVal : 9), [ (1,5,9) ]5 : (EndVertextIndex : 6, WeightVal : 7), [ (1,6,7) ] PathLenArray : [ (1,6,7) ] PathLenArrayLen : 1 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(0) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(3) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(6) Is Accessed. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 0, WeightVal : 32767), [ ]1 : (EndVertextIndex : 2, WeightVal : 32767), [ ]2 : (EndVertextIndex : 3, WeightVal : 32767), [ ]3 : (EndVertextIndex : 4, WeightVal : 32767), [ ]4 : (EndVertextIndex : 5, WeightVal : 9), [ (1,5,9) ]5 : (EndVertextIndex : 6, WeightVal : 7), [ (1,6,7) ] PathLenArray : [ (1,6,7),(1,5,9) ] PathLenArrayLen : 2 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(0) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(3) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(6) Is Accessed. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--ReturnWeightVal : 32767, Find All Access Path Ahead Of Time. [2023-7]--[ Debug ]--No Need To Traverse, Find OK, i : 4, StartVertexIndex : 1 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--No Need To Traverse, Find OK, i : 5, StartVertexIndex : 1 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Statistics StDijkstraAccees OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StDijkstra OK. [2023-7]--[ Debug ]--Dijkstra Algorithm OK. [2023-7]--[ Debug ]--Printf StDijkstra AccessPath : [ ] [ ] [ ] [ ] [ (1,5,9) ] [ (1,6,7) ] AccessPathMaxLen : 6 [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StDijkstraAccees OK. [2023-7]--[ Debug ]--Destroy Net Data : OK [2023-7]--[ Debug ]--Destroy Net Use AMGraph : OK [2023-7]--[ Debug ]--Destroy Net Use AGraph : OK 3、起点为3 [rootczg2 Graph]# ./TestGraph [2023-7]--[ Debug ]--Create Net Data : OK [2023-7]--[ Debug ]--Create Net Use AMGraph : OK [2023-7]--[ Debug ]--Printf AMGraph : VertexArray : [0 ,1 ,2 ,3 ,4 ,5 ,6 ] ArcArray : [32767 ,13 ,8 ,32767 ,30 ,32767 ,32 ] [32767 ,32767 ,32767 ,32767 ,32767 ,9 ,7 ] [32767 ,32767 ,32767 ,5 ,32767 ,32767 ,32767 ] [32767 ,32767 ,32767 ,32767 ,6 ,32767 ,32767 ] [32767 ,32767 ,32767 ,32767 ,32767 ,2 ,32767 ] [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,17 ] [32767 ,32767 ,32767 ,32767 ,32767 ,32767 ,32767 ] CurVertexNum : 7 CurArcNum : 10 [2023-7]--[ Debug ]--Create Net Use AGraph : OK [2023-7]--[ Debug ]--Printf AGraph : 0 : [ (6, 32, 0xdcd8d0),(4, 30, 0xdcd8b0),(2, 8, 0xdcd890),(1, 13, (nil))] 1 : [ (6, 7, 0xdcd910),(5, 9, (nil))] 2 : [ (3, 5, (nil))] 3 : [ (4, 6, (nil))] 4 : [ (5, 2, (nil))] 5 : [ (6, 17, (nil))] 6 : [] VertexNum : 7 ArcNum : 10 [2023-7]--[ Debug ]--Traverse Use AMGraph : [6 ] [2023-7]--[ Debug ]--Traverse Use AGraph : [6 ] [2023-7]--[ Debug ]--Init SqQueue Normal [2023-7]--[ Debug ]--Enter SqQueue Normal [2023-7]--[ Debug ]--Leave SqQueue Normal [2023-7]--[ Debug ]--Destroy SqQueue Normal [2023-7]--[ Debug ]--Breadth First Search Use AMGraph OK [2023-7]--[ Debug ]--Traverse Use AMGraph : [6 ] [2023-7]--[ Debug ]--Init SqQueue Normal [2023-7]--[ Debug ]--Enter SqQueue Normal [2023-7]--[ Debug ]--Leave SqQueue Normal [2023-7]--[ Debug ]--Destroy SqQueue Normal [2023-7]--[ Debug ]--Breadth First Search Use AGraph OK [2023-7]--[ Debug ]--Traverse Use AGraph : [6 ] [2023-7]--[ Debug ]--Init WeightSortList OK [2023-7]--[ Debug ]--Kluskal WeightSort OK [2023-7]--[ Debug ]--Printf WeightSortList Data : [(4, 5, 2, 0xdcdcb0),(2, 3, 5, 0xdcdcd0),(3, 4, 6, 0xdcdc70),(1, 6, 7, 0xdcdc30),(0, 2, 8, 0xdcdc90),(1, 5, 9, 0xdcdc50),(0, 1, 13, 0xdcdd10),(5, 6, 17, 0xdcdc10),(0, 4, 30, 0xdcdbf0),(0, 6, 32, 0xdcdcf0)] NodeCnt : 10 [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,-1 ,-1 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,-1 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,2 ,4 ,-1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,-1 ,2 ,2 ,4 ,1 } [2023-7]--[ Debug ]--Printf Parent Array { -1 ,-1 ,0 ,2 ,2 ,4 ,1 } [2023-7]--[ Debug ]--Destroy WeightSortList OK [2023-7]--[ Info ]--Kluskal Create MST OK [2023-7]--[ Debug ]--Printf MST { (4,5,2),(2,3,5),(3,4,6),(1,6,7),(0,2,8),(1,5,9)} [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,8),(0,32767),(0,30),(0,32767),(0,32)} ArrayLen : 1 ArrayMaxLen : 7 [2023-7]--[ Debug ]--Init ShortestEdgeArray OK LowestEdgeVertexIndex : 2 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,5),(0,30),(0,32767),(0,32)} ArrayLen : 2 ArrayMaxLen : 7 LowestEdgeVertexIndex : 3 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,6),(0,32767),(0,32)} ArrayLen : 3 ArrayMaxLen : 7 LowestEdgeVertexIndex : 4 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,0),(4,2),(0,32)} ArrayLen : 4 ArrayMaxLen : 7 LowestEdgeVertexIndex : 5 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,13),(0,0),(2,0),(3,0),(4,0),(5,17)} ArrayLen : 5 ArrayMaxLen : 7 LowestEdgeVertexIndex : 1 [2023-7]--[ Debug ]--Printf ShortestEdgeArray {(0,0),(0,0),(0,0),(2,0),(3,0),(4,0),(1,7)} ArrayLen : 6 ArrayMaxLen : 7 LowestEdgeVertexIndex : 6 [2023-7]--[ Debug ]--Destroy ShortestEdgeArray OK [2023-7]--[ Info ]--Prim Create MST OK [2023-7]--[ Debug ]--Printf MST { (0,2,8),(2,3,5),(3,4,6),(4,5,2),(0,1,13),(1,6,7)} [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StDijkstraAccees OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StAccessPath OK. [2023-7]--[ Debug ]--Init StDijkstra OK. [2023-7]--[ Debug ]--(StartVertexIndex : 3, EndVertexIndex : 4, Weight : 6) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 0, WeightVal : 32767), [ ]1 : (EndVertextIndex : 1, WeightVal : 32767), [ ]2 : (EndVertextIndex : 2, WeightVal : 32767), [ ]3 : (EndVertextIndex : 4, WeightVal : 6), [ (3,4,6) ]4 : (EndVertextIndex : 5, WeightVal : 32767), [ ]5 : (EndVertextIndex : 6, WeightVal : 32767), [ ] PathLenArray : [ (3,4,6) ] PathLenArrayLen : 1 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(0) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(1) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Not Accessed. [2023-7]--[ Debug ]--Clear Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 4, EndVertexIndex : 5, Weight : 2) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(6) Is Not Accessed. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 0, WeightVal : 32767), [ ]1 : (EndVertextIndex : 1, WeightVal : 32767), [ ]2 : (EndVertextIndex : 2, WeightVal : 32767), [ ]3 : (EndVertextIndex : 4, WeightVal : 6), [ (3,4,6) ]4 : (EndVertextIndex : 5, WeightVal : 8), [ (4,5,2) ]5 : (EndVertextIndex : 6, WeightVal : 32767), [ ] PathLenArray : [ (3,4,6),(3,5,8) ] PathLenArrayLen : 2 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(0) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(1) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(6) Is Not Accessed. [2023-7]--[ Debug ]--Clear Data To StAccessPath OK. [2023-7]--[ Debug ]--(StartVertexIndex : 5, EndVertexIndex : 6, Weight : 17) [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--Printf StDijkstra LowestEdgeArray :0 : (EndVertextIndex : 0, WeightVal : 32767), [ ]1 : (EndVertextIndex : 1, WeightVal : 32767), [ ]2 : (EndVertextIndex : 2, WeightVal : 32767), [ ]3 : (EndVertextIndex : 4, WeightVal : 6), [ (3,4,6) ]4 : (EndVertextIndex : 5, WeightVal : 8), [ (4,5,2) ]5 : (EndVertextIndex : 6, WeightVal : 25), [ (5,6,17) ] PathLenArray : [ (3,4,6),(3,5,8),(3,6,25) ] PathLenArrayLen : 3 PathLenArrayMaxLen : 6 [2023-7]--[ Debug ]--Push Data To StAccessPath OK. [2023-7]--[ Debug ]--Judge Vertex(0) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(1) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(2) Is Not Accessed. [2023-7]--[ Debug ]--Judge Vertex(4) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(5) Is Accessed. [2023-7]--[ Debug ]--Judge Vertex(6) Is Accessed. [2023-7]--[ Debug ]--Push Data To Lowest Edge Array OK. [2023-7]--[ Debug ]--ReturnWeightVal : 32767, Find All Access Path Ahead Of Time. [2023-7]--[ Debug ]--No Need To Traverse, Find OK, i : 3, StartVertexIndex : 3 [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Push Data To StDijkstraAccees OK. [2023-7]--[ Debug ]--Statistics StDijkstraAccees OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StDijkstra OK. [2023-7]--[ Debug ]--Dijkstra Algorithm OK. [2023-7]--[ Debug ]--Printf StDijkstra AccessPath : [ ] [ ] [ ] [ (3,4,6) ] [ (4,5,2),(3,4,6) ] [ (5,6,17),(4,5,2),(3,4,6) ] AccessPathMaxLen : 6 [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StAccessPath OK. [2023-7]--[ Debug ]--Destroy StDijkstraAccees OK. [2023-7]--[ Debug ]--Destroy Net Data : OK [2023-7]--[ Debug ]--Destroy Net Use AMGraph : OK [2023-7]--[ Debug ]--Destroy Net Use AGraph : OK

查看全文

http://www.dnsts.com.cn/news/199207.html