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]);
        }
    }
}
1 Like

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

Similar discussion : https://www.quora.com/Why-is-the-order-of-the-loops-in-Floyd-Warshall-algorithm-important-to-its-correctness

1 Like

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 : algorithm - Why does order of 3 loops in Floyd-Warshall matters? - Stack Overflow

Or may be this one :

EDIT: I found similar question on CodeChef here : Floyd Warshall Algorithm - general - CodeChef Discuss

1 Like

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).

#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);
}

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

Because in the second code you changed the loop variables position

btw @coder_voder from where are you learning graphs?

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?

geeksforgeeks and commonlounge

Which topics have you prepared till now?

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

@emim3m that was a nice link

@tanmay_sachan thanks

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

Yes pretty comfortable

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

1 Like

@nikhil_chandak thanks