弗洛伊德算法计算所有顶点对之间最短通路的长度

//弗洛伊德算法计算所有顶点对之间最短通路的长度
// procedure Floyd(G:带权简单图)
//  {G有顶点v1.v2....vn和权}
// for i= 1 to n
///  for j= 1 to n
//     d(vi,vj)=w（i，j）
//
// for i= 1 to n
///  for j= 1 to n
//     for k= 1 to n
//       if d(vj,vi)+d(vi,vk)<d(vj,vk)
//        then d(vj,vk) = d(vj,vi)+d(vi,vk)
// d(vi,vj)是在vi到vj之间的最短通路

//这个算法是计算所有顶点对之间最短通路的长度
//具体实现，应该要用到保存所有顶点对之间最短通路的长度的存贮单位(这里使用了二维数组存贮)


/*
粘贴输入下列测试数据
  6 9
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3
‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘‘
0 4 2 32767 32767 32767
4 0 1 5 32767 32767
2 1 0 8 10 32767
32767 5 8 0 2 6
32767 32767 10 2 0 3
32767 32767 32767 6 3 0

0 ,0:0
0 ,1:3
0 ,2:2
0 ,3:8
0 ,4:10
0 ,5:13
1 ,1:0
1 ,2:1
1 ,3:5
1 ,4:7
1 ,5:10
2 ,2:0
2 ,3:6
2 ,4:8
2 ,5:11
3 ,3:0
3 ,4:2
3 ,5:5
4 ,4:0
4 ,5:3
5 ,5:0
Press any key to continue

*/

#include <iostream>
using namespace std;
//012345分别表示v0 v1......
  int v;//////点数目
  int edge;///边数目

int** draw(int ** &l);//绘图
void shuchu(int **l);//输出
int main(int argc, char const *argv[])
{
 
  int **l;
  int**a=draw(l);
//------------------------------------------------------------------------//

//------------------------------------------------------------------------//
  int i,j,k;
  		for ( i = 0; i < v; ++i)
  			for ( j = 0; j < v; ++j)
  				for (k = 0; k < v; ++k)
  		           	if (l[j][i] + l[i][k] < l[j][k])
 						l[j][k] = l[j][i] + l[i][k];
 
  //------------------------------------------------------------------------//
  shuchu(l);
  return 0;
}
int** draw(int ** &l)//绘图
{
  int i,j;
  cin>>v>>edge;///输入点数目和边数目
  int **a=new int*[v];
  for ( i = 0; i < v; ++i)
    a[i]=new int[v];

  l=new int*[v];
   for ( i = 0; i < v; ++i)
     l[i]=new int[v];

  for ( i = 0; i < v; ++i)
    for ( j = 0; j < v; ++j)
      {
		if(i==j){a[i][j]=0;l[i][j]=0;continue;}
		a[i][j]=32767;l[i][j]=32767;
	}

  int spot1,spot2,len;
  for ( i = 0; i < edge; ++i)
  {
    cin>>spot1>>spot2>>len;
    a[spot1][spot2]=len;    a[spot2][spot1]=len;
     l[spot1][spot2]=len;    l[spot2][spot1]=len;
  }
///-------------------------------------------------------------///
    for ( i = 0; i < v; ++i){
    for ( j = 0; j < v; ++j)
      cout<<a[i][j]<<" ";
    cout<<"\n";
    }
    cout<<"\n";
  return a;
}

void shuchu(int **l)
{
	int i,j;
   for ( i = 0; i < v; ++i)
      for ( j = i; j < v; ++j)
        cout<<i<<" ,"<<j<<":"<<l[i][j]<<"\n";


}

弗洛伊德算法计算所有顶点对之间最短通路的长度

原文：http://blog.csdn.net/h1023417614/article/details/18794725