Wednesday, 24 June 2015

Shortest Path Between I and J


int edges[][]; //edge[i][j] = length btwn direct edge btwn i and j
int dist[][]; //dist[i][j] = length of shortest path btwn i and j
int path[][]; //path[i][j] = on shrotest path from i to j, path[i][j] is the last node before j
int n;
void solveFloydWarshall()
{ int i, j,k;
//copy edge weight over and set each path pointing to itself for(i = 0; i < n; i++)
{
for(j =0; j< n; j++)
{ dist[i][j] = edges[i][j]; path[i][j] = i;
}
}
//all diagonal distances is 0 for(i = 0; i < n; i++)
{ dist[i][i] = 0;
}
//perform the algorithm
for(k = 0; k < n; k++)//length of the current paths
{ for(i = 0; i < n; i++) //start at node i
{
for(j =0; j < n; j++) //point to node j
{ int cost = dist[i][k] + dist[k][j]; if( cost < dist[i][j])
{ dist[i][j] = cost; // reduce i -> j to smaller i ->
//k -> j path[i][j] = path[k][j]; //update path for i -> j
}
}
}
}
}

No comments:

Post a Comment