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;