Dijkstra算法（更新堆）

我正在使用堆数据结构实现Dijkstra算法。我还使用一个数组来跟踪节点的“可能的最小距离”。问题是当我更新数组时，如何更新堆中对应的值？Dijkstra算法（更新堆）

确定这里是代码

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

来源

2013-05-29 user1780800

我认为你需要向我们展示一些代码。 – Jack

有人可能请格式化此代码吗？我不知道应该格式化C代码，否则我会自己做，但是我不能正确阅读它。 –

我不知道还有什么办法.. – user1780800

要写入DecreaseKey，你需要的优先级队列实现，以维持nodeTag个地图，在队列中的位置。这意味着无论何时二进制堆数据结构要求交换或者可能选择基于指针的实现（如配对堆从不在内存中移动节点），都需要更新此映射。

除非你有一个大的，有点密集的图形，否则DecreaseKey是不值得的;只需多次插入节点并忽略ExtractMin的重复结果。（为了检测重复：每次实现Dijkstra时，我都需要距离或树，在我选择的编程语言中，很容易从两个阵列中晃动一点，以记忆每个节点是否已访问过）

来源

2013-05-29 20:59:22

谢谢！这是非常有用的信息 – user1780800

Dijkstra算法（更新堆）

回答

相关问题