floyd.cpp

来自「是各种常用算法的集合」· C++ 代码 · 共 16 行

//动态规划
//Floyd算法
//G.n()返回图中的顶点数目
void Floyd(Graph &G) {
	//建立数组以存储各对顶点间的距离
	int D[G.n()][G.n()];
	for (int i=0; i<G.n(); i++) 
		for (int j=0; j<G.n(); j++)
			D[i][j] = G.weight(i, j);
	for (int k=0; k<G.n(); k++)
		for (int i=0; i<G.n(); i++)
			for (int j=0; j<G.n(); j++)
				if (D[i][j] > (D[i][k] + D[k][j]))
					D[i][j] = D[i][k] + D[k][j];
}