c - 从完整图计算最短路径

Question

我有一个矩阵 NxN，其中是无向图中顶点和jmatrice[i][j]之间的边的成本。if

我需要确定的是包含矩阵中所有顶点的最短路径。

所以对于像这样的输入：

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

我需要尝试所有可能的路径，在这种情况下：

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

是正确的，长度为 998。

我该如何实施？

Answer 1

您正在描述被广泛研究的旅行推销员问题。

虽然有很多方法可以近似解决方案 - 确切的解决方案确实需要指数运行时间，并且蛮力是解决它的一种选择（在 O 中(n!)）。

这个想法是生成所有可能的排列并评估每个排列 - 并找到最小值。
例如，这个问题讨论了如何生成所有排列。同样的想法也适用于您的问题。

可以进行一些可能的优化，例如分支定界技术 - 或使用智能DP解决方案。