此算法可以求任意两点的最短距离，其中边权值可以为负数，而dijkstra只能是固定的点间的距离，并且边全值不能为负数。

保存的是后面的点（更好）

#include<iostream>

#include<stdio.h>

#include<iomanip>

using namespace std;

#define N 100

#define MAX 1000000

int a[N][N];

int path[N][N];

void input (int n)

{

 int p,q,len,i,j;

 for( i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

   a[i][j]=MAX;

   if(i==j)

    a[i][j]=0;

  }

 while(1)

 {

  cin>>p>>q;

  if(p||q)

   cin>>len;

  else

   break;

  a[p][q]=len;

 }

}

void Floyd(int n)

{

 int i,j,k;

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

   path[i][j]=j;//初始化路径，将i后面的点记录在path中

 for(k=1;k<=n;k++)

  for(i=1;i<=n;i++)

   for(j=1;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];/*path记录i后面的点*/

    }

 printf("最短路径矩阵如下:\n");

 for(i=1;i<=n;i++)/*打印最短路径矩阵j*/

 {

  for(j=1;j<=n;j++)

   printf("%8d",a[i][j]);

  cout<<endl;

 }

}

void Dispath(int n)//输出经过的点

{

 int i,j,h;

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

         cout<<" 点 "<<i<<" 到点 "<<j<<" 最短长度为: "<<a[i][j];

   cout<<" 经过的点为:  ";

            cout<<i<<"->";

         h=path[i][j];

         while(h!=j)

   {

             cout<<h<<"->";

          h=path[h][j];

   }

         cout<<j<<endl;

  }

}   

int main()

{

 int n;

 scanf("%d",&n);

 input(n);

 Floyd(n);

 Dispath(n);

 return 0;

}

或者

保存的是前面的点

#include<iostream>

#include<stdio.h>

#include<iomanip>

using namespace std;

#define N 100

#define MAX 10000

int a[N][N];

int path[N][N];

void input (int n)

{

 int p,q,len,i,j;

 for( i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

   a[i][j]=MAX;

   if(i==j)

    a[i][j]=0;

  }

 while(1)

 {

  cin>>p>>q;

  if(p||q)

   cin>>len;

  else

   break;

  a[p][q]=len;

 }

}

void Floyd(int n)

{

 int i,j,k;

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

   path[i][j]=i;//初始化路径，将j前面的点记录在path中

 for(k=1;k<=n;k++)

  for(i=1;i<=n;i++)

   for(j=1;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[k][j];/*path记录j前面的点*/

    }

 printf("最短路径矩阵如下:\n");

 for(i=1;i<=n;i++)/*打印最短路径矩阵*/

 {

  for(j=1;j<=n;j++)

   printf("%8d",a[i][j]);

  cout<<endl;

 }

}

void Dispath(int n)//输出经过的点

{

 int i,j,temp,que[N],tot;

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

   tot=1;

   que[tot++]=j;

   temp=path[i][j];

   while(temp!=i)

   {

    que[tot++]=temp;

    temp=path[i][temp];

   }

   que[tot]=i;

   cout<<" 点 "<<i<<" 到点 "<<j<<" 最短长度为: "<<a[i][j];

   cout<<" 经过的点为:  ";

   for(;tot>1;tot--)

    cout<<que[tot]<<"->";

   cout<<que[tot]<<endl;

  }

}   

int main()

{

 int n;

 scanf("%d",&n);

 input(n);

 Floyd(n);

 Dispath(n);

 return 0;

}

递归也可以

#include<iostream>

#include<stdio.h>

#include<iomanip>

using namespace std;

#define N 100

#define MAX 10000

int a[N][N];

int path[N][N];

void input (int n)

{

 int p,q,len,i,j;

 for( i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

   a[i][j]=MAX;

   if(i==j)

    a[i][j]=0;

  }

 while(1)

 {

  cin>>p>>q;

  if(p||q)

   cin>>len;

  else

   break;

  a[p][q]=len;

 }

}

void Floyd(int n)

{

 int i,j,k;

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

   path[i][j]=-1;

 for(k=1;k<=n;k++)

  for(i=1;i<=n;i++)

   for(j=1;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]=k;

    }

 printf("最短路径矩阵如下:\n");

 for(i=1;i<=n;i++)/*打印最短路径矩阵*/

 {

  for(j=1;j<=n;j++)

   printf("%8d",a[i][j]);

  cout<<endl;

 }

}

void ppath(int i,int j)//递归你懂吗

{

 int k;

 k=path[i][j];

 if(k==-1)

  return;

 ppath(i,k);

 printf("->%d",k);

 ppath(k,j);

}

void Dispath(int n)//输出经过的点

{

 int i,j;

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

   cout<<" 点 "<<i<<" 到点 "<<j<<" 最短长度为: "<<a[i][j];

   cout<<" 经过的点为:  ";

   cout<<i;

   ppath(i,j);

   cout<<"->"<<j;

   cout<<endl;

  }

}   

int main()

{

 int n;

 scanf("%d",&n);

 input(n);

 Floyd(n);

 Dispath(n);

 return 0;

}