#include
#include
#include
#include
typedef char InfoPtr;
typedef char VertexType[4];
typedef int VRType;
#define INFINITY 100000
#define MAXSIZE 100
typedef int PathMatrix[MAXSIZE][MAXSIZE][MAXSIZE];
typedef int ShortPathLength[MAXSIZE][MAXSIZE];
typedef enum{DG, DN, UG, UN
}GraphKind;
typedef struct
{
VRType adj;
InfoPtr *info;
}ArcNode, AdjMatrix[MAXSIZE][MAXSIZE];
typedef struct
{
VertexType vex[MAXSIZE];
AdjMatrix arc;
int vexnum, arcnum;
GraphKind kind;
}MGraph;
typedef struct
{
int row;
int col;
int weight;
} GNode;
void CreateGraph(MGraph *N, GNode *value, int vnum, int arcnum, VertexType *ch);
void DisplayGraph(MGraph N);
void Floyd(MGraph N, PathMatrix path, ShortPathLength dist);
void main()
{
int w, u, v, vnum = 3, arcnum = 4;
MGraph N;
GNode value[] = {{0,1,5}, {1,0,10}, {1,2,6}, {2,0,9}};
VertexType ch[] = {"v0", "v1", "v2"};
PathMatrix path;
ShortPathLength dist;
CreateGraph(&N, value, vnum, arcnum, ch);
for(v = 0; v < N.vexnum; v++)
N.arc[v][v].adj = 0;
DisplayGraph(N);
Floyd(N, path, dist);
printf("顶点之间的最短路径长度矩阵dist:\n");
for(u = 0; u < N.vexnum; u++)
{
for(v = 0; v < N.vexnum; v++)
printf("%6d", dist[u][v]);
printf("\n");
}
for(u = 0; u < N.vexnum; u++)
for(v = 0; v < N.vexnum; v++)
if(u != v)
printf("%s到%s的最短路径为%d\n", N.vex[u], N.vex[v], dist[u][v]);
printf("各顶点之间的最短路径所经过的顶点:\n");
for(u = 0; u < N.vexnum; u++)
for(v = 0; v < N.vexnum; v++)
if(u != v)
{
printf("由%s到%s经过: ", N.vex[u], N.vex[v]);
for(w = 0; w < N.vexnum; w++)
if(path[u][v][w] == 1)
printf("%s ", N.vex[w]);
printf("\n");
}
}
void CreateGraph(MGraph *N, GNode *value, int vnum, int arcnum, VertexType *ch)
{
int i, j, k, w, InfoFlag, len;
char s[MAXSIZE];
VertexType v1, v2;
N->vexnum = vnum;
N->arcnum = arcnum;
for(i = 0; i < vnum; i++)
strcpy(N->vex[i], ch[i]);
for(i = 0; i < N->vexnum; i++)
for(j = 0; j < N->vexnum; j++)
{
N->arc[i][j].adj = INFINITY;
N->arc[i][j].info = NULL;
}
for(k = 0; k < arcnum; k++)
{
i = value[k].row;
j = value[k].col;
N->arc[i][j].adj = value[k].weight;
}
N->kind = DN;
}
void DisplayGraph(MGraph N)
{
int i, j;
printf("有向网具有%d个顶点%d条弧，顶点依次是：", N.vexnum, N.arcnum);
for(i = 0; i < N.vexnum; ++i)
{
printf("%s ", N.vex[i]);
}
printf("\n有向网N的：\n");
printf("序号i=");
for(i = 0; i < N.vexnum; i++)
{
printf("%11d", i);
}
printf("\n");
for(i = 0; i < N.vexnum; i++)
{
printf(" %6-d ", i);
for(j = 0; j < N.vexnum; j++)
printf("%-11d", N.arc[i][j].adj);
printf("\n");
}
}
void Floyd(MGraph N, PathMatrix path, ShortPathLength dist)
{
int u, v, w, i;
for(v = 0; v < N.vexnum; v++)
for(w = 0; w < N.vexnum; w++)
{
dist[v][w] = N.arc[v][w].adj;
for(u = 0; u < N.vexnum; u++)
path[v][w][u] = 0;
if(dist[v][w] < INFINITY)
{
path[v][w][v] = 1;
path[v][w][w] = 1;
}
}
for(u = 0; u < N.vexnum; u++)
for(v = 0; v < N.vexnum; v++)
for(w = 0; w < N.vexnum; w++)
if(dist[v][u] < INFINITY && dist[u][w] < INFINITY
&& dist[v][u] + dist[u][w] < dist[v][w])
{
dist[v][w] = dist[v][u] + dist[u][w];
for(i = 0; i < N.vexnum; i++)
path[v][w][i] = path[v][u][i] || path[u][w][i];
}
}
