最短路问题的解法及应用.docx

摘要：不仅是最短路问题本身在我们的社会生活中有十分广泛的应用，而且，最短路问题也可以作为一种工具，去解决其他的优化问题，因此，深入研究最短路问题是非常有必要的. 本文讲解了贪心算法（Floyd 算法）和动态规划（Dijkstra 算法）这两种经典算法的原理，以实例进行分析并对比了两种算法的异同点. 除此之外，还分别用着两种算法解决了实际问题. 

关键词：单源最短路径，贪心算法，动态规划. 

目录

摘要

Abstract

1 引言  1

1.1产生 1

1.2引例 2

2 方法原理  4

2.1 贪心算法  4

2.2 动态规划算法  7

3 实际应用  9

参考文献   15