最短路径
举了个地铁图的例子
网络中两定点间的所有路径中，边权值之和最小的那条即为最短路径shortest path
source -> destination
分为：
无权单源
void Unweighted ( Vertex S ){ //无权图的单源最短路径
/*
先初始下列初始化
dist[W] = S到W的最短距离
dist[S] = 0; //S自己到自己的距离为0
path[W] = S到W的路上经过的顶点
*/
Enqueue(S, Q); //源结点入队
while(!IsEmpty(Q)){
V = Dequeue(Q); //出队，此时最短路已被找到
for ( V 的每个邻接点 W )
if ( dist[W]==-1 ) { //假设-1为未访问过的初始值，于是访问它
dist[W] = dist[V]+1; //前结点到S距离+1
path[W] = V; //V是必经的顶点，经过堆栈处理可打印出最短路径经过的结点
Enqueue(W, Q);
}
}
}
//用邻接表存储T = O(|V|+|E|)
有权单源
Dijkstra算法
以起始点为中心向外层层扩展，直到扩展到终点为止
void Dijkstra( Vertex s ){
/*
S = { 源点s + 已经确定了最短路径的顶点vi }
dist[v] = s到v[仅经过S中的各顶点]的最短路径长度，即路径{s->(vi属于S)->v}的最小长度
dist[w] = min{dist[w], dist[v] + <v,w>的权重}
dist[s] = 0;
*/
while (1) {
V = 未收录顶点中dist最小者;
if ( 这样的V不存在 )
break;
collected[V] = true; //V被收录
for ( V 的每个邻接点 W )
if ( collected[W] == false ) //W未被收录
if ( dist[V]+E<V,W> < dist[W] ) { //dist被初始化为正无穷
dist[W] = dist[V] + E<V,W> ;
path[W] = V;
}
}
} /* 不能解决有负边的情况 */
// 法1.直接扫描所有未收录顶点 – O( |V| )
// T = O( |V|*|V| + |E| ) 对于稠密图效果好
// 法2.将dist存在最小堆中 – O( log|V| )
// 更新dist[w]的值 – O( log|V| )
// T = O( |V| log|V| + |E| log|V| ) = O( |E| log|V| ) 对于稀疏图效果好
有权多源
法1.对于稀疏图效果好
将单源最短路算法调用|V|遍，对每一个顶点调用Dijkstra算法
T = O( |V||V||V| + |E||V|)
法2.Floyd算法*
void Floyd(){
//求多源最短路径
for ( i = 0; i < N; i++ )
for( j = 0; j < N; j++ ) {
D[i][j] = G[i][j]; /*Dij为i到j的最小距离；初始化为其邻接矩阵，对角线为0，其他为两边的权值，不相邻为正无穷*/
path[i][j] = -1; //最短路径初始化-1
}
for( k = 0; k < N; k++ ) /*D0 -> Dk ，包含k个结点时，i到j的最小值，当k从0->n-1则说明遍历了整个图*/
for( i = 0; i < N; i++ )
for( j = 0; j < N; j++ )
if( D[i][k] + D[k][j] < D[i][j] ) { /*若k加入后是更小的值，则必是i到k和k到j最短路径的和*/
D[i][j] = D[i][k] + D[k][j]; /*若更小则更新*/
path[i][j] = k; // i -> k -> j
}
}
// T = O( |V|3 ) 对于稠密图效果好
最小生成树
树：无回路，V个顶点且有V-1条边
生成树：包含全部顶点，V-1条边全在图里
最小生成树：边的权重和最小
思路：贪心算法
每一步都是最好的
Prim算法
void Prim(){
MST = {s}; //初始化一棵最小生成树，选了个根结点S
while (1) {
V = 未收录顶点中dist最小者; //顶点V到最小生成树（上的所有顶点）的最小距离dist
if ( 这样的V不存在 ) //没有没收录的顶点了，或多有没收录的顶点都没边了（不连通）
break;
将V收录进MST: dist[V] = 0; //变成树本身，距离为0
for ( V 的每个邻接点 W )
if ( dist[W]!=0 ) //说明W未被收录
if ( E(V,W) < dist[W] ){
dist[W] = E(V,W) ;
parent[W] = V; //V可能是W的parent？
}
}
if ( MST中收的顶点不到|V|个 ) //（不连通）
Error ( “生成树不存在” );
}//T = O( V*V )稠密图合算
Kruskal算法
思路：把森林合并成树
初始每个顶点都是一棵树，通过不断收边，两棵树并成一颗树，直至全部并成一棵树。但要注意保持最小生成树的3个性质（前面有提到）
void Kruskal ( Graph G ){
MST = { } ; //一开始一条边都没有
while ( MST 中不到 |V|-1 条边 && E 中还有边 ) { //E是所有边的集 最坏情况O（|V|-1）次
从 E 中取一条权重最小的边 E(v,w) ; /*最小堆 O（logE）取出最小边*/
将 E(v,w)从 E 中删除;
if ( E(V,W)不在 MST 中构成回路) /*并查集 V和W分别属于不同集合则不会构成回路*/
将 E(V,W) 加入 MST;
else
彻底无视 E(V,W);
}
if ( MST 中不到 |V| 1 条边 )
Error ( “生成树不存在” );
}
//T = O( |E|*log|E| )稀疏图合算 即E约等于V时，约定于T = O( |V|*log|V| )比Prime快一点
拓扑结构
如果图中从V到W有一条有向路径，则V一定排在W之前。满足此条件的顶点序列，称为一个拓扑序。
AOV必须是有向无环图DAG。
<pre>void TopSort(){
for ( cnt = 0; cnt < |V|; cnt++ ) {
V = 未被输出的 && 入度为0的顶点; //普通方法O(|V|），则整体T=O（V*V）。
if ( 这样的V不存在 ) { //必定有回路
Error ( “图中有回路” );
break;
}
输出V，或者记录V的输出序号;
for ( V 的每个邻接点 W )
Indegree[W]––; //入度-1，即V-W这条边去掉
}
}//普通方法O(|V|），则整体T=O（|V|*|V|）。
</pre>
<pre>//改进将入度变为0的顶点放到一个容器里，下次从容器里取出即可，加快V的查找
void TopSort(){
for ( 图中每个顶点 V )
if ( Indegree[V]==0 )
Enqueue( V, Q ); //这里的容器用队列
while ( !IsEmpty(Q) ) {
V = Dequeue( Q ); //容器里取出入度为0的顶点
输出V，或者记录V的输出序号;
cnt++; //记录输出的顶点个数
for ( V 的每个邻接点 W )
if ( ––Indegree[W]==0 ) //邻接点入度-1，但要检查是否减完后变为0
Enqueue( W, Q ); //若为0再放入容器
}
if ( cnt != |V| ) //还有顶点留在图里
Error( “图中有回路” );
}//T=O（|V|+|E|） 可用来检测DAG
</pre>
拓扑排序的应用
关键路径问题
- AOV网络（Activity On vertex)
- AOE网络 (Activity On Edge)
这里讨论AOE网络，关键路径由绝对不允许延误的活动组成的路径，没有机动时间的路径组成的路径就是关键路径。
