文章目录
  1. 1. 算法描述
  • Kruscal算法(克鲁斯卡尔)
    1. 1. 定义
    2. 2. 算法描述
  • Floyd算法(弗洛伊德)
    1. 1. 定义
    2. 2. 算法描述
  • Dijkstra算法(迪杰斯特拉)
    1. 1. 定义
    2. 2. 算法描述
  • 以下这几个算法,是当时学习算法的时候总结的。今天整理过去纸质资料的时候发现的。这里面的内容,很多都已经看不懂了。

    现在整理了一下,不为别的,只为了告诉自己:你曾经搞过怎么变态的一些算法分析,还有什么比这个更难的么?

    特别说明的是,这里面的算法我没有具体用代码实现过,当时是为了分析时间复杂度和空间复杂度而整理的伪代码。特别是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
    文章目录
    1. 1. 算法描述
  • Kruscal算法(克鲁斯卡尔)
    1. 1. 定义
    2. 2. 算法描述
  • Floyd算法(弗洛伊德)
    1. 1. 定义
    2. 2. 算法描述
  • Dijkstra算法(迪杰斯特拉)
    1. 1. 定义
    2. 2. 算法描述