#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;
}
|
