Dijkstra算法,最小优先队列用堆(Heap)实现 伪代码描述 void dijkstra() { Q=V; S={}; // 空集 while(Q!={}) { v = ExtractMin(Q); S = S + {v}; Q = Q - {v}; for all edge(v,u), relax the edge; // if(d[v] + dis[v][u] < d[u]) d[u] = d[v] + dis[v][u]; } }
1![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//* 2 最基本的二叉堆是实现不了的,因为dijkstra要求在运行过程中随时修改堆内元素,因此要用扩展版的、引入了外部指针的二叉堆 3 另外,当图用邻接表来表示的时候,用二叉堆的时间复杂度为O(ElgV),不用二叉堆的复杂的是O(V^2);不用邻接表的时候,用二叉 4 堆时间复杂度为O(V^2lgV),不用二叉堆的时间复杂度为O(V^2)。也就是说,只有当使用邻接表来表示稀疏图的时候,使用二叉堆才 5 有效率优势。因此本程序使用邻接表来表示图 6 */ 7 #include <stdio.h> 8 #include <iostream> 9 #define INF 0xfffffff 10 #define MAXN 100 11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 12 using namespace std; 13![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 14 int deg[MAXN]; // 节点i的度 15 int list[MAXN][MAXN][2]; // list[i][j][1]:节点i第j个邻接节点在list中的下标,list[i][j][2]表示它们之间的距离 16 int heap[MAXN]; // 堆,heap[i]存储的是节点的编号 17 int key[MAXN]; // 堆中元素的值,算法结束时为各点到源s的最短路的值 18 int pos[MAXN]; // pos[i]表示第i个节点在堆中的位置 19 int count; // 未找到最短路径的节点数目,也是堆的大小 20 bool exist[MAXN]; // 标识节点i是否还未找到最短路 21 int n; // 结点数 22 int trace[MAXN]; // 存放最短路的路径 23 // 交换两个整数 24 void swap(int &a,int &b) 25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 26 int tmp=a; 27 a=b; 28 b=tmp; 29 } 30 // 向下调整 31 void siftdown(int index) 32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 33 pos[heap[count]]=pos[heap[index]]; 34 heap[index]=heap[count]; 35 int i=index,j; 36 while(2*i<=count) 37![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 38 j=2*i; 39 if(key[heap[j+1]]<key[heap[j]] && j+1<=count) j++; 40 if(key[heap[j]]>=key[heap[i]]) break; 41 swap(pos[heap[i]],pos[heap[j]]); 42 swap(heap[i],heap[j]); 43 i=j; 44 } 45 } 46 // 向上调整 47 void siftup(int index) 48![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 49 int i=index; 50 while(i>1 && key[heap[i]]<key[heap[i/2]]) 51![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 52 swap(pos[heap[i]],pos[heap[i/2]]); 53 swap(heap[i],heap[i/2]); 54 i/=2; 55 } 56 } 57 // 找到当前离source最近的点,返回它的编号 58 int extract() 59![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 60 int tmp=heap[1]; 61 if(count>1) siftdown(1); 62 return tmp; 63 } 64 // 修改编号为id的结点在堆中的值,并调整堆 65 void relax(int u) 66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {// 若d[u]+dis[u][v]<d[v],则修改d[v]为d[u]+dis[u][v];u为刚从堆中弹出的点,有向边(u,v) 67 for(int i=0;i<deg[u];i++) 68![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 69 if(exist[list[u][i][0]] == true && key[u]+list[u][i][1]<key[list[u][i][0]]) 70![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 71 key[list[u][i][0]]=key[u]+list[u][i][1]; 72 trace[list[u][i][0]]=u; 73 int p=pos[list[u][i][0]]; 74 siftup(p); 75 } 76 } 77 } 78![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 79 void dijkstra() 80![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 81 int i,j,k; 82 for(i=1;i<=n;i++) 83![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 84 heap[i]=i; 85 exist[i]=true; 86 pos[i]=i; // 源为1 87 key[i]=INF; 88 } 89 // 初始时堆Q中存放所有的节点 90 count=n; 91 key[1]=0; 92 while(count>0) 93![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 94 int id=extract(); // 当前距离节点1最近的点提出来并修改所有与它邻接的点 95 count--; 96 exist[id]=false; 97 relax(id); 98 } 99 return; 100 } 101![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 102 int main() 103![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 104 freopen("test.txt","r",stdin); 105 scanf("%d",&n); 106 count=n; 107 for(int i=1;i<=n;i++) 108![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 109 scanf("%d",°[i]); 110 for(int j=0;j<deg[i];j++) 111![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 112 scanf("%d%d",&list[i][j][0],&list[i][j][1]); 113 } 114 } 115 dijkstra(); 116 for(i=1;i<=n;i++) printf("node %d precessor %d length %d\n",i,trace[i],key[i]); 117 return 1; 118 }
|