最小点覆盖问题,是指给定一个无向图G=(V,E),其中V为顶点集,E为边集,求顶点集V的一个最小子集S,使得对于边集E的任意一条边uv∈E,有u∈S或v∈S.最小点覆盖问题是组合优化中一个典型的NP完全问题,因其有着广泛的应用,所以备受关注.至今虽然已经有很多求解该问题的近似算法,但许多人仍致力于最小点覆盖的研究,以便寻求更简洁、更精确的算法.　　因此,本文利用经典的最短路算法Dijkstra算法和蚁群算法对最小点覆盖问题分别进行了研究,具体内容如下：　　（1）基于最短路算法,分别研究了无权图与赋权图的最小点覆盖问题,并设计了算法.首先,在给定的图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.　　（2）关于蚁群算法,研究了赋权图的最小点覆盖问题.给出了一个基于蚁群算法的近似算法,求解最小点覆盖问题的近似解.通过修改蚂蚁的状态转移概率公式,简化状态转移规则,建立了相应的数学模型,从而得出求解最小点覆盖的近似算法步骤,最后进行了实例解析.　　（3）将最小点覆盖问题应用到求解停车场选址问题中.利用已获得的近似算法,对停车场选址问题进行了求解,并且给出了停车场选址问题的较优方案.