include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

define MaxVex 100

typedef char VexType;
typedef int EdgeType;
typedef struct{
VexType node[MaxVex];
EdgeType edges[MaxVex][MaxVex];
int vexnum,edgenum;
}AdjMatrix;
//邻接矩阵定义

typedef struct {
int v0;
int v1;
int weight;
}Edge;

define MaxInt 50

int dist[MaxVex][MaxVex];
//dist[i][j]表示从i到j点的最短路径距离
int path[MaxVex][MaxVex];
//path[i][j]表示从i到j的最短路径上，j的前一个顶点
void Floyed(AdjMatrix G){
int n=G.vexnum;//这样可以节省后面大量时间
for(int i=1;i<=n;i){
for(int j=1;j<=n;j){
dist[i][j]=G.edges[i][j];
if(dist[i][j]<MaxInt){
path[i][j]=i;
else path[i][j]=-1;
}
}
}
for(int k=1;k<=n;k){
for(int i=1;i<=n;i){
for(int j=1;j<=n;j++){
if(dist[i][k]+dist[k][j]<dist[i][j]){
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=path[k][j];
}
}
}
}
//非常简洁，就是初始化加n-1轮
}

void create(AdjMatrix &G,Edge data[],int n){
for(int i=1;i<=MaxVex-1;i){
for(int j=1;j<=MaxVex-1;j)
G.edges[i][j]=MaxInt;
}
for(int i=1;i<=G.vexnum;i) G.edges[i][i]=0;
for(int i=0;i<n;i){
G.edges[data[i].v0][data[i].v1]=data[i].weight;
G.edges[data[i].v1][data[i].v0]=data[i].weight;
}
}

int main(){
AdjMatrix G;
G.vexnum=7;
G.edgenum=12;
Edge data[]={{1,2,23},{1,7,36},{1,6,28},{2,7,1},{2,3,20},
{3,7,4},{3,4,15},{4,7,9},{5,4,3},{5,7,16},{5,6,17},{6,7,25}
};
AdjMatrix &M=G;
create(M,data,12);
// for(int i=1;i<=G.vexnum;i){
// for(int j=1;j<=G.vexnum;j)
// cout<<setw(3)<<G.edges[i][j]<<’ ‘;
// cout<<endl;
// }
Floyed(G);
for(int i=1;i<=G.vexnum;i){
for(int j=1;j<=G.vexnum;j){
cout<<setw(3)<<dist[i][j];
}
cout<<endl;
}
//通过n次调用dijkstra来验证
}