[1] 周康,同小军,许进.路径排序问题基于表面的DNA算法[J].华中科技大学学报自然科学版, 2005,33(8) 100－103.
［2］ 周康,同小军,刘文斌,等.最短路问题的闭环DNA算法[J].系统工程与电子技术,2008,30(3)556－560.
［3］ 许珀温,罗森贝格,萨洛马.DNA计算一种新的计算模式[M].许进,王淑栋,潘林强,译.北京清华大学出版社,2004.DNA Algorithm for Shortest Path Problem of Undirected GraphBased on Sticker SystemsNIE Xiao－yan1, GENG Jun2, TANG Jian－gang1(1.School of Mathematics and Statistics, Yili Normal University, Yili 835000, Xinjiang, China;2.Department of Mathematics, Kashi Normal University, Kashi 844006, Xinjiang, China)Abstract Proposed a new project of DNA computing model to solve the shortest path problem of fixed start point and end point of undirected graph, In this DNA algorithm,two opposite directed edge took place of each side of undirected graph, so changed the undirected graph into directed graph, And all paths of fixed start and end point are obtained by taking use of parallelism of sticker systems.Then can take the shortest path by some molecular biology technology, such as probe, electrophoresis, and so on.An example is applied to illustrate the feasibility of the DNA algorithm.Key words DNA computing; sticker systems; shortest path problem |
