Shortest Path ======== Single Source Shortest Path -------- - <big>若使用Backtracking演算法,將枚舉所有路徑,必會TLE,因此我們將列舉幾項好用DER演算法!!</big>  ###Relaxation - <big>若點v離source的距離為8、點u離source的距離為3,現在有一個點k,(u,k)長度為2、(k,v)長度為1,則對(u,v)做Relax。Relax後點v離source距離更改為6。</big>  ~~~{.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); } ~~~ ###SPFA() All Pair Shortest Path --------- ###Floyd