Radix Heap ---Dijkstra算法的优化 BY Gremount-白红宇

Radix Heap ---Dijkstra算法的优化 BY Gremount

阅读量：6474 次

发布时间：2019-06-23

本文共 8538 字，大约阅读时间需要 28 分钟。

Radix Heap 算法是在Dijkstra的Dial实现的基础上，通过减少对桶的使用，来优化算法的时间复杂度:

Dial 时间复杂度是O(m+nC) -------C是最长的链路

Radix Heap 时间复杂度是O(m+n*log(nC))

本质上来说Radix Heap是Dial和Dijkstra的折中，因为Dial用NC个桶，Dijkstra用1个桶

下面是本程序中使用的一些函数介绍：

void radix_heap():

（1）对所有桶的range初始化

（2）所有节点的初始化(这一步可以在建图的时候完成)；

（2）除开始点，其他全部放入无穷桶里，注意这里的无穷桶的id=初始d值对2求对数后上去整；

（3）更新源节点

（4）后续是找最小值和更新的操作循环（类似于dijkstra算法）

int FindMin():

（1）移动指针到第一个不为空的桶

（2）如果桶的编号是0或者1，则任取元素出来返回；

如果编号大于1且桶内元素个数为1，则将该元素取出来返回；

如果编号大于1且桶内的元素个数大于1，则先找出最小值，再执行redistribute()

重置桶里的元素

int Redistribute():

（1）根据最小值，更改桶的range，修改range和桶的映射；

（2）将该桶内的元素重置位置，返回最小值；

void Update(int i):

根据i点的d值和邻接边的值来更改与i相连的其他节点的d值；

下面是我写的程序，分为三部分，第一部分是主程序，第二部分是资源程序，第三部分是头文件

第一部分：创建如下图：

//radix_heap.cpp 主程序：完成图的创建和最短路函数调用#include "resources.h"CEdge::CEdge(int a, int b, int c, int d){	tail=a;	head=b;	weight=c;	capacity=d;}CEdge::CEdge(int a, int b, int c){	head=b;	tail=a;	weight=c;}CEdge::CEdge(CEdge & x){	tail=x.getTail();	head=x.getHead();	weight=x.getWeight();	capacity=x.getCap();}CGraph::CGraph(list
    
      listEdge){	IncidentList=listEdge;	numVertex=N;	numEdge=listEdge.size();}int main(){	list
     
       listEdge;		CEdge* e1=new CEdge(1,2,1,10);	CEdge* e2=new CEdge(2,1,1,10);	CEdge* e3=new CEdge(1,7,1,10);	CEdge* e4=new CEdge(7,1,1,10);	CEdge* e5=new CEdge(7,10,1,10);	CEdge* e6=new CEdge(10,7,1,10);	CEdge* e7=new CEdge(3,2,1,10);	CEdge* e8=new CEdge(2,3,1,10);	CEdge* e9=new CEdge(3,4,1,10);	CEdge* e10=new CEdge(4,3,1,10);	CEdge* e11=new CEdge(4,10,1,10);	CEdge* e12=new CEdge(10,4,1,10);	CEdge* e13=new CEdge(1,5,1,10);	CEdge* e14=new CEdge(5,1,1,10);	CEdge* e15=new CEdge(6,5,1,10);	CEdge* e16=new CEdge(5,6,1,10);	CEdge* e17=new CEdge(6,10,1,10);	CEdge* e18=new CEdge(10,6,1,10);	CEdge* e19=new CEdge(8,10,1,10);	CEdge* e20=new CEdge(10,8,1,10);	CEdge* e21=new CEdge(9,10,1,10);	CEdge* e22=new CEdge(10,9,1,10);	listEdge.push_back(e1);	listEdge.push_back(e2);	listEdge.push_back(e3);	listEdge.push_back(e4);	listEdge.push_back(e5);	listEdge.push_back(e6);	listEdge.push_back(e7);	listEdge.push_back(e8);	listEdge.push_back(e9);	listEdge.push_back(e10);	listEdge.push_back(e11);	listEdge.push_back(e12);	listEdge.push_back(e13);	listEdge.push_back(e14);	listEdge.push_back(e15);	listEdge.push_back(e16);	listEdge.push_back(e17);	listEdge.push_back(e18);	listEdge.push_back(e19);	listEdge.push_back(e20);	listEdge.push_back(e21);	listEdge.push_back(e22);	CGraph g(listEdge);	g.p1();	g.p2();	g.p3();	g.p4();	g.radix_heap(g,1);	getchar();	return 0;}

