之前在网上面看到这个算法还有提到如果使用堆的话会减低时间复杂度。然后就在想如果使用堆的话代码应该如何实现。然后尝试自己写一个出来进行测试。测试了一副图没有问题。写一篇博客记录一下之前写的代码。

#defineINF99999999structSortNode{intNodeLabel;intPathLength;};voidswap(SortNode*a,SortNode*b){SortNodetemp=*b;*b=*a;*a=temp;}voidmax_heapify(SortNodearr[],intstart,intend){intdad=start;intson=dad*2+1;while(son<=end){if(son+1<=end&&(arr[son].PathLength>arr[son+1].PathLength))son++;if(arr[dad].PathLength<arr[son].PathLength)return;else{swap(&arr[dad],&arr[son]);dad=son;son=dad*2+1;}}}voidDijkstra(int**iPath,intnNodeNum,int*pOutputDistance,int**OutPutPath){if(nNodeNum==1){pOutputDistance[0]=0;OutPutPath[0][0]=0;return;}SortNode*heap=newSortNode[nNodeNum];for(inti=nNodeNum-1;i>=0;i--){heap[i].NodeLabel=i;heap[i].PathLength=iPath[0][i];if(heap[i].PathLength<INF){OutPutPath[i][0]=0;OutPutPath[i][1]=i;if(2<nNodeNum)OutPutPath[i][2]=0;}max_heapify(heap,i,nNodeNum-1);}for(inti=nNodeNum-1;i>0;i--){swap(&heap[0],&heap[i]);max_heapify(heap,0,i-1);for(intj=i-1;j>0;j--){if(iPath[heap[0].NodeLabel][heap[j].NodeLabel]<INF){intnewPathLength=heap[0].PathLength+iPath[heap[0].NodeLabel][heap[j].NodeLabel];if(newPathLength<(heap[j].PathLength)){heap[j].PathLength=newPathLength;OutPutPath[heap[j].NodeLabel][0]=OutPutPath[heap[0].NodeLabel][0];for(intk=1;k<nNodeNum;k++){if(OutPutPath[heap[0].NodeLabel][k]!=0){OutPutPath[heap[j].NodeLabel][k]=OutPutPath[heap[0].NodeLabel][k];}else{OutPutPath[heap[j].NodeLabel][k]=heap[j].NodeLabel;if((k+1)<nNodeNum)OutPutPath[heap[j].NodeLabel][k+1]=0;break;}}max_heapify(heap,j,i-1);}}}}for(inti=0;i<nNodeNum;i++){pOutputDistance[heap[i].NodeLabel]=heap[i].PathLength;}delete[]heap;}

以上就是我写的实现代码。自己写了一个main函数来测试。

intmain(){inte[10][10];intn=0,m=0;scanf_s("%d%d",&n,&m);for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(i==j)e[i][j]=0;elsee[i][j]=INF;}}intt1,t2,t3;for(inti=0;i<m;i++){scanf_s("%d%d%d",&t1,&t2,&t3);e[t1-1][t2-1]=t3;}int*a[10];for(inti=0;i<10;i++){a[i]=e[i];}intdis[10];intoutputPath[10][10];int*b[10];for(inti=0;i<10;i++){b[i]=outputPath[i];}Dijkstra(a,n,dis,b);for(inti=0;i<n;i++)printf("%d",dis[i]);printf("\n");for(inti=0;i<n;i++){printf("%d",outputPath[i][0]+1);for(intj=1;j<n;j++){if(outputPath[i][j]>0){printf("->%d",outputPath[i][j]+1);}elsebreak;}printf("\n");}}

使用了网上面的一张图来测试。


下面是运行结果截图: