最短路径算法—Dijkstra(迪杰斯特拉)算法分析与实现(CC++)

5星 · 超过95%的资源
所需积分/C币: 48
浏览量·759
DOCX
19KB
2012-05-11 22:23:18 上传
wanwan0429
  • 粉丝: 0
  • 资源: 3
前往需求广场,查看用户热搜
上传资源 快速赚钱
精品专辑
内容简介:Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra 算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。  Dijkstra 算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。其基本思想是,设置顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。初始时,S 中仅含有源。设 u 是 G 的某一个顶点,把从源到 u 且中间只经过 S 中顶点的路称为从...