Re: [問題] 關於最短路徑
看板C_and_CPP (C/C++)作者guest0079 (火辣辣的大姊姊)時間16年前 (2009/08/17 01:56)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《hsm926 (韓森慢)》之銘言：
: 通常學過的最短路徑演算法
: 好像都是算s 起始點到 t 終點的最短路徑
: 有沒有可以算 例如輸入5點(有權重的圖)
: 要都走過 可重複走 然後是最短的路徑的演算法
: 或者用什麼演算法變型可以作到?
: 感謝！
不好意思，騙騙文章數，再一篇就可以去八掛版發廢文了
先用最短路徑演算法得出所有任兩點之間的最短路徑，得一路徑矩陣
N個點應該會有n(n-1)/2次的最短路徑計算量（約n^2）
再把該問題視為TSP問題解之
由n(n＋1)/2改為n(n－1)/2
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.220.208
推
08/17 02:00, , 1F
08/17 02:00, 1F
※ 編輯: guest0079 來自: 220.136.220.208 (08/17 02:05)
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
