最短路径

举了个地铁图的例子
网络中两定点间的所有路径中，边权值之和最小的那条即为最短路径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网络，关键路径由绝对不允许延误的活动组成的路径，没有机动时间的路径组成的路径就是关键路径。