Minimum Spanning Trees Breaking the Norm

It is common for engineers to follow the trend, often overlooking the potential of re-creating solutions. I have a unique approach to a Minimum Spanning Tree (MST) problem using principles inspired by Dijkstra’s algorithm. By stepping away from conventional practices and exploring creative adaptations, we can unlock new pathways for innovation.

The core idea behind my approach is reminiscent of Dijkstra's algorithm. I maintain a check on all nodes in the graph to ensure that we select the edge that provides the minimum weight for each specific node. This strategy allows us to build the Minimum Spanning Tree (MST) incrementally by always considering the lightest edge connected to any node.

Here’s how it works:

1. Node Connection: At each step, I focus on adding a single edge that connects a new node to the growing MST. By selecting the edge with the minimum weight for that node, we effectively ensure that each addition contributes to minimizing the overall tree weight.
2. Edge Count: This process continues until we have added n−1 edges, where n is the total number of nodes in the graph. Since each node must connect to at least one other node(considering it doesn't have an unconnected component) to be included in the tree, we can be confident that all nodes will eventually be connected. As we select the lightest edge for each node, there will never be a scenario where a node is left unconnected; every node reaches another through some edge and we take the minimum one.
3. Limitations: It’s important to note that this approach does not handle negative cycles. Since we rely on the assumption of non-negative edge weights, any negative cycle could disrupt the tree structure and lead to incorrect results.

 int spanningTree(int V, vector<vector<int>> adj[])
    {
        vector<int> weight(V,INT_MAX);
        vector<vector<int>> mat(V,vector<int>(V,-1));
        for(int i=0;i<V;i++){
            for(auto it: adj[i]){
                mat[i][it[0]]=it[1];
            }
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
        q.push({0,0});
        weight[0]=0;
        int ans=0;
        while(!q.empty()){
            int node=q.top().second;
            int dis=q.top().first;
            q.pop();
            for(int i=0;i<V;i++){
                int wei=mat[node][i];
                if(weight[i]>wei && wei!=-1){
                    q.push({wei,i});
                    if(weight[i]!=INT_MAX){
                        ans-=weight[i];
                    }
                    weight[i]=wei;
                    ans+=wei;
                    //this statement ensures that we don't add the bidirectional edge
                    mat[i][node]=-1;
                }
            }
        }
        return ans;
    }

I welcome any thoughts on its correctness and potential edge cases that might challenge its validity. Let's discuss how we can further refine this solution and explore scenarios where it may or may not hold up. Your insights and critiques are invaluable in this journey of exploration!