給定一 connected graph， 每個邊 （edge） 附屬一正整數代表該邊的距離 。 下列何者至今尚無polynomial time的演算法以求解？
A給定任一節點（vertex）a，求 a 至所有其他節點的最短路徑
B尋找一最短路徑，以通過所有的節點剛好各一次正確答案
C求出所有節點相互間的最短路徑
D找出一 spanning tree，使其邊的距離加總為最小
答案與詳解
為什麼答案是 B
等同 TSP / Hamiltonian Path，屬 NP-hard，至今無多項式時間演算法，為正解。
載入中…
