→ oohay:不,Dijkstra認為那是誰都知道的方法,並不是從他開始 02/18 00:02
→ oohay:他那篇文章二頁半,第一頁是問題ㄧ,第二頁是問題二,問題二那 02/18 00:27
→ oohay:一頁讀了十幾次才習慣他的語言,講得很口語反而難讀,而且方法 02/18 00:29
→ oohay:在其他演算法或DP書上沒看過 02/18 00:31
我剛剛在 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