What is the logical error in my implementation of Prim's algorithm for minimum spanning tree?

Question

#define ll long long
ll prims(int n)
{
     ll ans;
    vector<bool> used (n); 

    #define INF 1000000000000LL


    vector<ll> min_e (n, INF), sel_e (n, -1);

     min_e[0]=-1*INF;

     ll dis=1;
    for(int i=0;i<n;i++)
    {
        int v=-1;
        for(int j=0;j<n;j++)
        {
             if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
            v = j;
        }
        used[v] = true;
        if(sel_e[v]!=-1)
        cout << v << " " << sel_e[v] << endl;

    for (int to=0; to<n; ++to)
        if (g[v][to] < min_e[to]) {
            min_e[to] = g[v][to];
            sel_e[to] = v;
        }

    }
     for(int i=0;i<n;i++) cout<<i<<" "<<sel_e[i]<<" "<<g[i][sel_e[i]]<<endl;


    return dis;
}

I am trying to apply Prim's algorithm for a dense undirected graph for negative edge weights but I am unable to understand why it is producing wrong outputs for nearly all cases. I am using an adjacency matrix g[N][N] for storing the edges.

Actually the output for my current code is a minimum spanning tree with cycles. Why is the cycle checking mechanism not working?

pow() isn't guaranteed to return exact powers for integer inputs. That's one. — Alexey Frunze
– Alexey Frunze, Commented Apr 9, 2013 at 19:02
@AlexeyFrunze:I have corrected it.Still no improvement in the result, — user1907531
– user1907531, Commented Apr 9, 2013 at 19:04
Please never ever use a #define instead of a typedef. — Zeta
– Zeta, Commented Apr 9, 2013 at 19:19
It could be min_e[0]=-1*INF if you later add min_e, or the fact that sel_e[0] = -1, so you can't query g[0][sel_e[0]]. — abeln
– abeln, Commented Apr 9, 2013 at 19:26

abeln · Accepted Answer · 2013-04-09 19:39:11Z

1

Actually, the problem is here:

for (int to=0; to<n; ++to)
    if (g[v][to] < min_e[to]) {
        min_e[to] = g[v][to];
        sel_e[to] = v;
    }
}

You should only update sel_e and min_e if to hasn't been visited yet.

Otherwise, consider this case:

0 -- 1 -- 2

where w({0, 1}) = 10, and w({1, 2} = 1). You would set sel_e[1] = 2, even though you need sel_e[1] = 0.

answered Apr 9, 2013 at 19:39

abeln

3,7672 gold badges24 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

What is the logical error in my implementation of Prim's algorithm for minimum spanning tree?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related