Алгоритм Дейкстры (обновление кучи)

Question

Я реализую алгоритм Дейкстры, используя структуру данных кучи. Я также использую массив, который отслеживает "вероятные минимальные расстояния" узлов. Проблема в том, когда я обновляю массив, как обновить соответствующие значения в куче?

хорошо, вот код

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

Чтобы написать DecreaseKey, вам нужна реализация очереди приоритетов для поддержки карты из nodeTags к местам в очереди. Это означает, что нужно обновлять эту карту всякий раз, когда структура данных двоичной кучи требует перестановки, или, возможно, выбирать реализацию на основе указателей, такую ​​как пары кучи, которые никогда не перемещают узлы в памяти.

Если у вас нет большого, несколько плотного графика, DecreaseKey не стоит; просто вставьте узел несколько раз и игнорируйте дублирующиеся результаты из ExtractMin. (Чтобы обнаружить дубликаты: каждый раз, когда я внедрял Dijkstra, мне нужны были либо расстояния, либо дерево. В моих выбранных языках программирования достаточно просто немного отстраниться от любого массива, чтобы запомнить, посещался ли каждый узел.)