改进的Prim算法在求解旅行商问题中的应用

摘要

旅行商问题是图论中一个典型的组合优化问题，它的问题描述与图论中最小生成树问题的描述具有很多相似之处，在一些情形下，可以用最小生成树形成的路径来获得旅行商问题的最短巡回路径。首先给出了最小生成树Prim算法，然后对其算法进行了改进，通过改进的Prim算法成功求解了旅行商问题。