Prims minimum spanning

41 views Asked by At

I am having an issue writing prims algorithm for a graph. The goal is to store the minimum spanning tree that begins a source node, and display the tree once it has been stored. I am using a heap class that I wrote as the priority queue, and I have verified that each method functions as it should. I have also implemented dijkstras algrorithm which I have also verified is working correctly. The issue appears to be somewhere in the while loop of primsMST method. At some point, the value that I am looking for is not in the minheap, and -1 is returned as an index for the search "int index = pq.findValue(vertex.first);". Here is the entire method.

    void Graph::primsMST(std::string source)
{
    // Dummy containers to run dijkstras
    std::map<std::string, std::string> par;    
    std::map<std::string, int> dist;
    // End of dumm containers

    std::map<std::string, std::string> parent;
    std::map<std::string, int> distance;

    for(const auto& val: ajacencyList){
        distance[val.first] = INT_MAX;
        parent[val.first] = "";
    }

    distance[source] = 0;
    Heap pq;

    for(const auto &vertex: ajacencyList){
        pq.minHeapInsert(vertex.first, distance[vertex.first]);
    }

    while(!pq.empty()){
        std::pair<std::string, int> u = pq.extractMinimum();
        
        for(const auto &vertex: ajacencyList[u.first]){
            
            int index = pq.findValue(vertex.first);
            if((index || vertex.first != source) && dijkstra(source, vertex.first, dist, par) < distance[vertex.first]){
                distance[vertex.first] = dijkstra(source, vertex.first, dist, par);
                parent[vertex.first] = u.first;
                pq.minHeapDecreaseKey2(index, distance[vertex.first]);
            }

            // Dummy containers to run dijkstras
            std::map<std::string, std::string> par;    
            std::map<std::string, int> dist;
            // End of dummy containers
        }
    }

    // for(const auto &val: ajacencyList){
    //     std::cout << parent[val.first] <<  " => " << val.first << " Distance: " << distance[val.first];
    //     std::cout << std::endl; 
    // }
}

The dummy containers need to exist for dijkstras because of the way I wrote that method. They are reset after each for loop in the primsMST method. If there are any observations that you have, I would greatly appreciate any help. The ajacency list is represented as follows

std::unordered_map<std::string, std::list<std::pair<std::string, int>>> ajacencyList;
0

There are 0 answers