Floyed.h

#include<iostream>
using namespace std;

#define MAX_VEX_NUM 20
#define INFINITY INT_MAX

class Graph //图的存储结构
{
public:
	Graph();
	int vexnum; //顶点数
	int dist[MAX_VEX_NUM][MAX_VEX_NUM]; //dist[i][j]表示从vi到vj的弧上的权值没有弧相同的话就是INFINITY
	bool path[MAX_VEX_NUM][MAX_VEX_NUM][MAX_VEX_NUM]; //path[i][j][k]==true表示vk在vi到vj的路径上
	char name[MAX_VEX_NUM]; //顶点名字
};

Graph::Graph()
{
	vexnum = 0;
	for (int i = 0; i < MAX_VEX_NUM; i++)
		for (int j = 0; j < MAX_VEX_NUM; j++)
			dist[i][j] = INFINITY;
	memset(path, 0, sizeof(path));
}

class ShortestPath_Floyd
{
public:
	void Floyod(); //接口函数
private:
	void GetVex(); //得到顶点
	void GetArc(); //得到弧
	void GetShortestPath(); //得到最短路径
	void PrintPath(); //打印最短路径
	Graph g;
};

void ShortestPath_Floyd::Floyod() //接口函数
{
	GetVex(); //得到顶点
	GetArc(); //得到弧
	GetShortestPath(); //得到最短路径
	PrintPath(); //打印最短路径
}

void ShortestPath_Floyd::GetVex() //得到顶点
{
	cout << "Please Input The Name Of Each Vertex :" << endl;
	while (cin >> g.name[g.vexnum])
		g.vexnum++;
	cin.clear();
}

void ShortestPath_Floyd::GetArc() //得到弧
{
	cout << "Please Input The Information Of Each Arc :" << endl
			<< "tail head weight" << endl;
	int tail, head, weight;
	while (cin >> tail >> head >> weight)
	{
		g.dist[tail][head] = weight;
		g.path[tail][head][tail] = g.path[tail][head][head] = true; //将tail和head放置在从tail到head的最短路径上
	}
	cin.clear();
}

void ShortestPath_Floyd::GetShortestPath() //得到最短路径
{
	for (int u = 0; u < g.vexnum; u++)
		for (int v = 0; v < g.vexnum; v++)
			for (int w = 0; w < g.vexnum; w++)
				if (g.dist[v][u] != INFINITY && g.dist[u][w] != INFINITY
						&& g.dist[v][u] + g.dist[u][w] < g.dist[v][w])
				//如果从v到u，从u到w均有路径相通且大于v到w的当前最小路径长度
				{
					g.dist[v][w] = g.dist[v][u] + g.dist[u][w]; //更新v到w的最短路径长度
					for (int i = 0; i < g.vexnum; i++)
						g.path[v][w][i] = g.path[v][u][i] || g.path[u][w][i]; //将相关点加到从v到w的路径上
				}
}

void ShortestPath_Floyd::PrintPath() //打印最短路径
{
	for (int i = 0; i < g.vexnum; i++)
	{
		for (int j = 0; j < g.vexnum; j++)
		{
			if (i != j && g.dist[i][j] != INFINITY)
			{
				cout << g.name[i] << "-" << g.dist[i][j] << "->" << g.name[j]
						<< " : " << endl;
				for (int k = 0; k < g.vexnum; k++)
				{
					if (g.path[i][j][k])
						cout << g.name[k] << " ";
				}
				cout << endl;
			} //if
		} //for
	} //for
}

main.cpp

#include"Floyd.h"
 
int main()
{
	ShortestPath_Floyd f;
	f.Floyod();
	system("pause");
}