1、最小生成树
在一个连通网的所有生成树中，各边的代价之和最小的那颗生成树称为该连通网的最小代价生成树，简称为最小生成树。
1.1 普里姆算法（加点法）
假设N=（V，{E}）是连通网，TE为最小生成树中边的集合。
①初始U={u0}（u0∈V），TE=∅；
②在所有u∈U，v∈V-U的边中选一条代价最小的边（u0，v0）并入集合TE，同时将v0并入U；
③重复②，直到U=V为止。
此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。
1.2 克鲁斯卡尔算法（加边法）
假设N={V，{E}}是连通网，将N中的边按权值从小到大的顺序排列。
①将n个顶点看成n个集合；
②按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中，同时将改变的两个顶点所在的顶点集合合并；
③重复②直到所有的顶点都在同一个顶点集合内。
2、拓扑排序
用顶点表示活动，用弧表示活动间的优先关系的有向无环图（DAG），称为顶点表示活动的网（Activity On Vertex Network），简称为AOV-网。
有向无环图的拓扑排序的基本思想如下：
①从有向图中选一个无前驱的结点输出；
②将此结点和以它为起点的边删除；
③重复①、②，直到不存在无前驱的结点；
④若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。
算法思想如下：
拓扑排序具体的实现还需考虑图的存储结构。
①首先求出各顶点的入度，并将入度为0的顶点入栈；
②只要栈不空，则重复下面处理：
a.将栈顶顶点i出栈并打印；
b.将顶点i的每一个邻接点k的入度减1，如果顶点k的入度变为0，则将顶点k入栈。
3、关键路径
在AOE-网中存在唯一的、入度为0的顶点，称为源点；存在唯一的、出度为0的顶点，称为汇点。从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径称为关键路径。关键路径上的活动称为关键活动。
在讨论关键路径算法之前，首先给出几个重要的定义。
①事件vi的最早发生时间ve(i):从源点到顶点vi的最长路径的长度，称为事件vi的最早发生时间。
求ve(i)的值可以从源点开始，按拓扑顺序向汇点递推：
ve(0)=0;
ve(i)=Max{ve(k)+＜dutk,i＞}，＜k,i＞∈T,1≤i≤n-1;
其中，T为所有以i为头的弧＜k,i＞的集合，dut（＜k,i＞）表示与弧＜k,i＞对应的活动持续时间。
②事件vi的最晚发生时间vl(i)：在保证汇点按其最早发生时间发生这一前提下，求事件vi的最晚发生时间。
在求出ve(i)的基础上，可从汇点开始，按逆拓扑顺序向源点递推，求出vl(i):
vl(n-1)=ve(n-1);
vl(i)=Min{vl(k)-dut(＜i,k＞)},＜i,k＞∈S,0≤i≤n-2；
其中S为所有以i为尾的弧＜i,k＞的集合，dut(＜i,k＞)表示与弧＜i,k＞对应的活动的持续时间；
③活动ai的最早开始时间e(i):如果活动ai对应的弧为＜j,k＞,则e(i)等于从源点到顶点j的最长路径的长度，即e(i)=ve(j)。
④活动ai的最晚开始时间l(i):如果活动ai对应的弧为＜j,k＞，其持续时间为dut(＜j,k＞),则有l(i)=vl(k)-dut(＜j,k＞)。即在保证事件vk的最晚发生时间为vl(k)的前提下，活动ai的最晚开始时间为l(i)。
⑤活动ai的松弛时间(时间余量):ai的最晚开始时间与ai的最早开始时间之差，即l(i)-e(i)。显然，松弛时间为0的活动为关键活动。
求关键路径的基本步骤：
①对图中顶点进行拓扑排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i);
②按逆拓扑序列求每个事件的最晚发生时间vl(i);
③求出每个活动ai的最早开始时间e(i)和最晚发生时间l(i);
④找出e(i)=l(i)的活动ai，即为关键活动。
利用拓扑排序算法求每个事件的最早发生时间ve(i)的算法思想如下：
①首先求出各顶点的入度，并将入度为0的顶点入栈S；
②将各顶点的最早发生时间ve[i]初始化为0；
③只要栈S不空，则重复下面处理：
a.将栈顶顶点j出栈并压入栈T（生成逆拓扑序列）；
b.将顶点j的每一个邻接点k的入度减1，如果顶点k的入度变为0，则将顶点k入栈；
c.根据顶点j的最早发生时间ve[j]和弧＜j,k＞的权值，更新顶点k的最早发生时间ve[k]。
求关键路径的算法实现如下：
①首先调用修改后的拓扑排序算法，求出每个事件的最早发生时间和逆拓扑序列栈T。
②将各顶点的最晚发生时间vl[i]初始化为汇点的最早发生时间；
③只要栈T不空，则重复下面处理；
a.将栈顶顶点j出栈；
b.对于顶点j的每一个邻接点k，根据顶点k的最晚发生时间vl[k]和弧＜j,k＞的权值，更新顶点j的最晚发生时间vl[j]。
④扫描每一条弧，计算其最早发生时间ei和最晚发生时间li，如果ei等于li则输出该边。
4、最短路径
4.1 迪杰斯特拉算法（单源最短路径）
算法思想如下：
①S←{v0}；
dist[i]=g.arcs[v0][vi].adj;(vi∈V-S)
(将v0到其余顶点的最短路径长度初始化为权值)
②选择vk,使得dist[k]=Min(dist[i] | vi∈V-S),vk为目前求得的下一条从v0出发的最短路径的终点；
③将vk加入S；
④修正从v0出发到集合V-S上任一顶点vi的最短路径的长度：
从v0出发到集合V-S上任一顶点vi的当前最短路径的长度为dist[i],
从v0出发，中间经过新加入S的vk，然后到达集合V-S上任一顶点vi的路径长度为：
dist[k]+g.arcs[k][i].adj
如果dist[k]+g.arcs[k][i].adj＜dist[i],则dist[i]=dist[k]+arcs[k][i].adj。
⑤重复②~④共n-1次，即可按最短路径长度的递增顺序，逐个求出v0到图中其他每个顶点的最短路径。
4.2 弗洛伊德算法（多源最短路径）