DNA算法是一种模拟DNA分子结构并借助生物分子技术新的计算方法.分子计算这一全新学科逐渐的发展,它在解决数目巨大的并行计算方面和NP完全问题方面优势的明显的.1994年, Adleman首次借助试管实验成功地用分子算法求解出七节点的哈密顿路径问题.DNA算法的实验操作过程是: DNA分子结构为双螺旋结构并且碱基互补配对,所以可以把计算对象映射成DNA分子链,在酶的催化作用下,形成不同的数据池,再把初始数据映射成容易控制的生化操作.最终使用聚合链反应PCR,超声波降解,亲和层析,克隆,诱变,分子纯化,电泳,磁珠分离等检测运算结果.本文分三部分研究DNA算法在解决NP-完全问题方面的应用.第一部分给出了单约束非0-1整数背包问题的DNA计算方法,即对变量取值进行DNA编码并形成所有可能解；用批接入实验,电泳实验得到最优解;通过检测实验输出所有最优解.并例证此算法的可行性.在第二部分中,由于Adleman和Lipton的开创性工作,最近DNA计算引起了人们的极大兴趣,他们提出的分子算法解决了图形的表示方法,但是没有给出如何处理图中节点的弧线的信息.本文的目的是通过提出在图中城市间的距离用简单的弧线代表,延伸了Adleman和Lipton提出的基本的分子算法.并提出只有当算法步骤由当前的需要人工干预被可执行的可在试管中操作的DN瞄代替,解决计算难题的真正可行DNA计算可以实现.第三部分给出了一种新的计算模型求解最短路径问题.