25 August 2015

最短路算法总结


Dijkstra算法:

Dijkstra算法是经典的单源最短路算法。用于计算一个节点到其他所有节点间的最短路径的算法。Dijkstra算法可以用在有向图中,但是不可以用于负权图中。

已知条件是起始点与终止点,有向图的邻接矩阵,需要求解的是起始点与终止点之间的最短路径以及该路径的长度。
初始时,初始点的距离值为0,其他所有点的距离值为正无穷大。

从起始点开始,首先,先比较与所有邻居点的距离,若该点与邻居点的距离小于邻居点自己的距离值,将邻居点的前置点设为该点,并更新邻居点的距离值。
然后,将该点标记为已访问,之后,从未访问的点中选择距离值最小的点作为下一轮的点。

这样,直到找到终止点,最后,从终止点可以倒推出最短路径以及该路径的长度。
并且,当所有点都被标记为已访问,那么可以得到起始点到所有其他节点间的最短路径。

Floyd算法:

Floyd算法是多源最短路算法。用于计算任意两个节点间的最短路径的算法。Floyd算法可以用在有向图以及负权图中。
Floyd算法使用了动态规划的思想,将最短路径的目标做了精彩的演绎。状态转移方程是DIS[i,j]= min{(DIS[i,k]+ DIS[k,j]), DIS[i,j]}。

已知条件是有向图的邻接矩阵,需要求解的是任意两点间的最短路径。

对于每一对节点i和j,如果存在一个节点k,使得i经过k后可以到达j,那么比较DIS[i,j]> DIS[i,k]+ DIS[k,j],如果成立,更新DIS[i,j]= DIS[i,k]+ DIS[k,j]。
当整个邻接矩阵遍历完毕后,即可得到任意两点间的最短路径。


blog comments powered by Disqus