Algorithme de Dijkstra (mise à jour du tas)

Question

Je suis en train d'implémenter l'algorithme de Dijkstra en utilisant une structure de données en tas. J'utilise aussi un tableau qui garde trace des "distances minimales probables" des nœuds. Le problème est quand je suis mise à jour le tableau, comment mettre à jour les valeurs correspondantes dans le tas?

ok voici le code

typedef struct temp      
{ 
    int nodeTag;  
    int weight; 
    struct temp *next; 
}myStruct; //this structure corresponds to the elements of the linked list 

typedef struct temp *link; 

typedef struct 
{ 
    int nodeTag; //each node has an integer nodeTag associated with it 
    link l; 
}head; //the head of the elements of the adjacency list 

typedef struct { 
    head *adjList; 
    int numNodes; 
    int numEdges; 
} Graph; 

typedef struct { 
    int possibleMinWeight; 
    int minFound; //minFound==1 if true min is found 
} dummy; 

dummy *dijkstraSSSP(Graph G, int nodeTag) 
{ 
    minHeap H=createEmptyHeap(G.numNodes); 
    while(i=0;i<G.numNodes;i++) 
    { 
     if(i!=nodeTag)  
      H.A[i].priority=INFINITY; 
     else 
      H.A[i].priority=0; 
     H.A[i].nodeTag=i; 
    } 

    convertIntoHeap(H); 

    int min;  

    dummy *A=(dummy *)malloc(sizeof(int)*G.numNodes); 

    A[nodeTag-1].possibleMinWeight=0; 
    A[nodeTag-1].minFound=1; 

    while(!isEmpty(H)) 
    { 
     element e=findMin(H); H=deleteMin(H); 

     A[e.nodeTag-1].minFound=1;  

     link l=G.adjList[e.nodeTag-1].l;   
     while(l!=NULL) 
     { 
      if(A[l->nodeTag-1].minFound==0); //its true minimum distance is yet to be found 
      {    
       if(A[l->nodeTag-1].possibleMinWeight>A[x-1].possibleMinWeight+(l->weight)) 
        A[l->nodeTag-1].possibleMinWeight=A[x-1]+(l->weight); 
      }     
      l=l->next; 
     } 
    } 
    return A; 
} 

Answer 1

Pour écrire decreaseKey, vous avez besoin de la mise en œuvre file d'attente prioritaire de maintenir une carte de nodeTag s à des emplacements dans la file d'attente. Cela signifie que vous devez mettre à jour cette carte chaque fois que la structure de données binaire-heap appelle un swap ou peut-être choisir une implémentation basée sur un pointeur, comme l'appariement de tas qui ne déplace jamais les nœuds en mémoire.

À moins que vous n'ayez un graphique volumineux et relativement dense, DecreaseKey n'en vaut pas la peine; Il suffit d'insérer un nœud plusieurs fois et d'ignorer les résultats en double d'ExtractMin. (Pour détecter les doublons: chaque fois que j'ai implémenté Dijkstra, j'ai eu besoin des distances ou de l'arbre.) Dans mes langages de programmation, il est assez facile de se débarrasser un peu des deux tableaux pour se souvenir si chaque noeud a été visité