作者DJWS (...)
看板Prob_Solve
标题Re: [问题] prim's vs dijkstra
时间Sun Feb 17 22:23:39 2008
我刚刚在 wikipedia 找到了这一篇：
E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs.
Numerische Mathematik, vol. 1, pp. 269-271 (1959).
这篇论文解决了两个问题：
1. 建一个最小生成树 (minimum spanning tree)。
2. 找出两点间的最短路径。
－
CLRS那本书当中的Dijkstra's algorithm则是指：
找出一点到图中各点的最短路径。
这个演算法同时运用了greedy method和dynamic programming。
－
※ 引述《oohay (五黑)》之铭言：
: Dijkstra在1959年刊登在Numerische Mathematik 1, 269-271的最短路径算法,
: 题为 A Note on Two Problems in Connexion with Graphs
: 与前几篇文章所提的似乎有些出入. 或许是原典与後续改善者之间的差别吧.
我猜是这样：
这个找最短路径的点子一开始是由Dijkstra阿伯所想的，
後人利用他的点子，衍生出了一套完整的最短路径演算法。
一方面由於点子是Dijkstra阿伯所想的，一方面也为了纪念Dijkstra阿伯，
所以就把这演算法叫做Dijkstra's Algorithm。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.216.102.24
1F：→ oohay:不,Dijkstra认为那是谁都知道的方法,并不是从他开始 02/18 00:02
2F：→ oohay:他那篇文章二页半,第一页是问题ㄧ,第二页是问题二,问题二那 02/18 00:27
3F：→ oohay:一页读了十几次才习惯他的语言,讲得很口语反而难读,而且方法 02/18 00:29
4F：→ oohay:在其他演算法或DP书上没看过 02/18 00:31