|
全点对最短路径问题
对于给定的图G（V,E），求出图中任何点对之间的最短距离。 已知： W[i][j]表示在图上i和j两个结点的距离。INF表示无穷大。 L[i][j]表示从结点i到结点j的最短距离。 b[i][j]表示求从结点i到结点j的最短路径时，结点j的父节点。
算法实现
首先，假设对于每条路径而言，最多只有一条边，L（1）表示每条路径最多只有一条边时的结果，则有L（1）=W。 接着，求出每条路径最多有2，3，4。。。n-1条边时的结果。 很明显，我们可以得到一个结论：L(m)[i][j]=min{L(m-1)[i][k]+W[k][j]}，其中k可取的值为0~n-1.
代码实现
#include
#include
#define INF 90
const int n=5;
int w[n][n] =
{
{0,3,8,INF,-4},
{INF,0,INF,1,7},
{INF,4,0,INF,INF},
{2,INF,-5,0,INF},
{INF,INF,INF,6,0}
};
int **L;
int b [n][n];
int ** extend(int **old,int m){
int **l = (int **)malloc(n*sizeof(int *));
for(int i=0;i |