最短路徑

舉了個(gè)地鐵圖的例子
網(wǎng)絡(luò)中兩定點(diǎn)間的所有路徑中，邊權(quán)值之和最小的那條即為最短路徑shortest path
source -> destination
分為：

無(wú)權(quán)單源

void Unweighted ( Vertex S ){ //無(wú)權(quán)圖的單源最短路徑
    /*
    先初始下列初始化
    dist[W] = S到W的最短距離
    dist[S] = 0; //S自己到自己的距離為0
    path[W] = S到W的路上經(jīng)過的頂點(diǎn)
    */
    Enqueue(S, Q);    //源結(jié)點(diǎn)入隊(duì)
    while(!IsEmpty(Q)){ 
        V = Dequeue(Q);     //出隊(duì)，此時(shí)最短路已被找到
        for ( V 的每個(gè)鄰接點(diǎn) W )
            if ( dist[W]==-1 ) {    //假設(shè)-1為未訪問過的初始值，于是訪問它
                dist[W] = dist[V]+1;    //前結(jié)點(diǎn)到S距離+1
                path[W] = V;    //V是必經(jīng)的頂點(diǎn)，經(jīng)過堆棧處理可打印出最短路徑經(jīng)過的結(jié)點(diǎn)
                Enqueue(W, Q);
            }
    }
}
//用鄰接表存儲(chǔ)T = O(|V|+|E|)

有權(quán)單源

Dijkstra算法
以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止

void Dijkstra( Vertex s ){ 
    /*
    S = { 源點(diǎn)s + 已經(jīng)確定了最短路徑的頂點(diǎn)vi }
    dist[v] = s到v[僅經(jīng)過S中的各頂點(diǎn)]的最短路徑長(zhǎng)度，即路徑{s->(vi屬于S)->v}的最小長(zhǎng)度
    dist[w] = min{dist[w], dist[v] + <v,w>的權(quán)重}
    dist[s] = 0;
    */
    while (1) {
    V = 未收錄頂點(diǎn)中dist最小者;
    if ( 這樣的V不存在 )
        break;
    collected[V] = true;    //V被收錄
    for ( V 的每個(gè)鄰接點(diǎn) W )
        if ( collected[W] == false )    //W未被收錄
        if ( dist[V]+E<V,W> < dist[W] ) {   //dist被初始化為正無(wú)窮
        dist[W] = dist[V] + E<V,W> ;
        path[W] = V;
        }
    }
} /* 不能解決有負(fù)邊的情況 */
// 法1.直接掃描所有未收錄頂點(diǎn) – O( |V| )
// T = O( |V|*|V| + |E| ) 對(duì)于稠密圖效果好
// 法2.將dist存在最小堆中 – O( log|V| )
// 更新dist[w]的值 – O( log|V| )
// T = O( |V| log|V| + |E| log|V| ) = O( |E| log|V| ) 對(duì)于稀疏圖效果好

有權(quán)多源

法1.對(duì)于稀疏圖效果好
將單源最短路算法調(diào)用|V|遍，對(duì)每一個(gè)頂點(diǎn)調(diào)用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(luò)的最小距離；初始化為其鄰接矩陣，對(duì)角線為0，其他為兩邊的權(quán)值，不相鄰為正無(wú)窮*/
        path[i][j] = -1;    //最短路徑初始化-1
        }
    for( k = 0; k < N; k++ )    /*D0 -> Dk ，包含k個(gè)結(jié)點(diǎn)時(shí)，i到j(luò)的最小值，當(dāng)k從0->n-1則說(shuō)明遍歷了整個(gè)圖*/
        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(luò)最短路徑的和*/
                    D[i][j] = D[i][k] + D[k][j];    /*若更小則更新*/
                    path[i][j] = k; // i -> k -> j
                }
}
// T = O( |V|3 ) 對(duì)于稠密圖效果好

最小生成樹

樹：無(wú)回路，V個(gè)頂點(diǎn)且有V-1條邊
生成樹：包含全部頂點(diǎn)，V-1條邊全在圖里
最小生成樹：邊的權(quán)重和最小
思路：貪心算法
每一步都是最好的

Prim算法

