👀 Views: 205 💬 Answers: 1 📅 Created: 2025-06-09

algorithms cpp prim C++

I need some guidance on I'm prototyping a solution and I'm currently implementing Prim's algorithm to find the Minimum Spanning Tree (MST) of a graph in C++. However, I am encountering unexpected results when the graph contains edges with negative weights. The algorithm seems to be incorrectly including edges that should not be part of the MST. Here's a snippet of my implementation where I maintain a priority queue for edge weights: ```cpp #include <iostream> #include <vector> #include <queue> #include <utility> // for std::pair #include <limits> using namespace std; void primMST(vector<vector<pair<int, int>>>& graph) { int V = graph.size(); vector<int> key(V, numeric_limits<int>::max()); vector<bool> inMST(V, false); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap; key[0] = 0; minHeap.push({0, 0}); // {key, vertex} while (!minHeap.empty()) { int u = minHeap.top().second; minHeap.pop(); inMST[u] = true; for (auto& edge : graph[u]) { int v = edge.first; int weight = edge.second; // Here is where I suspect the problem occurs: if (!inMST[v] && weight < key[v]) { key[v] = weight; minHeap.push({key[v], v}); } } } } int main() { vector<vector<pair<int, int>>> graph = { {{1, 2}, {2, 3}}, {{0, 2}, {2, -1}}, {{0, 3}, {1, -1}} }; primMST(graph); return 0; } ``` When I run the above code with a graph containing negative edges, I find that the algorithm includes edges that seem to violate the properties of MSTs. For instance, if I have an edge from vertex 1 to vertex 2 with a weight of -1, it gets selected over other edges with valid weights. Is there a reason why Prim's algorithm would behave this way with negative weights? I am using GCC version 11.1 on Ubuntu. I've also considered how to handle negative weights properly, but I am unsure if I need to modify the priority queue logic or the key update condition. Any insights on why this might be happening and how to correct it would be greatly appreciated! This is happening in both development and production on Ubuntu 20.04. Any ideas how to fix this? I'm on macOS using the latest version of C++.