[問題] 請問最短路徑演算法如何儲存路徑？

看板C_and_CPP作者 (yem)時間14年前 (2010/05/28 01:12), 編輯推噓3(3推 0噓 6→)
留言9則, 6人參與, 最新討論串1/1
遇到的問題： 有一張圖形結構的節點圖,需要求出最短路徑,並存下該路徑經過的節點 希望得到的正確結果： 得到最短路徑,並存下節點 程式跑出來的錯誤結果： 我用Dijkstra演算法算出最短路徑後,再用暴力法探訪每個路徑,找出最短路徑 存在的節點,老師要求我不使用暴力法,因為效率問題 開發平台： DEV C++ 補充說明： 因為小弟我本身不是資工類別的科系,所以可能要請前輩們稍微講得比較詳細一 點,關於這個問題有哪些比較好的解法呢？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.44.207.231
→
05/28 01:22, , 1F
上網查 Travelling salesman problem?
05/28 01:22, 1F
推
05/28 01:34, , 2F
樓上猜錯了 他是想找 Dijkstra 找出來的那條路
05/28 01:34, 2F
→
05/28 01:35, , 3F
給原 PO 提示: 每個節點的那個距離值總是由別的節點計算來的
05/28 01:35, 3F
→
05/28 01:35, , 4F
那麼如果一直追它是怎麼算出來的話...?
05/28 01:35, 4F
推
05/28 01:40, , 5F
推樓上，只要記錄前一個節點是誰就好
05/28 01:40, 5F
→
05/28 01:45, , 6F
哦對欸！沒說要每個點都走過... 我笨了 = ="
05/28 01:45, 6F
→
05/28 02:28, , 7F
好像想到該怎麼做了..感謝！！
05/28 02:28, 7F
推
05/30 16:01, , 8F
存Tree Edge
05/30 16:01, 8F
→
05/30 23:41, , 9F
每個點更新最短距離時順便存 parent 是誰
05/30 23:41, 9F
‣ 更多 a149851571 的文章
文章代碼(AID): #1B_gW9UB (C_and_CPP)