從完整圖計算最短路徑

Question

我有一個矩陣NxN其中matrice[i][j]是在非方向圖中頂點i和f j之間的邊的代價。

我需要確定的是最短路徑，其中包含矩陣中的所有頂點 。

因此，對於輸入，如：

0 198 67 368 
198 0 131 432 
67 131 0 301 
368 432 301 0 

我需要嘗試更多鈔票的所有路徑，並在這種情況下：

0-->1-->2-->3-->0 

是正確至極給人長度998

我如何能實現這個？

Answer 1

您正在描述被廣泛研究的Traveling Salesman Problem。

雖然有很多方法來近似解決方案 - 確切的解決方案確實需要指數運行時間，而蠻力是解決它的一個選項（在O (n!)中）。

這個想法是產生所有可能的排列和評估每個 - 並找到最小值。例如
This question討論如何生成所有排列。相同的想法適用於您的問題。

可以進行一些可能的優化，例如branch & bound技術 - 或者使用智能DP解決方案。