You are not logged in. Please login at www.codechef.com to post your questions!

×

Floyd-Warshall Algorithm doubt!

So I know that the algo is -

for (int k = 0; k < n; k ++){
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            adj[i][j] = min(adj[i][j],adj[i][k]+adj[k][j]);
        }
    }
}

I wanted to ask that why does it become wrong when we change it to -

for (int i = 0; i < n; i ++){
    for (int j = 0; j < n; j++){
        for (int k = 0; k < n; k++){
            adj[i][j] = min(adj[i][j],adj[i][k]+adj[k][j]);
        }
    }
}

asked 23 Dec '16, 21:36

mathecodician's gravatar image

6★mathecodician
2.6k11034
accept rate: 7%


Since smaller sub-problems need to be solved first and the sub-problems size is controlled by k so we should always put k in the outermost for loop (As k governs which vertices you are permitted to use internal to your path from source i to destination j). The order of i and j are irrelevant but k must go first as it controls the size of the sub-problems.

This may help : http://stackoverflow.com/questions/27700629/why-does-order-of-3-loops-in-floyd-warshall-matters

Or may be this one : http://cs.stackexchange.com/questions/9636/why-doesnt-the-floyd-warshall-algorithm-work-if-i-put-k-in-the-innermost-loop

EDIT: I found similar question on CodeChef here : https://discuss.codechef.com/questions/5583/floyd-warshall-algorithm

link

answered 23 Dec '16, 21:56

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

edited 24 Dec '16, 18:29

(24 Dec '16, 19:20) mathecodician6★
link

answered 23 Dec '16, 21:41

emin3m's gravatar image

2★emin3m
629
accept rate: 3%

@emim3m that was a nice link

(23 Dec '16, 23:04) mathecodician6★

The correct code is adj[j][k] = min(adj[j][k],adj[j][i]+adj[i][k]);

link

answered 23 Dec '16, 21:39

coder_voder's gravatar image

2★coder_voder
593332
accept rate: 8%

edited 23 Dec '16, 21:40

i know that this is the correct code but i want to ask that why does the second one give WA

(23 Dec '16, 21:41) mathecodician6★

Because in the second code you changed the loop variables position

(23 Dec '16, 21:41) coder_voder2★

btw @coder_voder from where are you learning graphs?

(23 Dec '16, 21:48) mathecodician6★

Actually my INOI Preparation is not going well. Btw i was seeing Tushar Roy's Videos and some tutorials from GeeksForGeeks and from where you are learning this?

(23 Dec '16, 22:04) coder_voder2★

geeksforgeeks and commonlounge

(23 Dec '16, 22:30) mathecodician6★

Which topics have you prepared till now?

(23 Dec '16, 22:39) coder_voder2★

There's practice in dp and shortest paths and DAGs left

(23 Dec '16, 22:56) mathecodician6★

Are you comfortable with Stacks, Queues, Greedy Algorithms, Data Structures etc.

(23 Dec '16, 23:06) coder_voder2★

Yes pretty comfortable

(23 Dec '16, 23:08) mathecodician6★
showing 5 of 9 show all

That would change the order in which the subproblems are solved in the DP

it would try to take values from data which has not been computed yet(it would try to solve bigger subproblems before the smaller ones)...

as a result giving garbage values(or infinity, i.e distance between 2 non connected vertices).

link

answered 23 Dec '16, 22:35

tanmay_sachan's gravatar image

1★tanmay_sachan
424
accept rate: 9%

edited 23 Dec '16, 22:36

(23 Dec '16, 23:04) mathecodician6★
-2

#include<stdio.h>

include<stdlib.h>

int arr[10][10],d[10][10],p[10][10];

void floyed(int c[][10],int n) { int i,j,k,q; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { d[i][j]=arr[i][j];
p[i][j]=-1; } } for(i=1;i<=n;i++) { for(i=1;i<=n;i++) { d[i][i]=0; p[i][i]=-1; } } for(k=1;k<=n;k++) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) {

            if(d[i][k]+d[k][j]<d[i][j] && i!=j)
            {
                d[i][j]=d[i][k]+d[k][j];
                p[i][j]=p[k][j];
            }
        }
    }
    printf("\n D matrix:\n");
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            printf("\t%d",d[i][j]);
        }
        printf("\n");
    }
}

}

int main() { int n,i,j,k; FILE *fp; printf("\n Enter no. of vertices:"); scanf("%d",&n); fp=fopen("floyed.txt","r"); if(fp==NULL) exit(0); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) fscanf(fp,"%d",&arr[i][j]); } floyed(arr,n); }

link

answered 23 Dec '16, 23:05

sweetnandy's gravatar image

0★sweetnandy
-1
accept rate: 0%

2

@sweetnandy He didn't ask for Floyd-Warshall algorithm! Please read the question carefully. :)

(23 Dec '16, 23:23) nikhil_chandak5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×374
×65

question asked: 23 Dec '16, 21:36

question was seen: 867 times

last updated: 24 Dec '16, 19:20