floyd(多源最短路算法)

计算给定的带权图中任意两个顶点之间最短路径的算法

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

 

上一篇:最短路径 (复习?重新学!)(未完成)


下一篇:算法——最短路径 Dijkstra算法和Floyd算法