• C

Floyd's Algorithm

Hi, I am studing Floyd's Algorithm and I want to implement it by using C.  However, somehow, I just get stuck in there. I want to use that program to read a list of data from stdin and then write a matrix which shows each of the shorest path.
i.e. If I have the input,
A      B 24 F 28
B      A 24 C 11
C      B 11 D 13
D      C 13 E 20 F 12
E      D 20 F 15
F      A 28 D 12 E 15

I want to have :
      A      B      C      D      E      F
A      0      24      35      40      43      28
B      24      0      11      24      44      36      
C      35      11      0      13      33      25      
D      40      24      13      0      20      12      
E      43      44      33      20      0      15      
F      28      36      25      12      15      0

as the output.

here is the algorithm I am going to use, but I never know how to bring them together.

NODE u,v,w;

for(v=0;v<MAX;v++)
      for(w=0;w<MAX;w++)
            dist[v][w]=arc[v][w];
for(u=0;u<MAX;u++)
      for(v=0;v<MAX;v++)
            for(w=0;w<MAX;w++)
            if (dist[v][u]+dist[u][w] <dist[v][w])
            dist[v][w]=dist[v][u]+dist[u][w];

If have did that problem before, or know to how implement it , just let me know.

thanks,
fokchiAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

 
alexoCommented:
////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE    6
#define NO_PATH 99999

void display(float dist[SIZE][SIZE]);

////////////////////////////////////////////////////////////////////////////////

void main()
{
    float   dist[SIZE][SIZE];
    char    buff[256];
    int     i, j, k;

    for (i = 0; i < SIZE; ++i)
        for (j = 0; j < SIZE; ++j)
            dist[i][j] = (i == j) ? 0 : NO_PATH;

    while (gets(buff) && strlen(buff) > 2)
    {
        char*   p;

        i = toupper(*buff) - 'A';

        for (p = buff + 1; *p; ++p)
        {
            if (*p == ' ')
                continue;

            j = toupper(*p) - 'A';
            p += 2;

            dist[i][j] = dist[j][i] = atof(p);

            while (*p > ' ')
                ++p;
        }
    }


    display(dist);

    for (i = 0; i < SIZE; ++i)
        for (j = 0; j < SIZE; ++j)
            for (k = 0; k < SIZE; ++k)
            {
                float n = dist[j][i] + dist[i][k];
                if (dist[j][k] > n)
                dist[j][k] = n;
            }

    display(dist);
}

////////////////////////////////////////////////////////////////////////////////

void display(float dist[SIZE][SIZE])
{
    int     i, j;

    for (i = 0; i < SIZE; ++i)
    {
        for (j = 0; j < SIZE; ++j)
        {
            float n = dist[i][j];

            if (n == NO_PATH)
                printf(" --- ");
            else
                printf("%4.0f ", dist[i][j]);
        }

        putchar('\n');
    }

    putchar('\n');
}

////////////////////////////////////////////////////////////////////////////////

0
 
alexoCommented:
Of course, you need to add some error checking.
0
 
julio011597Commented:
Where's Floyd gone?
0
Get Certified for a Job in Cybersecurity

Want an exciting career in an emerging field? Earn your MS in Cybersecurity and get certified in ethical hacking or computer forensic investigation. WGU’s MSCSIA degree program was designed to meet the most recent U.S. Department of Homeland Security (DHS) and NSA guidelines.  

 
alexoCommented:
Between the two display() function calls.  I know you need a microscope to spot it, but that's it.
0
 
julio011597Commented:
Right, thanks.
0
 
fokchiAuthor Commented:
Thanks alexo,

I tried your codes. It works! But, how can I read in a flexible size of matrix. Now, if I input a different size of matrix, it won't work. I want to know how do I have the program to masure the the size of that input matrix and preform the "Floyd's Algorithm"? Just let me know if you know how to do it. Again, thanks for you help!

0
 
alexoCommented:
If the program is ok, why did you reject the answer?  It is customary to grade it according to it's merit.

for flexible size, change it as follows:

1) #define MAX_SIZE 100

2) Change the definition of dist to be of maximum size.

3) Input the desired size into a variable.

4) Change all the loop limits to the varible.

5) The display() function needs some work:

void display(float* pItem, int size)
{
  int i, j;

  for (i = 0; i < size; ++i)
  {
    for (j = 0; j < size; ++j)
      {
        float n = dist[i * size + j];
        /* or maybe [j * size + i], don't remember... */

        if (n == NO_PATH)
          printf(" --- ");
        else
          printf("%4.0f ", dist[i * size + j]);
          /* or maybe [j * size + i], don't remember... */
      }

    putchar('\n');
  }

  putchar('\n');
}

6) The call to display() becomes:

  display(&(dist[0][0]), size);

Note: I didn't check this code.  Minor bugs may exist.

0

Experts Exchange Solution brought to you by ConnectWise

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
 
fokchiAuthor Commented:
I am sorry to reopen you answer. It is because I afraid that you may not see my later comments after I grade it. Anyway, I will the way you told me. Thanks,
0
 
julio011597Commented:
To only add a comment, you don't need to reject the answer; just don't check any grading box.
0
 
alexoCommented:
fokchi, two things:

First, as julio mentioned, you can add comments to an answer without grading or rejecting it.  That way you can ask for clarifications and later decide if the answer (plus later comments) is good enough for you.  But I see you got it.

Second, you and the person who answers your question can continue adding comments without expenting any points even after the question is graded.

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.