最短路算法及其 应用.doc

最短路算法及其应用 广东北江中学 余远铭 摘要 最短路问题是图论中的核心问题之一它是许多更深层算法的基础同时该问题有着大量的生产实际的背景不少问题从表面上看与最短路问题没有什么关系却也可以归结为最短路问题本文较详尽地介绍了相关的基本概念常用算法及其适用范围并对其应用做出了举例说明侧重于模型的建立思考和证明的过程最后作出总结 关键字 最短路 目录 TOC \o "1-3" \h 22204一基本概念