Floyd-Warshall算法的原理是动态规划。
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。
- 若最短路径经过点k,则Di,j,k = Di,k,k − 1 + Dk,j,k − 1;
- 若最短路径不经过点k,则Di,j,k = Di,j,k − 1。
因此,Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。
for (k = ; k <= n; k++) //经过编号为前k个的顶点
{
for (i = ; i <= n; i++)
{
for (j = ; j < i; j++)
{
if ( == A[i][k] || == A[k][j])
continue;
if ( == A[i][j] || A[i][k] + A[k][j] < A[i][j])
A[i][j] = A[j][i] = A[i][k] + A[k][j];
}
}
}