所有顶点对之间的最短路径问题是：对于给定的有向网络G=(V,E)，要对G中任意两个顶点v,w(v不等于w),找出v到w的最短路径。当然我们可以n次执行DIJKSTRA算法，用FLOYD则更为直接，两种方法的时间复杂度都是一样的。

有向网络用邻接矩阵存储，以下面的有向网络为例：

http://s15/middle/686d0fb0n78c1c0ef710e&690

源程序清单：

#include<stdio.h>
#define n 5   //结点数目
#define maxsize 160  //表示两点间不可达
int path[n][n];//路径矩阵
void floyd(int A[][n],int C[][n]);  //A是路径长度矩阵，C是有向网络G的带权邻接矩阵

void main()
{
 printf("               ——所有顶点对之间的最短路径：Floyd算法——\n");
 printf("（160为无穷远，不可达）\n");
 int A[n][n],C[n][n]={
  {0,10,maxsize,30,100},
  {maxsize,0,50,maxsize,maxsize},
  {maxsize,maxsize,0,maxsize,10},
  {maxsize,maxsize,20,0,60},
  {maxsize,maxsize,maxsize,maxsize,0}
 };
 floyd(A,C);
}

void floyd(int A[][n],int C[][n])  //A是路径长度矩阵，C是有向网络G的带权邻接矩阵
{
 int i,j,k,next;
 int max=160;
 for(i=0;i<n;i++)//设置A和path的初值
 {
  for(j=0;j<n;j++)
  {
   if(C[i][j]!=max)
    path[i][j]=j;   //j是i的后继
   else
    path[i][j]=0;
   A[i][j]=C[i][j];
  }
 }
 for(k=0;k<n;k++)
 //做n次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上
 {
  for(i=0;i<n;i++)
  {
   for(j=0;j<n;j++)
   {
    if(A[i][j]>(A[i][k]+A[k][j]))
    {
     A[i][j]=A[i][k]+A[k][j];  //修改长度
     path[i][j]=path[i][k];    //修改路径
    }
   }
  }
 }
 for(i=0;i<n;i++)//输出所有顶点对i,j之间的最短路径Pij的长度及路径
 {
  for(j=0;j<n;j++)
  {
   if(i!=j)
   {
    printf("%d到%d的最短距离为",i+1,j+1);
    printf("%d\n",A[i][j]);   //输出Pij的长度
    next=path[i][j];        //next为起点i的后继顶点
    printf("输出路径：\n");
    if(next==0)
     printf("%d到%d不可达\n",i+1,j+1);
    else//Pij存在
    {
     printf("%d",i+1);
     while(next!=j)
     {
      printf("——>%d",next+1);  //打印后继点
      next=path[next][j];        //继续找下一个后继点
     }
     printf("——>%d\n",j+1);       //打印终点
    }
    printf("****************************************************\n");
   }
  }
 }
}

运行结果：

               ——所有顶点对之间的最短路径：Floyd算法——
（160为无穷远，不可达）
1到2的最短距离为10
输出路径：
1——>2
****************************************************
1到3的最短距离为50
输出路径：
1——>4——>3
****************************************************
1到4的最短距离为30
输出路径：
1——>4
****************************************************
1到5的最短距离为60
输出路径：
1——>4——>3——>5
****************************************************
2到1的最短距离为160
输出路径：
2到1不可达
****************************************************
2到3的最短距离为50
输出路径：
2——>3
****************************************************
2到4的最短距离为160
输出路径：
2到4不可达
****************************************************
2到5的最短距离为60
输出路径：
2——>3——>5
****************************************************
3到1的最短距离为160
输出路径：
3到1不可达
****************************************************
3到2的最短距离为160
输出路径：
3到2不可达
****************************************************
3到4的最短距离为160
输出路径：
3到4不可达
****************************************************
3到5的最短距离为10
输出路径：
3——>5
****************************************************
4到1的最短距离为160
输出路径：
4到1不可达
****************************************************
4到2的最短距离为160
输出路径：
4到2不可达
****************************************************
4到3的最短距离为20
输出路径：
4——>3
****************************************************
4到5的最短距离为30
输出路径：
4——>3——>5
****************************************************
5到1的最短距离为160
输出路径：
5到1不可达
****************************************************
5到2的最短距离为160
输出路径：
5到2不可达
****************************************************
5到3的最短距离为160
输出路径：
5到3不可达
****************************************************
5到4的最短距离为160
输出路径：
5到4不可达
****************************************************
请按任意键继续. . .