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

版本 d74c6907054306c8980ed14e7e046c0f69ec83b4

acm/course/Shortest_Path

Changes from d74c6907054306c8980ed14e7e046c0f69ec83b4 to ec4a75bdc697cbaf50be3d3be7b90582571338ae

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)

~~~{.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()

All Pair Shortest Path
---------
###Floyd