最短路径算法正确性和操作性闲杂谈-Dijkstra&Floyd算法

事实上,对于大多数的学生或者领域内的工作者而言,根本没有必要去操心Dijkstra算法正确与否,直接拿来用即可,只有事多的较真儿的或者美其名曰研究型的人才会关注算法的正确性。相反,令人悲哀的是,对于大多数的人而言,不如直接来一段可以编译通过并打印出结果的C代码或者Java代码来的痛快。对于我个人而言,也一样,我自己也想来点可操作的东西,我不想或者说是十分讨厌在操作之外空谈理论。那么,我该来一段Dijkstra算法的代码吗?
不!决不!
接下来的篇幅交给另一个算法,即Floyd算法。这次,我只谈操作性,不谈证明。
事实上,我并没刻意去区分Floyd算法和Dijkstra算法,它们本质上是一样的东西,都是局部决定整体思想下的结果。

首先将一个原始图转化为以下两个矩阵,其中矩阵D表示图的邻接矩阵,而矩阵P表示图节点的经由路径:


然后操作就开始了,步骤非常之简单,我只给出前三个步骤:

五个步骤操作全部完成后,矩阵D的结果代表的就是节点间的最短距离,而矩阵P则表示一张路由表,这两个矩阵代表了一个任意节点到任意节点间最短路径的向量集,是的,它是一张完美的路由表。
        这个Floyd算法是个典型的Step by Step的算法步骤,非常适合计算机硬件去实现,但是相对于单源Dijkstra算法,其时间复杂度是立方级的O(n^3),对于路由器而言,这实则压力不小,反观Dijkstra算法则更适合路由器,因为IP网络是逐跳转发的,路由器只用操心以自己为源点到达其它任意节点的最短距离即可。

未经允许不得转载:JX BLOG » 最短路径算法正确性和操作性闲杂谈-Dijkstra&Floyd算法

赞 (0)

评论 0

评论前必须登录!

登陆 注册