Code Floyd's algorithm for shortest path


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 5 of 5

Thread: Code Floyd's algorithm for shortest path

  1. #1
    Join Date
    Jan 2007
    Posts
    2

    Question Code Floyd's algorithm for shortest path

    Hi . I need to code Floyd’s Algorithm that prints the optimal (shortest path) length between any 2 given vertices using c++ language .

    Here's the algorithm that i want to code it :confused:
    void floyd (int n , const number w[],number D[][],index P[][])
    {
    index i, j,k;
    for(i=1;i<=n;i++)
    for(j=1; j<=n;j++)
    p[i][j]=0;
    D=W;
    for(k=1;k<=n;ki++)
    for(i=1; i<=n;i++)
    for(j=1; j<=n;j++)
    if (D[i][k]+D[k][j]<D[i][j]){
    p[i][j]=k;
    D[i][j]=D[i][k]+ D[k][j];
    }
    }

  2. #2
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819
    I think it miss 'print' and 'stop' , anyway where u have stoped , and what u can't continue ? , u just need to put a proper variable name , int, long , and so on .. and recognize the interface with the main function and calling this function ...
    send us what u have tried and where u have stoped .
    Programmer&Cracker CS
    MyBlog:Blog.Amahdy.com
    MyWebsite:www.Amahdy.com

  3. #3
    Join Date
    Dec 2003
    Posts
    3,366
    its pretty close already.

    you need to put types on these:
    number types are int, float, double in c++

    void floyd (int n , int *w, int **D, int **P)
    {

    int i, j,k;
    for(i=1;i<=n;i++)
    for(j=1; j<=n;j++)
    p[i][j]=0;

    D=W; //this statement is no good. You need to copy in a loop or use memcpy to move the elements over. Since the dimensions are different, I am not sure what you wanted, but it would just be another loop like the ones you have here.


    for(k=1;k<=n;ki++)
    for(i=1; i<=n;i++)
    for(j=1; j<=n;j++)
    if (D[i][k]+D[k][j]<D[i][j]){
    p[i][j]=k;
    D[i][j]=D[i][k]+ D[k][j];
    }
    }

  4. #4
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819
    Execuse me jonnin I don't meen anything at all,, just if he was asking about c++ implementation , and u try helping him by giving him the total code [not like I made to let him give a try] u think he will make the for loop and memcopy ? also (question for me) why u have changed to pointers and make life complex , it's the same with arrays as mentioned in the algorithm ,
    and hence he will use w directly without d ...
    I hope that u understand what I meen my friend , thank u.
    Programmer&Cracker CS
    MyBlog:Blog.Amahdy.com
    MyWebsite:www.Amahdy.com

  5. #5
    Join Date
    Dec 2003
    Posts
    3,366
    He already had the total code except for minor syntax changes from whatever that was to c++. The compiler would have told him most of what I did.

    It does not matter what is in the header, the array dereference and pointer dereference are the same, and it removed many excess chars (extra long header) so I shortened [] to * multiple times for a shorter header. No extra complexity here, its not dynamic memory or "pointers" you see?

    also you can pass
    void foo(int *p)
    an array as follows
    int x[100];
    foo(x); //this is fine....

    given what he wrote, I think he can make the assignment loop for w and d, if not he can ask again. Its just more of the same.

    Memcpy / memset are frowned upon these days because of objects, but to remove a double for loop and replace it with an operation that maps one to one on intel processor's assembly language (or closely, there are some sweet memory movement ops on the x86's) it makes sense to use it sometimes.

Similar Threads

  1. Replies: 5
    Last Post: 12-26-2008, 09:43 PM
  2. Replies: 2
    Last Post: 04-02-2007, 01:06 PM
  3. Replies: 60
    Last Post: 09-13-2002, 06:41 PM
  4. Brain Washing
    By Danny Bowman in forum .NET
    Replies: 152
    Last Post: 09-13-2001, 08:23 AM
  5. Replies: 0
    Last Post: 04-03-2001, 05:32 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center