[問題] xy平面點最短距離問題

[oo855050 (阿偉)]

版上各位好，
小弟想請教一個問題
如圖下圖所示，我有好幾個橘色點(分別有各自的xy座標)
https://imgur.com/VJhyQeO
而我想做到指定起點後依照最短路徑點做連接
最終將其全部連接完畢
請問有什麼好的演算方法可以做到這件事嗎(時間複雜度盡量低)

網上搜尋有找到
廣度優先搜尋、深度優先搜尋、dijkstra等演算法似乎是在解決最短路徑問題
但小弟才疏學淺不曉得這幾種演算法是否有機會適用到我的問題上
希望版上大大幫解惑QQ
感激不盡!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.169.144.155 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1583166425.A.FC0.html
→ Hsins: 有，但你要會用呀。先決定問題再決定資料儲存方式，最後才
→ Hsins: 是演算法，至於挑選哪個？根據你的問題和資料特性都會不同
→ Hsins: ，就看你要不要花時間下去。
→ aassdd926: dijkstra 可以，只是你要先建立點與點之間的路徑，如
→ aassdd926: 果不想實作，可以看看networkx
推 TitanEric: 這是TSP吧 NP hard問題不要覺得有高效演算法
→ TitanEric: 但是concorde可以參考一下
→ TitanEric: 補充一下 你這問題不像TSP要回第一個點 但也可能我會
→ TitanEric: 有poly time演算法
→ oo855050: Hs大，摁摁了解了 感謝!
→ oo855050: aas大，摁摁dijkstra感覺是可行的，只不過我考慮到時間
→ oo855050: 複雜度的問題，所以在想是否有更好的選擇方法
→ oo855050: Ti大，其實我的需求應該是要讓他回第一點
→ oo855050: 我會再看看你說的TSP方法，感謝!