图的单源最短路径,Floyd算法(数据结构c++)

这个算法结构很是简单,但是理解还是有一定的困难,一开始做的时候想不明白,跟着算法自己动手画画就知道这个算法具体是怎么回事了。

时间复杂度是O(N*3)

算法有点动态规划的意思,有两个数组,一个(dis[])是记录俩顶点之间的最短路径的长度的,一个[path]数组是记录俩结点的中间结点的。在初始化这个数组的默认为 顶点的下标。。 

最重要的就是下面的几步

if(dis[sta][end]>dis[sta][temp]+dis[temp][end]){

dis[sta][end] = dis[sta][temp]+dis[temp][end];

}

上面的代码就是这个算法的精华部分。

sta:开始的顶点,end:结束的顶点,temp:是sta和end上的中间结点

两者相比较,要是有更短的路径就跟新俩结点的距离。

以每一个结点为中间点,更新数组,也就是所有顶点的距离。

话不多说。上程序。。。。


图的单源最短路径,Floyd算法(数据结构c++)



图的单源最短路径,Floyd算法(数据结构c++)
图的单源最短路径,Floyd算法(数据结构c++)
图的单源最短路径,Floyd算法(数据结构c++)
图的单源最短路径,Floyd算法(数据结构c++)

OK

就这个多,之前的都是铺垫,注意看重点的部分,floyd算法部分

上一篇:二叉树中用到的基本算法(叶子,度,遍历)


下一篇:目前比较全的CSS重设(reset)方法总结