点击下载课件

最短途径

Dijksra算法

1.问题描述

2.基本思想

3.Dijksra 算法伪代码

4.Dijksra算法图示

5.算法的代码实现

6.例题CHDOJ 2244

Bellman-ford算法

1.算法思想

2.算法流程

3.算法的代码实现

4.例题Acwing 853.有边数限制的最短路

Floyd算法

1.算法思路

2.算法的代码实现

3.例题Acwing 854.Floyd求最短路

最小生成树

一、Prim算法

1.基本思想

2.Prim算法伪代码

3.Prim算法图示

4.算法的代码实现

5.例题ACwing 858.Prim算法求最小生成树

二、Kruskal算法（破圈发，并查集的应用）

1.基本思想

2.Kruskal算法伪代码

3.Kruskal算法图示

4.算法的代码实现

5.例题Acwing 859.Kruskal算法求最小生成树

最近公共祖先（LCA）

一、倍增

1.算法思路

2.例题P3379最近公共祖先（LCA）

二、Tarjan算法（离线）

1.基本思想（DFS遍历）

2.算法的伪代码

3.算法图示

主讲人：田宇