数据结构 || 图中两点间的最短路径(弗洛伊德算法)

原理讲解参考：https://www.cnblogs.com/wangyuliang/p/9216365.html

代码实现：

#include <iostream>
#include <limits.h>
#include <string>
#include <vector>
#include <iomanip>
using namespace std;
#define MAX_VERTEX_NUM 20
struct Graph {
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	string vexs[MAX_VERTEX_NUM];
	int vexnum, arcnum;
};

int LocateVex(Graph G, string v) {
	for (int i = 0; i < G.vexnum; i++) {
		if (G.vexs[i] == v) {
			return i;
		}
	}
	return -1;
}

void CreateGraph(Graph *G) {
	cout << "请输入顶点数和弧数: " << endl;
	cin >> G->vexnum >> G->arcnum;
	cout << "请输入顶点: " << endl;
	for (int i = 0; i < G->vexnum; i++) {
		cin >> G->vexs[i];
		G->arcs[i][i] = 0;
	}
	for (int i = 0; i < G->vexnum; i++) {
		for (int j = 0; j < G->vexnum; j++) {
			if (i != j) {
				G->arcs[i][j] = INT_MAX;
			}
		}
	}
	for (int i = 0; i < G->arcnum; i++) {
		cout << "请输入边的两个顶点, from v1 to v2: " << endl;
		string v1, v2;
		cin >> v1 >> v2;
		int i1 = LocateVex(*G, v1);
		int i2 = LocateVex(*G, v2);
		cout << "请输入弧的权值: " << endl;
		cin >> G->arcs[i1][i2];
	}
}

void Print(Graph G) {
	cout << "图的邻接矩阵是: " << endl;
	cout << "     ";
	for (int i = 0; i < G.vexnum; i++) {
		cout << setw(3) << G.vexs[i] << setw(3) << "|";
	}
	//cout << G.vexs[(G.vexnum - 1)];
	cout << endl;
	for (int i = 0; i < G.vexnum; i++) {
		cout << G.vexs[i] << "  ";
		for (int j = 0; j < G.vexnum; j++) {
			if (G.arcs[i][j] == INT_MAX) {
				cout << "|" << setw(5) << "∞";
			}
			else
				cout <<  "|" << setw(5) << G.arcs[i][j];
		}
		cout << "|" << endl;
	}
}

void ShortestPath_Flyod(Graph G) {
	const int num = G.vexnum;
	int ShortPathTable[num][num];
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			ShortPathTable[i][j] = G.arcs[i][j];
		}
	}
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			if (i != j) {
				for (int k = 0; k < num; k++) {
					if (j != k) {
						if (ShortPathTable[i][k] != INT_MAX && ShortPathTable[j][i] != INT_MAX) {
							if (ShortPathTable[i][k] + ShortPathTable[j][i] < ShortPathTable[j][k]) {
								ShortPathTable[j][k] = ShortPathTable[i][k] + ShortPathTable[j][i];
							}
						}
						
					}
				}
			}
		}
	}
	cout << "更新后图的最短路径矩阵是: " << endl;
	cout << "     ";
	for (int i = 0; i < num; i++) {
		cout << setw(3) << G.vexs[i] << setw(3) << "|";
	}
	cout << endl;
	for (int i = 0; i < num; i++) {
		cout << G.vexs[i] << "  ";
		for (int j = 0; j < num; j++) {
			if (ShortPathTable[i][j] == INT_MAX) {
				cout << "|" << setw(5) << "∞";
			}
			else
				cout <<  "|" << setw(5) << ShortPathTable[i][j];
		}
		cout << "|" << endl;
	}
}

int main () {
	Graph G;
	CreateGraph(&G);
	Print(G);
	ShortestPath_Flyod(G);
	return 0;
}

实现效果：

测试2：