在網(wǎng)絡(luò)中，求兩個不同頂點(diǎn)之間的所有路徑中，邊的權(quán)值之和最小的那一條路徑

• 這條路徑是兩點(diǎn)之間的最短路徑
  *第一個頂點(diǎn)為源點(diǎn)
  *最后一個頂點(diǎn)為終點(diǎn)

問題分類

• 單源 最短路徑問題
  從固定源點(diǎn)出發(fā)，求其到所有其他頂點(diǎn)的最短路徑
  • (有向)無權(quán)圖
  • (有向)有權(quán)圖
• 多源 最短路徑問題
  求任意兩頂點(diǎn)見得最短路徑

有向無權(quán)圖的單源最短路徑

按照 遞增 的順序找出給定節(jié)點(diǎn)到各個節(jié)點(diǎn)的最短路徑

Paste_Image.png

dist[S] = 0
path[]
public  UnWeight(Vertex S){
    Enqueue(S,Q);
    while(!IsEmpty(Q)){
        V = Dequeue(Q);
        for( V 的鄰接節(jié)點(diǎn) W ){
            if(dist[W]!=-1){
                dist[W] = dist[V]+1;
                path[W] = V;
                Enqueue(W,Q);
            }
        }
    }
}

有權(quán)有向圖的單源最短路徑

#dijkstra算法

令 S={源點(diǎn)A+已經(jīng)確定了最短路徑的頂點(diǎn)Vi}
對任一未收錄的·頂點(diǎn)v·,定義dist[v] = A 到 v 的最短路徑長度。
（但該路徑僅僅經(jīng)過集合S中的頂點(diǎn)）。
若路徑是按照 @遞增 的順序生成的=>
{
  真正的最短路必須只經(jīng)過集合S中的頂點(diǎn)。（反證法）
  每次從未收錄的頂點(diǎn)中選一個dist最小的收錄（貪心）。
  增加v進(jìn)入S以后，可能影響另外一個未收錄節(jié)點(diǎn)w的dist值
    #（比如之前不可達(dá)，或是之前的到達(dá)路徑比較長==）
    # dist[w]=min(dist[v] + E<v,w>, dist[w])
    # E<v，w>表示該邊的權(quán)重
}

Paste_Image.png

#個人BB
一個富有侵略性的算法。
想象頂點(diǎn)就是一個城池。
占據(jù)了頂點(diǎn)以后，依據(jù)已經(jīng)占據(jù)的城池向外擴(kuò)展。
首先擴(kuò)展就是離出發(fā)點(diǎn)最近的領(lǐng)土
（始終是計算出發(fā)點(diǎn)和其他點(diǎn)的距離）。

后進(jìn)來的領(lǐng)土?xí)粫绊懪f的領(lǐng)土的距離呢？
@不會
為什么？
加進(jìn)來的點(diǎn)是按距離順序添加的。

#代碼

void Dijkstra(Vertex s){
    while(1){
        V = 未收錄頂點(diǎn)中dist最小者；
        if(沒有V){
            return;
        }
        collected[V]=true；
        for(V 的每個鄰接點(diǎn) W)
            if(collected[W] == false)
                if(dist[V] +E(v,w) < dist[W]){
                    dist[W] = dist[V] + E(v,w);
                    path[W] = V;
                }
    }
}
/*不能解決有負(fù)邊的情況*/

如果遇到負(fù)值圈，就可能會陷入一直死循環(huán)的情況。

負(fù)值圈

• 方法1：直接掃描所有未收錄頂點(diǎn) - O(|V|) 適用于稠密圖
  • T =O(|V|*|V| + E)

每個節(jié)點(diǎn)都要掃一遍。V個點(diǎn)*V
但是其實(shí)真是情況是不是，但后面掃的范圍會變小呢...因?yàn)榇蟛糠直患尤氲搅思蟘ollected 中了。
E 是因?yàn)橐獙γ總€新加入的點(diǎn)的鄰接點(diǎn)進(jìn)行處理，所以每條邊都會處理一遍

• 方法2：將dist存在最小堆中-O（log(V)） 適用于稀疏圖
  • 更新dist[w]的值 - O(log|V|)
  • T = O(|N|log|V| + |E|log|V|) = O(|E|log|V|)

多源最短路徑問題

#floy算法:

#個人BB

其實(shí)和dijkstra有點(diǎn)像。就是不斷地添加點(diǎn)到一個集合中。

添加進(jìn)來的點(diǎn)，
      #已經(jīng)收錄的集合到這個點(diǎn)的路徑
以及  #這個點(diǎn)到達(dá)其他點(diǎn)的路徑
暴露了出來。

此時，到達(dá)k的路徑，以及從k 到達(dá)別人的路徑保持不變。
改變的是其他要經(jīng)過k來走最短路徑的路。

假設(shè)之后，某個點(diǎn)w到k的距離發(fā)生了變化，必然是因?yàn)榧恿诵碌狞c(diǎn)k1，
那么k1，自然會將 w到k的距離發(fā)生變化，而且，會把w經(jīng)過 k1到達(dá)的所有點(diǎn)的距離都會進(jìn)行改變。
（因?yàn)橹?，我在?dān)心，k對整個距離產(chǎn)生變化以后，其他點(diǎn)的結(jié)果相當(dāng)于依賴于看k的距離，但是，如果k的距離改變了，那么豈不是其他結(jié)果不準(zhǔn)了？
其實(shí)k距離發(fā)生變化，只有可能是有k1加入導(dǎo)致，如果k1導(dǎo)致k發(fā)生變化，那么經(jīng)過k的路徑，自然一定要經(jīng)過k1,
因此k1自然會將所有的后面所能到達(dá)的點(diǎn)全部化為更新后的最短路徑。

需要多想想。）

public void floyd(){
    for(i =0;i<N ;i++){
        D[i][j] = G[i][j];
        path[i][j] = -1;
    }
    for(int k=0;k<N;k++){
        for(int i =0;i<N;i++){
            for(int j=0;j<N;j++){
                if(d[i][k]+d[k][j] < d[i][j]){
                    d[i][j] = d[i][k]+d[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

T=O(|V||V||V|)