以下这几个算法,是当时学习算法的时候总结的。今天整理过去纸质资料的时候发现的。这里面的内容,很多都已经看不懂了。
现在整理了一下,不为别的,只为了告诉自己:你曾经搞过怎么变态的一些算法分析,还有什么比这个更难的么?
特别说明的是,这里面的算法我没有具体用代码实现过,当时是为了分析时间复杂度和空间复杂度而整理的伪代码。特别是Dijkstra算法,可能都不是完整的,遗憾归遗憾,现在实在是没有心思整理完整的算法描述了……
#Prim算法(普利姆)
##定义
从图的顶点集合V中任意选择一个单顶点,作为序列中的初始子树,每次迭代时,选择不在树中的最近的顶点加入到树中。
算法描述
1 2 3 4 5 6 7 8 9 10 11 12 13
| Prim(G) 输入:加权连通图 G=<V,E> 输出:Et, 组成G的MST边的集合 BEGIN Vt = {Vo};// 可以用热议低昂点来初始化树的顶点集合 Et = {∅}; for i in [1..|V|-1) 在所有的边(v,u)中,求权重最小的边 e' = (v', u'),使v在Vt中,而u在V-Vt中; Vt = Vt ∪ {u'}; Et = Et ∪ {e'}l end for return Et; END
|
Kruscal算法(克鲁斯卡尔)
定义
算法开始时,按照权重的非递减顺序对图中的边进行排序,然后从一个空子图开始扫描这个有序列表,并试图把列表中的下一条边加到当前的子图中,如果产生回路,则跳过。
算法描述
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| Kruscal(G) 输入:加权连通图 G=<V, E> 输出:Et,组成G的MST的边的集合 BEGIN 按照边的权重 w(ei1 ≤ ... ≤ ei|E|)的非递减顺序对E排序; Et={∅}; ec = 0; k = 0; while ec < |v| - 1 k++; if Et ∪ {ejk} 无回路 Et = Et ∪ {ejk}; ec++; end if end while return Et; END
|
Floyd算法(弗洛伊德)
定义
- k=0, dij[0] = wij
- k≥1, dij[k] = min{dij[k-1], dik[k-1]+dkj[k-1]}
把当前距离矩阵D[k-1]中的第i行第j列元素替换为第i行第k列元素和第k行第j列元素的和,当且仅当后者的和小于它的当前值
算法描述
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| Floyd(w[1..n, 1..n]) 输入:图的权重矩阵w 输出:包含最短路径长度的距离矩阵D BEGIN D=w; for k in [1..n] for i in [1..n] for j in [1..n] D[i,j]=min{D[i,j], D[i,k]+D[k,j]} end for end for end for return D; END ```language
|
Dijkstra算法(迪杰斯特拉)
定义
顶点标记 v(f, d):
- d:目前求出从起点到该顶点键间最短路径长度
- f:这条路径上倒数第二个顶点的名字
算法只需找到具有最小的d值得边缘顶点就可以,确定加入u’后:把u’从边缘集合移到树集合,对于余下的每一个边缘u,如果通过w(u’, u)的边与u’相连,当du’ + w(u’, u) < du时,更新u的标记为(u’, du+w(u’, u))。
算法描述
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| Dijkstra(G, S) 输入:加权连通图G=<V, E>,以及出发点S 输出:对于V中的每个顶点v来说,从S到V的最短路径长度dv,以及路径上倒数第二个顶点Pv BEGIN Initialize(Q);// 将顶点优先队列初始化为空 for V中的每一个顶点 v dv = ∞; pv = null; Insert(Q, V, dv);// 初始化优先队列中顶点的优先度 end for ds = 0; Decrease(Q, S, ds);// 将s的优先级更新为ds Vt = ∅; for i in [0..|v|-1) u' = DeleteMin(Q);// 删除优先级最小的元素 Vt = Vt ∪ {u'}; for V-Vt中每一个与u'相邻的顶点u if du' + w(u', u) < du du = du' + w(u', u); Pu = u'; Decrease(Q, u, du);// 将u的优先级更新为du end if end for end for END
|