计算给定的带权图中任意两个顶点之间最短路径的算法
const int inf=0x3f3f3f3f;
int g[MAX_N][MAX_N];//算法中的G矩阵
//初始化g矩阵
void init(){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(i==j){
g[i][j]=0;
}else{
g[i][j]=inf;
}
}
}
}
//插入一条带权有向边
void insert(int u,int v,int w){
g[u][v]=w;
}
//核心代码
void floyd(){
for(int k=0;k<n;++k){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(g[i][k]+g[k][j]<g[i][j]){
g[i][j]=g[i][k]+g[k][j];
}
}
}
}
}