我的日志

Home > My Log

 

 

2006-5-31 最短路径算法

在google黑板报上看到一个工程师关于“最笨”的人对于最短路径算法的有趣研究,佩服得很,载录如下:

 法国伟大的文学家、思想家、革命家孟德斯鸠教导我们说,身为 Google 工程师的最大好处就是 — 你总能在第一时间知道自己离“笨得离谱”还有多远。老孟的话得这么理解:“笨”其实是一种美德,远比“厚道”更易让人神往,尤其是在遇到了一个比你更笨的人之后。

有一次,我笨得忘记了该如何在一个复杂的有向图中找出两点之间的最短路径。身边的一位工程师很郑重地告诉我说:“你知道吗?解决这个问题有两种方法,聪明人的方法和笨人的方法。聪明人的方法是:照着算法教科书的讲解,实现那个时间复杂度相当大的名叫嘀嘀哒嘀哒的最短路径算法。笨人的方法时间复杂度最低:找一堆线头来,按照有向图的结构连成一张网,然后一手拿一个顶点,向两边一抻,中间拉直了的那条路就是最短路径呀。”

“哇噻!笨是一种多么伟大的品格呀!”我眩晕得说不出话来。于是,我们这两个自认为足够笨的工程师足足花了两周的时间,用计算机程序模拟了不同材质的细线在北半球的重力条件下相互连接并在两个反方向作用力的影响下向两边伸展的整个物理过程,然后以此为基础实现了时间复杂度最小的最短路径算法。——瞧,在 Google,什么东西都可以自己动手实现,什么东西也都可以推陈出新,我们的杰出表现就是最好的证明。

2006-5-31 开篇

其实在主页上写日志实在是不太合适,太麻烦了,不过好在我并不是那种勤于动笔记录生活的人,偶尔看到些有意思的文章,或由此有些想法,记在这里和大家分享也好啦。