Program segment for All pairs shortest paths algorithm

AllPairsShortestPaths(int N, Matrix C, Matrix P, Matrix D)

{

int i, j, k

if i = j then C[i][j] = 0

 for ( i = 0; i < N; i++)

{

for (j = 0; j < N; j++)

{

D[i][j] = C[i][j]; P[i][j] = -1;

} D[i][j] = 0;

}

for (k=0; k

{

for (i=0; i

{

for (j=0; J

{

if (D[i][k] + D[k][j] < D[i][j])

{

D[i][j] = D[i][k] + D[k][j]; P[i][j] = k;

}

}

}

}

}

/*********** End *************/

From the above algorithm, it is obvious that it has O(N³) time complexity. Shortest path algorithms had many applications in the areas of Operations like Computer Science, Research, Electrical Engineering and other related areas.