第二部分：

//resources.h 所用的类：点，边，图//图中包含对图的测量函数（p1`、p2、p3、p4）//radix_heap() FindMin() Update() Redistribute()#include "common.h"class CVertex{public:	int d;	int p;	int ID;	CVertex(int x){ID=x;d=INF;p=NULL;}	~CVertex(){;}};class CEdge{private:	int tail, head;	int weight, capacity;public:	CEdge(int a, int b, int c, int d);	CEdge(int a, int b, int c);	CEdge(CEdge &x);	int getHead(){return head;}	int getTail(){return tail;}	int getWeight(){return weight;}	int getCap(){return capacity;}	bool operator<(CEdge& x){		if(weight
    
      IncidentList;public:	set
     
       S;	set
      
        V;	int d[N+10];	int p[N+10];	map
       
         degree_vertex;	multimap
        
          degree_vertex2;	map
         
          
           > adjlist; vector
           
            
             > adjmatrix; map
             
              
               > nelist; map
               
                
                 > mapBuckets; map
                 
                   mapVID_Vertex; map
                  
                   
                    >::iterator itBucket; map
                    
                     ::iterator itcv; int range[2024]; int rbegin[20]; int rend[20]; int zhishu; int db[20]; CGraph(char* inputFile); CGraph(list
                     
                       listEdge); CGraph(CGraph &); void init() { //range表初始化 zhishu=2; rbegin[0]=1; rend[0]=1; rbegin[1]=2; rend[1]=2; for(int i=2;i<=10;i++) { zhishu=zhishu*2; rbegin[i]=rend[i-1]+1; rend[i]=zhishu; } //等比数列初始化 db[1]=1; for(int i=2;i<=10;i++) db[i]=db[i-1]*2; } int getNumVertex(){ return numVertex; } int getNumEdge(){ return numEdge; } int cmp(const pair
                      
                        &x, const pair
                       
                         &y){ return x.second > y.second; } void p1(){ list
                        
                         ::iterator it,iend; multimap
                         
                          ::iterator it2; iend=IncidentList.end(); vector
                          
                           
                            > dv_vec; for(int i=1;i<=N;i++) degree_vertex[i]=0; for(it=IncidentList.begin();it!=iend;it++) degree_vertex[(*it)->getTail()]++; for(int i=1;i<=N;i++) degree_vertex2.insert(pair
                            
                             (degree_vertex[i],i)); it2=--degree_vertex2.end(); printf("project 1:\n"); for(;it2!=degree_vertex2.begin();it2--) printf("%d,%d\n",it2->second,it2->first); } void p2(){ list
                             
                              ::iterator it,iend; list
                              
                               ::iterator it2,iend2; iend=IncidentList.end(); //printf("incidentList:\n"); for(it=IncidentList.begin();it!=iend;it++){ adjlist[(*it)->getTail()].push_back((*it)->getHead()); //printf("%d,%d\n",(*it)->getTail(),(*it)->getHead()); } it2=adjlist[3].begin(); iend2=adjlist[3].end(); printf("\n"); printf("project 2:\n"); printf("3:"); for(;it2!=iend2;it2++) printf("%d ",*it2); } void p3(){ list
                               
                                ::iterator it,iend; iend=IncidentList.end(); CEdge* emptyedge=new CEdge(-1,-1,-1,-1); for(int i=0;i<=numVertex;i++) { vector
                                
                                  vec; for(int j=0;j<=numVertex;j++) { vec.push_back(emptyedge); } adjmatrix.push_back(vec); } for(it=IncidentList.begin();it!=iend;it++){ //CEdge* e = new CEdge((*it)->getTail(),(*it)->getHead(),(*it)->getWeight(),(*it)->getCap()); adjmatrix[(*it)->getTail()][(*it)->getHead()] = *it ; } printf("\n"); printf("project 3:\n"); printf("%d,%d",adjmatrix[2][3]->getTail(),adjmatrix[2][3]->getHead()); } void p4(){ list
                                 
                                  ::iterator it,iend; iend=IncidentList.end(); for(it=IncidentList.begin();it!=iend;it++){ nelist[(*it)->getTail()].push_back(*it); } printf("\n"); printf("project 4:\n"); list
                                  
                                   ::iterator it2,iend2; iend2=nelist[3].end(); for(it2=nelist[3].begin();it2!=iend2;it2++) printf("%d %d\n",(*it2)->getTail(),(*it2)->getHead()); } void Update(int i){ list
                                   
                                    ::iterator it,iend; it=nelist[i].begin(); iend=nelist[i].end(); for(;it!=iend;it++) if((*it)->getWeight()+mapVID_Vertex[i]->d < mapVID_Vertex[(*it)->getHead()]->d){ int d; d=(*it)->getWeight()+mapVID_Vertex[i]->d; //增加新的点，删除旧的点，改动点信息 int k; k = mapVID_Vertex[(*it)->getHead()]->d; //pair
                                    
                                      p((*it)->getHead(),mapBuckets[int(ceil((log((float)k))/(log((float)2))))][(*it)->getHead()]); pair
                                     
                                       p((*it)->getHead(),mapVID_Vertex[(*it)->getHead()]); mapBuckets[int(ceil((log((float)d))/(log((float)2))))].insert(p); mapBuckets[int(ceil((log((float)k))/(log((float)2))))].erase((*it)->getHead()); mapVID_Vertex[(*it)->getHead()]->d = (*it)->getWeight()+mapVID_Vertex[i]->d; mapVID_Vertex[(*it)->getHead()]->p = i; } //printf("update\n"); } int Redistribute(int dmin, int mini) { rbegin[0]=dmin; rend[0]=dmin; rbegin[1]=dmin+1; rend[1]=dmin+1; range[dmin]=0; range[dmin+1]=1; for(int i=2;i<=10;i++) { rbegin[i]=rend[i-1]+1; rend[i]=rend[i-1]+db[i]; for(int j=rbegin[i];j<=rend[i];j++) range[j]=i; } cout<<"middle"<
                                      
                                       second.begin(); for(;itcv!=itBucket->second.end();) { //增加新的点，删除旧的点 cout<<"middle2"<
                                       
                                         p(itcv->first,itcv->second); //mapBuckets[range[mapVID_Vertex[itcv->first]->d]].insert(p); mapBuckets[range[itcv->second->d]].insert(p); cout<<"middle3"<
                                        
                                         first].erase(itcv++); cout<<"middle4"<

::iterator vi,vend; //移动指针到第一个不为空的桶 while(1) { if(itBucket->second.empty()==true) itBucket++; else {itcv=itBucket->second.begin();break;} } if(itBucket->first==0 || itBucket->first==1) { int mini; printf("1 if\n"); mini=itcv->first; mapBuckets[itBucket->first].erase(itcv++); printf("min is %d\n",mini); return mini; } else if(itBucket->second.size()==1) { int mini; printf("2 if\n"); mini=itcv->first; mapBuckets[itBucket->first].erase(itcv++); //printf("min is %d\n",mini); return mini; } else { int dmin=10000; int mini; printf("3 if\n"); itcv=itBucket->second.begin(); cout<

first]->d<

second.end();itcv++) { if(mapVID_Vertex[itcv->first]->d < dmin) {dmin=mapVID_Vertex[itcv->first]->d;mini=itcv->first;} } cout<

second.begin(); return Redistribute(dmin,mini); } } void radix_heap(CGraph &g,int s){ int i,j; init(); for(i=1;i<=10;i++) V.insert(i); for(i=1;i<=N;i++)//所有节点的初始化 { CVertex* vertex=new CVertex(i); pair

p(i,vertex); mapVID_Vertex.insert(p); } for(i=2;i<=N;i++)//除开始点，其他全部放入无穷桶里 { pair

p2(i,mapVID_Vertex[i]); mapBuckets[ceil(log(float(INF))/log(2.0))].insert(p2);//10=log1024,对应无穷桶，方便在删除时操作 } S.insert(s); V.erase(s); mapVID_Vertex[1]->d=0; Update(s); itBucket=mapBuckets.begin(); while (V.size()!=0) { j=FindMin(); S.insert(j); V.erase(j); cout<<"V :"<

<<" "<

9:%d\n",mapVID_Vertex[9]->d); }};

第三部分：

//一些需要用到的头文件#ifndef _COMMON_H_#define _COMMON_H_#include #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#include 
         
          #include 
          
           #include 
           
            #define INF 1024#define N 10#define C 1#endif

转载于:https://www.cnblogs.com/gremount/p/5768012.html

你可能感兴趣的文章