Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Floyd's Algorithm

Posted on 1997-12-16
10
Medium Priority
?
551 Views
Last Modified: 2006-11-17
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,
0
Comment
Question by:fokchi
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 3
  • 2
10 Comments
 
LVL 11

Expert Comment

by:alexo
ID: 1256649
////////////////////////////////////////////////////////////////////////////////

#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
 
LVL 11

Expert Comment

by:alexo
ID: 1256650
Of course, you need to add some error checking.
0
 
LVL 5

Expert Comment

by:julio011597
ID: 1256651
Where's Floyd gone?
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 11

Expert Comment

by:alexo
ID: 1256652
Between the two display() function calls.  I know you need a microscope to spot it, but that's it.
0
 
LVL 5

Expert Comment

by:julio011597
ID: 1256653
Right, thanks.
0
 

Author Comment

by:fokchi
ID: 1256654
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
 
LVL 11

Accepted Solution

by:
alexo earned 3040 total points
ID: 1256655
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
 

Author Comment

by:fokchi
ID: 1256656
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
 
LVL 5

Expert Comment

by:julio011597
ID: 1256657
To only add a comment, you don't need to reject the answer; just don't check any grading box.
0
 
LVL 11

Expert Comment

by:alexo
ID: 1256658
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

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

618 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question