c++ - Prim の実装を変更して最短パスの重みを記録する C++

Question

Prim のこの実装で、見つけた最短パスの合計の重みを追跡するのに問題があります。パスは正しいようですが、パスを格納する配列に重みが追加されるため、重みを合計する場所がわかりません (使用されるパスを格納するためだけに書かれているため)。

各頂点が MST に追加されるときに pCrawl->weight を合計しようとしましたが、それはグラフ上のすべての重みの合計のようです。値 key[] と同じです。

私の質問は、すべての最短パスが追加されたときの MST の合計重みを反映するために、パスが MST に追加されるたびに何を合計できるかということです。

私が使用しているコードは次のとおりです。http://pastebin.com/TFLGCE0L

私が作成した隣接リスト: http://pastebin.com/SvgGjEPj

そして、それを作成するために使用された地図:地図

プリムの機能は次のようになります。

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

使用される構造体は次のようになります。

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

私はこのデータ構造コースで頭を悩ませているように感じます。そのため、インターネットのコードを使用して、完全な理解なしに課題のこの小さな部分を解決しようとしています:/

ありがとう、

マイケル