1

For a school project I have to modify a Dijkstra short path code given by the professor and change the priority queue from a simple array to an heap. The idea is clear but I can't understand what I should include in the heap nodes because in the code I have there are 3 different arrays, one for the distance between two nodes, one with the predecessors of the nodes and one boolean that says if I have yet visited the node. 

int *Dijkstra(int s, int n) //restituisce array dei predecessori
{
    //S nodi gia' visitati, Q nodi ancora da visitare
    int u, v, nVisited;
    int *d, *p; //array, distanze e pred dei nodi
    bool *Q; //coda di priorita' con array
    Vertex *vnext;
    d = (int*)malloc(n* sizeof(int));
    p = (int*)malloc(n* sizeof(int));
    Q = (bool*)malloc(n* sizeof(bool));
    for (v = 0; v<n; v++)
    {
        d[v] = INT_MAX;
        p[v] = -1;
        Q[v] = true;
    }
    d[s] = 0;
    p[s] = s;
    nVisited = 0;
    while (nVisited < n)
    {
        u = extractMin(Q, d, n);
        nVisited++;
        Q[u] = false; //non e' più da visitare
        vnext = Adj[u];
        while (vnext!= NULL)
        {
            v = vnext->id;
            if ((d[v] > d[u] + vnext->dist))
            {
                d[v] = d[u] + vnext->dist;
                p[v] = u;
            }
            vnext = vnext->next;
        }
    }
    return p;
}

Where Vertex is:

typedef struct _Vertex
{
    int id;
    int dist;
    struct _Vertex* next;
} Vertex;
Vertex** Adj;

The Adj array is initialized through a readfile that properly create it.

My idea of heap was this: 

typedef struct node {
    //What should I put here?
    //I thought about int distance, predecessors;
} node ;

typedef struct minHeap {
    int size ;
    node *elem ;
} minHeap ;
SnpShot
  • 13
  • 3
  • 1
    Welcome to Stack Overflow! [Please see this discussion on why not to cast the return value of `malloc()` and family in `C`.](http://stackoverflow.com/q/605845/2173917). – Sourav Ghosh May 19 '16 at 11:48
  • for ease of readability and understanding: 1) separate code blocks (for, if, else, while, do...while, switch, case, default) via a blank line. 2) follow the axiom: *only one statement per line and (at most) one variable declaration per statement.* 3) variable names should indicate content or usage (or better, both). – user3629249 May 20 '16 at 06:00
  • strongly suggest separating the struct definition(s) from the `typedef` statements. – user3629249 May 20 '16 at 06:01
  • when calling any of the memory allocation functions: (malloc, calloc, realloc), always check (!=NULL) the returned value to assure the operation was successful. – user3629249 May 20 '16 at 06:02

0 Answers0