CODEWITHSUNDEEP
c++algorithmgraphaverage
user2057191
user2057191

Reputation: 17

Average Optimal Path of a graph

I need to find the average optimal path of a graph. I decided to use Floyd-Warhsall's algorithm to attain all possible optimal lengths, but all of the entries get written over with zeros. Any ideas on how to fix this?

Original Matrix:

0 0 0 0 1 0
0 0 1 0 4 0
0 1 0 0 0 2
0 0 0 0 0 1
1 4 0 0 0 2
0 0 2 1 2 0

Averaging code:

double average = 0;
vector<vector<double> > p;
p = matrix;

for(int k = 0; k < vertices; k++)
{
    for(int i = 0; i < vertices; i++)
    {
        for(int j = 0; j < vertices; j++)
        {
            if((p[i][k] + p[k][j] < p [i][j]))
            {
                p[i][j] = p[i][k]+p[k][j];
            }
        }
    }
}

double sum = 0;

for(int i = 0;i < vertices; i++)
{
    for(int j = 0; j < vertices; j++)
    {
        sum += p[i][j]; //adds up all entries
    }
}

double fact = 0;
for(int i = 1; i < vertices; i++)
{
    fact += i;
}
average = sum/fact;

return average;

Upvotes: 1

Views: 221

Answers (1)

000
000

Reputation: 27237

Well, the output of all zeros is correct.

The wikipedia article says your matrix should be initialized like this:

 0  inf inf inf  1  inf
inf  0   1  inf  4  inf
inf  1   0  inf inf  2
inf inf inf  0  inf  1
 1   4  inf inf  0   2
inf inf  2   1   2   0

So in your initialization step, just set them to INT_MAX.

You're getting zero because that of course is the trivial solution when the weights between nodes is zero!

Edit: actually, INT_MAX is a bad choice because you're going to be adding two of them together. That's an overflow. Set them to INT_MAX/2 to be safe, I guess. Unless you plan on having weights greater than INT_MAX/2.

#include <cfloat>

for(int i = 0;i < vertices; i++)
{
    p[i][i] = 0; // diagonal should be initialized to zero.
    for(int j = 0; j < vertices; j++)
    {
        if ( i != j && p[i][j]==0)
        {
            p[i][j] = DBL_MAX / 2.0; // As close to infinity as we'll get
        }
    }
}

Upvotes: 1

Related Questions