Floyd算法的简单实现（C++版)

头文件Floyd.h
#ifndef MATRIX_H
#define MATRIX_H
using namespace std;
class Floyd
{
const int max = 100;//不连通时的距离，假设为无穷大
int v;//点的个数
int e;//边的个数
int d;//定义动态数组的指针(表示两点距离）
int *p;//定义动态数组的指针（表示两点的中间点）
int path;//记录插点后的两点路程总值
public:
Floyd(int v, int e) ;
~Floyd()
{
delete[]d;
delete[]p;
}
};
#endif
*类的实现
#include"pch.h"
#include
#include"Floyd.h"
using namespace std;
Floyd::Floyd(int v, int e) :v(v), e(e)
{
int i, j,x,y,L,k;
//动态二维矩阵创建
d = new int[v];
for (int i = 0; i < v; i++)
d[i] = new int[v];
p = new int[v];
for (int i = 0; i < v; i++)
p[i] = new int[v];
//初始化两点路径，默认为第二个点
for (i = 0; i <v; i++)
for (j = 0; j < v; j++)
p[i][j] = j;
//除对角元素外，矩阵元素默认最大值，即两点间距无穷大，不连通（只对右上角赋值)
for (i = 0; i < v; i++)
{
for (j = i; j < v; j++)
{
if (i == j)
d[i][j] = 0;
else
d[i][j] = max;
}
}
//根据边的数量，为对应矩阵元素赋值，使其连通
for (i = 0; i <e; i++)
{
cout << "请输入第" <<i+1<<"条边的起点、终点、边长"<< endl;
cin >> x >> y>> L;
d[x-1][y-1] = L;
}
//矩阵对折，对称矩阵的另一半赋值
for(i=0;i<v;i++)
for (j = i+1; j < v; j++)
{
d[j][i] = d[i][j];
}
//输出矩阵，用作查验
for (i = 0; i < v; i++)
{
if (i == 0)
{
for (j = 0; j <= v; j++)
{
if (j == 0)
cout << "v" << "\" << "e";
else
cout << "\t" << j;
if(j == v)
cout << endl << endl;
}
}
for(j=0;j<v;j++)
{
if (j == 0)
cout <<i+1<<"\t";
cout << d[i][j] << "\t";
if (j ==v-1)
cout << endl<<endl;
}

}
//比较并插点
for (k = 0; k < v; k++)
    for (i = 0; i < v; i++)
        for (j = 0; j < v; j++)
        {
            if (d[i][j] > d[i][k] + d[k][j])
            {
                d[i][j] = d[i][k] + d[k][j];
                p[i][j] = p[i][k];
            }

        }
int beg_p, end_p,last_beg_p;//last_beg_p用来存放起点位置，便于计算总距离
int path = 0;
cout << "input beg_p,end_p" << endl;
cin >> beg_p >> end_p;
while (beg_p != end_p)
{
    cout << beg_p << "->";
    last_beg_p = beg_p;
    beg_p = p[beg_p-1][end_p-1]+1;
    path += d[last_beg_p-1][beg_p-1];
}
cout << end_p<<endl;
cout << "distance:" << path << endl;

}
主函数
#include "pch.h"
#include
#include"Floyd.h"
using namespace std;

int main()
{
int v, e;//交互界面时使用，如不需要也可以直接类初始化，在形参表中给值
const int max = 10000;
cout << "请分别输入点的个数、边的个数" << endl;
cin >> v >> e;
Floyd(v,e);
system("pause");
return 0;
}