void Prim(){ 
    MST = {s};  //初始化一棵最小生成樹，選了個(gè)根結(jié)點(diǎn)S
    while (1) {
        V = 未收錄頂點(diǎn)中dist最小者;  //頂點(diǎn)V到最小生成樹（上的所有頂點(diǎn)）的最小距離dist
        if ( 這樣的V不存在 )  //沒有沒收錄的頂點(diǎn)了，或多有沒收錄的頂點(diǎn)都沒邊了（不連通）
            break;
        將V收錄進(jìn)MST: dist[V] = 0;  //變成樹本身，距離為0
        for ( V 的每個(gè)鄰接點(diǎn) W )
            if ( dist[W]!=0 )    //說(shuō)明W未被收錄
                if ( E(V,W) < dist[W] ){
                    dist[W] = E(V,W) ;
                    parent[W] = V;  //V可能是W的parent？
                }
    }
    if ( MST中收的頂點(diǎn)不到|V|個(gè) )   //（不連通）
        Error ( “生成樹不存在” );
}//T = O( V*V )稠密圖合算

Kruskal算法

思路：把森林合并成樹
初始每個(gè)頂點(diǎn)都是一棵樹，通過不斷收邊，兩棵樹并成一顆樹，直至全部并成一棵樹。但要注意保持最小生成樹的3個(gè)性質(zhì)（前面有提到）

void Kruskal ( Graph G ){ 
    MST = { } ; //一開始一條邊都沒有
    while ( MST 中不到 |V|-1 條邊 && E 中還有邊 ) {  //E是所有邊的集 最壞情況O（|V|-1）次
        從 E 中取一條權(quán)重最小的邊 E(v,w) ; /*最小堆 O（logE）取出最小邊*/
        將 E(v,w)從 E 中刪除;
        if ( E(V,W)不在 MST 中構(gòu)成回路)    /*并查集 V和W分別屬于不同集合則不會(huì)構(gòu)成回路*/
            將 E(V,W) 加入 MST;
        else
            徹底無(wú)視 E(V,W);    
    }
    if ( MST 中不到 |V| ?1 條邊 )
        Error ( “生成樹不存在” );
}
//T = O( |E|*log|E| )稀疏圖合算 即E約等于V時(shí)，約定于T = O( |V|*log|V| )比Prime快一點(diǎn)

拓?fù)浣Y(jié)構(gòu)

如果圖中從V到W有一條有向路徑，則V一定排在W之前。滿足此條件的頂點(diǎn)序列，稱為一個(gè)拓?fù)湫颉?br> AOV必須是有向無(wú)環(huán)圖DAG。

<pre>void TopSort(){
   for ( cnt = 0; cnt < |V|; cnt++ ) {
       V = 未被輸出的 && 入度為0的頂點(diǎn); //普通方法O(|V|），則整體T=O（V*V）。
       if ( 這樣的V不存在 ) {    //必定有回路
           Error ( “圖中有回路” );
           break;
       }
       輸出V，或者記錄V的輸出序號(hào);
       for ( V 的每個(gè)鄰接點(diǎn) W )
           Indegree[W]––; //入度-1，即V-W這條邊去掉
   }
}//普通方法O(|V|），則整體T=O（|V|*|V|）。
</pre> 

<pre>//改進(jìn)將入度變?yōu)?的頂點(diǎn)放到一個(gè)容器里，下次從容器里取出即可，加快V的查找
void TopSort(){ 
    for ( 圖中每個(gè)頂點(diǎn) V )
        if ( Indegree[V]==0 )
            Enqueue( V, Q );    //這里的容器用隊(duì)列
    while ( !IsEmpty(Q) ) {
        V = Dequeue( Q );   //容器里取出入度為0的頂點(diǎn)
        輸出V，或者記錄V的輸出序號(hào); 
        cnt++;  //記錄輸出的頂點(diǎn)個(gè)數(shù)
        for ( V 的每個(gè)鄰接點(diǎn) W )
            if ( ––Indegree[W]==0 ) //鄰接點(diǎn)入度-1，但要檢查是否減完后變?yōu)?
                Enqueue( W, Q );    //若為0再放入容器
    }
    if ( cnt != |V| )   //還有頂點(diǎn)留在圖里
        Error( “圖中有回路” );
}//T=O（|V|+|E|） 可用來(lái)檢測(cè)DAG
</pre> 

拓?fù)渑判虻膽?yīng)用

關(guān)鍵路徑問題

• AOV網(wǎng)絡(luò)（Activity On vertex)
• AOE網(wǎng)絡(luò) (Activity On Edge)

這里討論AOE網(wǎng)絡(luò)，關(guān)鍵路徑由絕對(duì)不允許延誤的活動(dòng)組成的路徑，沒有機(jī)動(dòng)時(shí)間的路徑組成的路徑就是關(guān)鍵路徑。