問JAVA 圖（graph)的算法（最大回路）(重新解釋）

來源: 市井之徒 於 2007-07-28 22:00:31 [] [舊帖] [給我悄悄話] 閱讀數 : (565 bytes)

simple, weighted,undirected graph
我會求 最短距離和最小生成數
但 要求是 要算一個 maximal limited cycle （最大限製回路）
意思為 給出一個起點和一個 weight總數，所謂“限製回路” 就是要從起點開始出發 遍曆，最後回到起點，最後要得出一個回路，其所遍曆的所有路徑的weight總和不能超過所給出的 weight總數。而其中走過最多節點的 就是最大限製回路

舉例就是： 大家一起開車從多倫多出發 每人一缸油，隻能往前開（不能走曾經走過的路），要 走的盡量遠 盡量多城市， 但要保證最後能開回多倫多， 最後走過最多城市而又回到多倫多的， 其所走路線就是最大限製回路。 求算法。謝謝

所有跟帖： 

請您先登陸，再發跟帖！