分享到plurk 分享到twitter 分享到facebook

版本 c6dba8f363ed1e1bd7cc7ef456dbf69a85c97dab

acm/course/Shortest_Path

Shortest Path

Single Source Shortest Path

  • 若使用Backtracking演算法,將枚舉所有路徑,必會TLE,因此我們將列舉幾項好用DER演算法!!

###Relaxation - 若點v離source的距離為8、點u離source的距離為3,現在有一個點k,(u,k)長度為2、(k,v)長度為1,則對(u,v)做Relax。Relax後點v離source距離更改為6。

Relex(u,v,w){
   if(dis[u]+w(u,v)<dis[v])
       dis[v]=dis[u]+w(u,v);
}

###Bellman Ford - 對所有的邊做n-1次的Relax - 時間複雜度:O(VE)

//Pseudo Code
BellmanFord(){
    //init
    dis[source]=0;
    for(all i != source) 
        dis[i] = INF;
    //n-1 times
    for(i=0;i<n-1;i++)
        for(each edge w(u,v) in G)
            Relax(u,v,w);
}
  • 若有負的cycle,每做一次Relax,source至cycle上點的距離,就會持續變小。
    • 偵測辦法:若在第n次做Relax時,若有任何一邊可以被Relax,則有負環存在。
//Pseudo Code
BellmanFord(){
    //init
    dis[source]=0;
    for(all i != source) 
        dis[i] = INF;
    //n-1 times
    for(i=0;i<n-1;i++)
        for(each edge w(u,v) in G)
            Relax(u,v,w);
    //Negative Cycle
    for(each edge w(u,v) in G)
        if(dis[u]+w(u,v)<dis[v])
            return true;
    return false;
}

###SPFA() - 相較於BellmanFord做了n-1次Relax,SPFA只對值有改變的點相連的邊做Relax。 - 方法:用Queue存有改變的點。 - 時間複雜度:O(kE),在k<<V的情況下。 O(VE),最差的情況。

SPFA(){
    for(all i){
        dis[i] = INF;
        inqueue[i] = false;
    }
    dis[source]=0;
    inqueue[source]=true;
    queue.push(source);
    while(!queue.empty()){
        int now = queue.front();
        inqueue[now]=false;
        queue.pop();
        for(each node v adjacent to now){
            if(dis[now]+w(now,v)<dis[v]){
                dis[v]=dis[now]+w(now,v);
                if(!inqueue[v]){
                    queue.push(v);
                    inqueue[v]=true;
                }
            }
        }
    }
}
  • 偵測負環:若一個點進去Queue的次數超過n-1次,則有負環存在。
SPFA(){
    for(all i){
        dis[i] = INF;
        inqueue[i] = false;
        count[i] = 0;
    }
    dis[source]=0;
    inqueue[source]=true;
    queue.push(source);
    while(!queue.empty()){
        int now = queue.front();
        inqueue[now]=false;
        queue.pop();
        for(each node v adjacent to now){
            if(dis[now]+w(now,v)<dis[v]){
                dis[v]=dis[now]+w(now,v);
                if(!inqueue[v]){
                    queue.push(v);
                    inqueue[v]=true;
                    count[v]++;
                    if(count[v]>=n)
                        return true;
                }
            }
        }
    }
    return false;
}
  • 負環的比較:BellmanFord偵測到的負環為整個Graph的,SPFA偵測到的負環為從source出發會走的到的。

All Pair Shortest Path

###Floyd