单源最短路径（贪心算法）报告.doc
需积分: 49 75 浏览量
2019-12-26
16:37:40
上传
评论 1
收藏 74KB DOC 举报
实验十一：单源最短路径（贪心算法）报告
2017061111 李静娴
1．问题描述
给定带权有向图 G =(V,E)，其中每条边的权是非负实数。另外，还给定 V 中的一个顶点，称
为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之
和。这个问题通常称为单源最短路径问题。
2．实验目的
（1）熟悉贪心算法，并学以致用
（2）熟练掌握单源最短路径算法
3．实验原理
Dijkstra 算法是解单源最短路径问题的贪心算法。
其基本思想是，设置顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合 S
当且仅当从源到该顶点的最短路径长度已知。初始时，S 中仅含有源。设 u 是 G 的某一个
顶点，把从源到 u 且中间只经过 S 中顶点的路称为从源到 u 的特殊路径，并用数组 dist 记
录当前每个顶点所对应的最短特殊路径长度。Dijkstra 算法每次从 V-S 中取出具有最短特殊
路长度的顶点 u，将 u 添加到 S 中，同时对数组 dist 作必要的修改。一旦 S 包含了所有 V 中
顶点，dist 就记录了从源到所有其他顶点之间的最短路径长度。
Dijkstra 算法可描述如下，其中输入带权有向图是 G=(V,E)，V={1,2,… ，n}，顶点 v 是源。
c 是一个二维数组，c[i][j]表示边(i,j)的权。当(i,j)不属于 E 时，c[i][j]是一个大数。dist[i]表示
当前从源到顶点 i 的最短特殊路径长度。在 Dijkstra 算法中做贪心选择时，实际上是考虑当
S 添加 u 之后，可能出现一条到顶点的新的特殊路，如果这条新特殊路是先经过老的 S 到达
顶点 u,然后从 u 经过一条边直接到达顶点 i，则这种路的最短长度是 dist[u]+c[u][i]。如果
dist[u]+c[u][i]<dist[i]，则需要更新 dist[i]的值。步骤如下：
(1) 用带权的邻接矩阵 c 来表示带权有向图, c[i][j]表示弧<vi,vj>上的权值。设 S 为已知最
短路径的终点的集合,它的初始状态为空集。从源点 v 经过 S 到图上其余各点 vi 的当前最短
路径长度的初值为：dist[i]=c[v][i], vi 属于 V.
(2) 选择 vu, 使得 dist[u]=Min{dist[i] | vi 属于 V-S},vj 就是长度最短的最短路径的终点。令
S=S U {u}.
(3) 修改从 v 到集合 V-S 上任一顶点 vi 的当前最短路径长度:如果 dist[u]+c[u][j]< dist[j] 则修
改 dist[j]= dist[u]+c[u][j].
(4) 重复操作(2),(3)共 n-1 次。
算法的时间复杂度：
O((E+V)lgV
)
空间复杂度：
O(E)
对于一个图
G(V,E)
来说，
V
是顶点，
E
是边。
4．实验设计
资源评论
