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(N3) time complexity. Shortest path algorithms had many applications in the areas of Operations like Computer Science, Research, Electrical Engineering and other related areas.