Dijkstra avec un tas. Comment mettre à jour le tas après la relaxation?

J’essaie d’implémenter l’algorithme de 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 

Alors, dans la relaxation, comment puis-je mettre à jour le tas, afin qu’il ait le bon ordre? Je n’ai pas l’index du tas pour ce noeud dans cette étape. Cela signifie-t-il que je dois créer un nouveau tableau tel que nodes[edge] = heapIndex , afin de pouvoir obtenir un index de nodes[edge] = heapIndex pour ce nœud? Mais cela semble très inefficace car je dois ensuite mettre à jour les fonctions insert_to_heap , remove_minimum .

Le code C ou JAVA est correct.

Cela signifie-t-il que je dois créer un nouveau tableau tel que nodes [edge] = heapIndex, afin de pouvoir obtenir un index de segment de mémoire pour ce nœud?

Oui.

Mais cela semble très inefficace car je dois ensuite mettre à jour les fonctions insert_to_heap, remove_minimum.

Les mises à jour de tableaux sont très peu coûteuses, en théorie comme en pratique, et vous ne devez effectuer que quelques-unes de ces opérations par tas, ce qui n’a rien d’inefficace. En outre, l’utilisation de la mémoire d’un tel tableau est très économique par rapport au coût de stockage d’une structure de données graphique.

 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? 

Je ne fais pas ce que signifie exactement le noeud [bord]. À mon avis, il devrait s’agir d’une Map (un tableau en effet) f qui f [nœud] = HeapIndex (Il donne l’index de ce nœud dans Heap). Le stockage du nœud [edge] n’est pas efficace.

Alors comment implémenter le MapHeap? J’ai implémenté un MapHeap efficace, mais pas tellement dans le code:

 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; } };