#include<stdio.h>
#include<stdlib.h>
#define MaxVexNum 50
#define MaxInt 32767
#define MaxEdgeNum 50
//邻接矩阵
typedef int VertexType;
typedef int EdgeType;
typedef struct AMGraph{
VertexType vexs[MaxVexNum];//顶点表
EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表
int vexnum,edgenum;//顶点数，边数
}AMGraph;
void createGraph(AMGraph &g){//创建无向图
printf("请输入顶点数：");
scanf("%d",&g.vexnum);
printf("\n请输入边数：");
scanf("%d",&g.edgenum);
//初始化顶点表
for(int i=0;i<g.vexnum;i++){
g.vexs[i]=i;
}
for(int i=0;i<g.vexnum;i++){
for(int j=0;j<g.vexnum;j++){
g.arcs[i][j]=MaxInt;
if(i==j) g.arcs[i][j]=0;
}
}
printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
for(int i=0;i<g.edgenum;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
g.arcs[x][y]=w;
//g.arcs[y][x]=w;
}
}
void PrintGraph(AMGraph g){
printf("邻接矩阵为:\n");
for(int i=0;i<g.vexnum;i++) {
printf(" %d",g.vexs[i]);
}
printf("\n");
for(int i=0;i<g.vexnum;i++){
printf("%d ",g.vexs[i]);
for(int j=0;j<g.vexnum;j++){
if(g.arcs[i][j]==32767){
printf("∞ ");
}else{
printf("%d ",g.arcs[i][j]);
}
}
printf("\n");
}
}
//Floyd算法
//递归输出两个顶点直接最短路径
void printPath(int u,int v,int path[][MaxVexNum]){
if(path[u][v]==-1){
printf("[%d %d] ",u,v);
}else{
int mid=path[u][v];
printPath(u,mid,path);
printPath(mid,v,path);
}
}
void Floyd(AMGraph g,int path[][MaxVexNum]){
int n=g.vexnum;
int A[n][n];
//第一步：初始化path[][]和A[][]数组
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
A[i][j]=g.arcs[i][j];
path[i][j]=-1;
}
}
//第二步：三重循环，寻找最短路径
for(int v=0;v<n;v++){//第一层是代表中间结点
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(A[i][j]>A[i][v]+A[v][j]){
A[i][j]=A[i][v]+A[v][j];
path[i][j]=v;
}
}
}
}
}
int main(){
AMGraph g;
createGraph(g);
PrintGraph(g);
int path[MaxVexNum][MaxVexNum];
Floyd(g,path);
printPath(1,0,path);
}
评论8