【数据结构】最短路径Floyd

#include
#include
#define MAX 50
#define INFINIT 65535

using namespace std;

class MGraph {
	private:
		int vertexNum, arcNum;
		int arc[MAX][MAX];
		string vertex[MAX];
		int dist[MAX][MAX];
		string path[MAX][MAX];

	public:
		MGraph(string v[], int n, int e);
		void display();
		void Floyd();

		void displayPath();
		void displayDist();
};

MGraph::MGraph(string v[], int n, int e) {
	vertexNum = n;
	arcNum = e;
	for (int i = 0; i < vertexNum; i++) {
		vertex[i] = v[i];
	}
	for (int i = 0; i < arcNum; i++) {
		for (int j = 0; j < arcNum; j++) {
			if (i == j) {
				arc[i][j] = 0;
			} else {
				arc[i][j] = INFINIT;
			}
		}
	}
	int vi, vj, w;
	for (int i = 0; i < arcNum; i++) {
		cout << "请输入有向边的两个顶点和这条边的权值" << endl;
		cin >> vi >> vj >> w;
		arc[vi][vj] = w; //有边标志
	}
}

void MGraph::display() {

	cout << "节点信息：" << endl;
	for (int i = 0; i < vertexNum; i++) {
		cout << vertex[i] << "t";
	}
	cout << endl;


	cout << "邻接矩阵：" << endl;
	for (int i = 0; i < vertexNum; i++) {
		for (int j = 0; j < vertexNum; j++) {
			if (arc[i][j] == INFINIT) {
				cout << "∞" << "t";
			} else {
				cout << arc[i][j] << "t";
			}
		}
		cout << endl;
	}

}

void MGraph::Floyd() {
	for (int i = 0; i < vertexNum; i++) {
		for (int j = 0; j < vertexNum; j++) {
			dist[i][j] = arc[i][j];
			if (INFINIT != dist[i][j] && 0 != dist[i][j]) {
				path[i][j] = vertex[i] + vertex[j];
			} else {
				path[i][j] = '';
			}
		}
	}
	for (int k = 0; k < vertexNum; k++) {
		for (int i = 0; i < vertexNum; i++) {
			for (int j = 0; j < vertexNum; j++) {
				if (dist[i][j] > dist[i][k] + dist[k][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
					string temp = path[i][k].substr(0, path[i][k].length() - 1);
					path[i][j] = temp + path[k][j];
				}
			}
		}
	}
	displayDist();
	displayPath();
}


void MGraph::displayPath() {
	cout << "path:" << endl;
	for (int i = 0; i < vertexNum; i++) {
		for (int j = 0; j < vertexNum; j++) {
			cout << path[i][j] << "t";
		}
		cout << endl;
	}
}

void MGraph::displayDist() {
	cout << "dist:" << endl;
	for (int i = 0; i < vertexNum; i++) {
		for (int j = 0; j < vertexNum; j++) {
			cout << dist[i][j] << "t";
		}
		cout << endl;
	}

}


int main() {
	int n, e;
	string v[MAX];
	cout << "请输入顶点数和边数" << endl;
	cin >> n >> e;
	cout << "请输入顶点信息" << endl;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	MGraph mgraph(v, n, e);
	mgraph.display();
	mgraph.Floyd();
	return 0;
}