版本 d74c6907054306c8980ed14e7e046c0f69ec83b4
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。
###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,則有負環存在。 ###SPFA()
All Pair Shortest Path
###Floyd