#include <iostream> #include <string> #include <stdio.h> using namespace std; #define MaxVertexNum 100 #define INF 32767 typedef struct { string vertex[MaxVertexNum]; int edges[MaxVertexNum][MaxVertexNum]; int n, e; } MGraph;
void CreateMGraph(MGraph &G) { int i, j, k, p; cout << "请输入顶点总数:"; cin >> G.n; cout << "请输入顶点元素:"; for (i = 1; i <= G.n; i++) { cin >> G.vertex[i]; } cout << "请输入边数:"; cin >> G.e;
for (i = 1; i <= G.n; i++) { for (j = 1; j <= G.n; j++) { G.edges[i][j] = INF; if (i == j) { G.edges[i][j] = 0; } } } for (k = 1; k <= G.e; k++) { cout << "请输入第" << k << "条弧头弧尾序号和相应的权值:"; cin >> i >> j >> p; G.edges[i][j] = p; G.edges[j][i] = p; } cout << endl << endl; }
void Ppath(MGraph G, int path[][MaxVertexNum], int i, int j) { int k; k = path[i][j]; if (k == -1) { return; } Ppath(G, path, i, k); cout << G.vertex[k] << "->"; Ppath(G, path, k, j); } void Dispath(MGraph G, int A[][MaxVertexNum], int path[][MaxVertexNum], int n) { int i, j; for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (A[i][j] == INF) { if (i != j) { cout << "从" << G.vertex[i] << "到" << G.vertex[j] << "没有路径" << endl; } } else { if (i != j) { cout << "从" << G.vertex[i] << "到" << G.vertex[j] << "=>最短路径路径长度为:"; printf("%3d", A[i][j]); cout << " 路径:"; cout << G.vertex[i] << "->"; Ppath(G, path, i, j); cout << G.vertex[j] << endl; } } } } } void Floyd(MGraph G) { int A[MaxVertexNum][MaxVertexNum], path[MaxVertexNum][MaxVertexNum]; int i, j, k; for (i = 1; i <= G.n; i++) { for (j = 1; j <= G.n; j++) { A[i][j] = G.edges[i][j]; path[i][j] = -1; } } for (k = 1; k <= G.n; k++) { for (i = 1; i <= G.n; i++) { for (j = 1; j <= G.n; j++) { if (A[i][j] > A[i][k] + A[k][j]) { A[i][j] = A[i][k] + A[k][j]; path[i][j] = k; } } } } Dispath(G, A, path, G.n); } int main() { freopen("input.txt", "r", stdin); MGraph G; CreateMGraph(G); Floyd(G); return 0; }
|