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算法（更新堆）

回答

相關問題