Modifying an Implementation of Prim's to record weight of shortest path c++

Question

I'm having some trouble getting this implementation of Prim's to track the total weight of the shortest path it finds. The path seems to be correct but I can't figure out where to sum the weights as they are added to the array that stores the paths (since it was written only to store paths used).

I've tried summing pCrawl->weight as each vertex is added to the MST but that seems to be the sum of all the weights on the graph. Same with the values key[].

My question is what can be summed each time a path is added to the MST to reflect the total weight of the MST when all shortest paths have been added.

Here's the code I'm using: http://pastebin.com/TFLGCE0L

The Adjacency List I made: http://pastebin.com/SvgGjEPj

And the map used to create it: Map

The Prim's function looks like this:

// The main function that constructs Minimum Spanning Tree (MST)
// using Prim's algorithm
void PrimMST(struct Graph* graph) 
{
int V = graph->V;// Get the number of vertices in graph
int parent[V];   // Array to store constructed MST
int key[V];      // Key values used to pick minimum weight edge in cut

// minHeap represents set E
struct MinHeap* minHeap = createMinHeap(V);

// Initialize min heap with all vertices. Key value of
// all vertices (except 0th vertex) is initially infinite
for (int v = 1; v < V; ++v)
{
    parent[v] = -1;
    key[v] = INT_MAX;
    minHeap->array[v] = newMinHeapNode(v, key[v]);
    minHeap->pos[v] = v;
}

// Make key value of 0th vertex as 0 so that it
// is extracted first
key[0] = 0;
minHeap->array[0] = newMinHeapNode(0, key[0]);
minHeap->pos[0]   = 0;

// Initially size of min heap is equal to V
minHeap->size = V;

// In the followin loop, min heap contains all nodes
// not yet added to MST.
while (!isEmpty(minHeap))
{
    // Extract the vertex with minimum key value
    struct MinHeapNode* minHeapNode = extractMin(minHeap);
    int u = minHeapNode->v; // Store the extracted vertex number

    // Traverse through all adjacent vertices of u (the extracted
    // vertex) and update their key values
    struct AdjListNode* pCrawl = graph->array[u].head;
    while (pCrawl != NULL)
    {
        int v = pCrawl->dest;

        // If v is not yet included in MST and weight of u-v is
        // less than key value of v, then update key value and
        // parent of v
        if (isInMinHeap(minHeap, v) && pCrawl->weight < key[v])
        {
            key[v] = pCrawl->weight;
            parent[v] = u;
            decreaseKey(minHeap, v, key[v]);
        }
        pCrawl = pCrawl->next;
    }
}

The structs used look like this:

// A structure to represent a node in adjacency list
struct AdjListNode
{
    int dest;
    int weight;
    struct AdjListNode* next;
};

// A structure to represent an adjacency liat
struct AdjList
{
    struct AdjListNode *head;  // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};
// Structure to represent a min heap node
struct MinHeapNode
{
    int  v;
    int key;
};

// Structure to represent a min heap
struct MinHeap
{
    int size;      // Number of heap nodes present currently
    int capacity;  // Capacity of min heap
    int *pos;     // This is needed for decreaseKey()
    struct MinHeapNode **array;
};

I feel like I'm in way over my head in this data structures course, hence trying to use code from the internet to solve this small part of the assignment without fulling understanding :/

Thanks,

Michael

Answer 1

You are doing the right thing. Sum of minimum weights (from Prim's) can be equal to sum of all the weights on the graph. Consider the case when there are 4 nodes in a graph and node 1 is at the center and is connected to nodes 2, 3 and 4 with weights of w. 2, 3 and 4 are not connected among themselves. In this case Prim's weight would come out to be 3*w which is same as total weight. I would suggest you to use few different cases, that would clarify what I'm saying.

Edit:

Here is the issue, you are not updating the sum properly. This -

weightTotal += pCrawl->weight

should be -

weightTotal += pCrawl->weight - key[v]