算法思想

对于构成最小环的点集{x1, x2, …},其中必定存在一个最大点xk,那么最小环的长度可以由dis[i][j]+m[j][xk]+m[xk][i]来表示,其中i,j均在点集中且小于xk,dis[i][j]是i到j的最短路径。因为xk是点集中最大的那个点,所以i到j的最短路径没有经过编号比xk更大的点。那么要求最小环的长度就可以由小到大枚举一下xk就行了。我们知道,floyd算法最外层每循环一次,就是由一个中间节点k更新点i到j的最短路径。k从小到大枚举,就保证了循环到k的时候,当前i到j的最短路经过的最大节点只可能是k,这刚好满足上面提到的dis[i][j]的定义。所以我们就可以愉快的使用floyd来求最小环了。

Continue reading
  • page 1 of 1

sillyplus

Write the code. Change the world


Student


China