Dijkstra有一堆。 放松后如何更新堆?

我正在尝试实现Dijkstra算法。

foreach distance d d = INFINITY d[source] = 0 create_heap_based_on_Distances(); while(true) bestedge = heap[0] remove_minimum_from_heap //it will be heap[0] foreach adjacency of bestedge if (weight + bestedge_distance < current_distance) { current_distance = weight + bestedge_distance // Now I have to update heap, how can I do that? } if (heap_empty) break 

所以,在放松的过程中,我如何更新堆,以便它具有正确的顺序? 我在该步骤中没有该节点的堆索引。 这是否意味着我必须创建一个新的数组,如nodes[edge] = heapIndex ,所以我可以得到该节点的堆索引? 但是因为我需要更新insert_to_heapremove_minimum函数, remove_minimum效率似乎非常低。

C或JAVA代码没问题。

这是否意味着我必须创建一个新的数组,如nodes [edge] = heapIndex,所以我可以得到该节点的堆索引?

是。

但是因为我需要更新insert_to_heap,remove_minimum函数,所以效率似乎非常低。

无论是在理论上还是在实践中,数组更新都非常便宜,而且每个堆操作只需执行一些,因此这根本不是低效的。 而且,与图形数据结构的存储成本相比,这种arrays的存储器使用非常便宜。

 Does that mean I have to create a new array like nodes[edge] = heapIndex, so I could get a heap's index for that node? 

我不知道节点[edge]的确切含义。 在我看来,它应该是一个Map(一个数组确实)f f [node] = HeapIndex(它给出了Heap中该节点的索引)。 存储节点[edge]效率不高。

那么如何实现MapHeap? 我已经实现了一个有效的MapHeap,但在代码中没有那么多注释:

 template struct MapHeap { DT f[HEAP_SIZE+5];//store the distance int mp1[HEAP_SIZE+5];//val -> index // I assume the val is unique. // In the dijk, the val is the nodeId,so it must be unique. // mp1[nodeId] gives the index of that node in my heap int mp2[HEAP_SIZE+5];//index -> val int nv;// number of node in my heap now MapHeap():nv(0) { memset(mp1,-1,sizeof(mp1)); memset(mp2,-1,sizeof(mp2)); } void print(int n) { for(int i=1;i<=n;i++) printf("%d ",f[i]); puts(""); for(int i=1;i<=n;i++) printf("%d ",mp1[i]); puts(""); for(int i=1;i<=n;i++) printf("%d ",mp2[i]); puts(""); } void print(){print(nv);} bool resize(int n) { if (nv<0||nv>HEAP_SIZE) return 0; for(int i=n+1;i<=nv;i++) { mp1[mp2[i]]=-1; mp2[i]=-1; } nv=n; return 1; } DT top()//get the smallest element { if (nv<1) return DT(-1); return f[1]; } DT get(int idx) { if (idx<1||idx>nv) return DT(-1); return f[idx]; } // it's for unpdating the heap. It should be pravite method. // Because I write this code for competition, so I just ignore the accsee controling void movedown(int now,int val,const DT &x)//this node is larger than son { for(;now*2<=nv;) { int a=now*2; int b=now*2+1; if (b<=nv&&f[b]=x) break; f[now]=f[a]; mp1[mp2[a]]=now; mp2[now]=mp2[a]; now=a; } f[now]=x; mp1[val]=now; mp2[now]=val; } void moveup(int now,int val,const DT &x)//this node is smaller than father { for(;now>1;now>>=1) { int par=now>>1; if (f[par]<=x) break; f[now]=f[par]; mp1[mp2[par]]=now; mp2[now]=mp2[par]; } f[now]=x; mp1[val]=now; mp2[now]=val; } bool pop(int idx=1)//pop a element, pop the smallest element by default { if (idx<1||idx>nv) return 0; DT &x=f[nv]; int v1=mp2[nv]; int v2=mp2[idx]; mp1[v1]=idx; mp2[idx]=v1; mp1[v2]=-1; mp2[nv]=-1; nv--; if (idx!=nv+1) movedown(idx,v1,x); x=0; return 1; } bool push(const DT &x,int val)//push a node, and with the value of val(in dijk, the val is the nodeId of that node) { int now=++nv; if (now>HEAP_SIZE) return 0; moveup(now,val,x); return 1; } };