Shortest Path
========
Single Source Shortest Path
--------
- <big>若使用Backtracking演算法，將枚舉所有路徑，必會TLE，因此我們將列舉幾項好用DER演算法!!</big>

![](/acm/13125075_944400135668382_1681010432_n.gif)


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

![](/acm/Relax.png)

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

###Bellman Ford
- <big>對所有的邊做n-1次的Relax</big>
- 時間複雜度：O(VE)

![](/acm/bellman.gif)

~~~{.c }
//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);
}
~~~

- <big>若有負的cycle，每做一次Relax，source至cycle上點的距離，就會持續變小。</big>
    - 偵測辦法：若在第n次做Relax時，若有任何一邊可以被Relax，則有負環存在。

~~~{.c }
//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()
- <big>相較於BellmanFord做了n-1次Relax，SPFA只對值有改變的點相連的邊做Relax。</big>
    - 方法：用Queue存有改變的點。
- <big>時間複雜度：O(kE)，在k<<V的情況下。
                  O(VE)，最差的情況。</big>

![](/acm/cutefafa.gif)

~~~{.c }
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次，則有負環存在。

~~~{.c }
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;
}
~~~

- <big>負環的比較：BellmanFord偵測到的負環為整個Graph的，SPFA偵測到的負環為從source出發會走的到的。</big>

All Pair Shortest Path
---------
<big>若用BellmanFord做V次，時間複雜度為O(V^2E)。若用SPFA做V次，時間複雜度為O(kVE)。都可能造成TLE。</big>

###Floyd
- <big>對所有點(i,j)，枚舉所有點k(點i連到點k，點k連到點j)，做Relax。</big>
- <big>時間複雜度：O(V^3)</big>

![](/acm/HI_18.gif)

~~~{.c }
Floyd(){
    for(i==j)
        dis[i][j]=0;
    for(each edge w(i,j))
        dis[i][j]=w(i,j);
    for(not each edge w(i,j))
        dis[i][j]=INF;
    for(k=0;k<n;k++)
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                if(dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
}
~~~