Re: [問題] prim's vs dijkstra
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間17年前 (2008/02/17 22:23)推噓0(0推 0噓 4→)留言4則, 1人參與討論串7/8 (看更多)
我剛剛在 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
→
02/18 00:02, , 1F
02/18 00:02, 1F
→
02/18 00:27, , 2F
02/18 00:27, 2F
→
02/18 00:29, , 3F
02/18 00:29, 3F
→
02/18 00:31, , 4F
02/18 00:31, 4F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
