Zoj*_*shi 5 algorithm graph graph-algorithm
我有一个有 500 个顶点的全连接图（无向图）。这会产生一个包含 250,000 个条目的矩阵（只有 125,000 个是必需的，因为它是无向的）。
每条边都有特定的权重。如果我只能访问 n < 500 的 n 个顶点，是否可以找到哪个起始顶点和哪个路径将导致最高的总权重。
这有可能在任何合理的时间内解决吗？
谢谢！
您描述的问题最终会成为 NP 难题（通过最长路径问题的简化），因此除非 P = NP，否则不会有任何算法在所有输入上都是正确的并且在所有输入上都有效。您要么需要愿意接受并不总是正确的答案（但可能大致接近），要么需要考虑在某些情况下很快但在其他情况下相当慢的算法。
只要路径不太长，有些算法就可以很好地解决这个问题。例如，如果最大路径长度不太长，颜色编码算法就可以很好地工作，但我担心长度 500 在这里会太大。快速谷歌搜索发现了这篇论文，其中包含一种用于在图中查找相当长的路径的算法，并且可能适用于此。但除此之外，您可能只需要进行一些随机抽样并希望一切顺利。
如果您对图有更多了解 - 例如，如果边遵守三角不等式或者如果边都具有某个小的有限范围内的值 - 您也许可以使用其他方法。但除此之外，恐怕你不会有太多选择。
对此感到抱歉，但希望这会有所帮助！