Shortest Path
========
Single Source Shortest Path
--------
- 若使用Backtracking演算法,將枚舉所有路徑,必會TLE,因此我們將列舉幾項好用DER演算法!!
![](/acm/13125075_944400135668382_1681010432_n.gif)
###Relaxation
- 若點v離source的距離為8、點u離source的距離為3,現在有一個點k,(u,k)長度為2、(k,v)長度為1,則對(u,v)做Relax。Relax後點v離source距離更改為6。
![](/acm/Relax.png)
~~~{.c }
Relex(u,v,w){
if(dis[u]+w(u,v)對所有的邊做n-1次的Relax
- 時間複雜度: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若有負的cycle,每做一次Relax,source至cycle上點的距離,就會持續變小。
- 偵測辦法:若在第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相較於BellmanFord做了n-1次Relax,SPFA只對值有改變的點相連的邊做Relax。
- 方法:用Queue存有改變的點。
- 時間複雜度:O(kE),在k<
![](/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)=n)
return true;
}
}
}
}
return false;
}
~~~
- 負環的比較:BellmanFord偵測到的負環為整個Graph的,SPFA偵測到的負環為從source出發會走的到的。
All Pair Shortest Path
---------
若用BellmanFord做V次,時間複雜度為O(V^2E)。若用SPFA做V次,時間複雜度為O(kVE)。都可能造成TLE。
###Floyd
- 對所有點(i,j),枚舉所有點k(點i連到點k,點k連到點j),做Relax。
- 時間複雜度:O(V^3)
![](/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