19/7/2021

· · 个人记录

all-pair最短路

O(n^3)

Floyd-Warshall算法

int d[1000][1000];
0...n-1

动态规划。 把图上的n个点从1到n编号 把计算all-pair最短路，分成若干个阶段。 考虑从s到t的路径，s,v_1,v_2,v_3,\dots,v_k,t,把v_1,v_2,v_3,\dots,v_k称为中间点。

第k个阶段，考虑从s到t的(中间点是1,2,3,\dots,k)路径，计算出这些路径最短路的那条路径的长度。

d_k(s,t) d_{k+1}(s,t)=\min(d_k(s,t),d_k(s,k+1)+d_k(k+1,t))

边界条件

d_0(s,s)=0

若s!=td_0(s,t)=从s到t最短的边的长度。

若不存在s->t的边，d_0(s,t)=\infty

负环

只考虑图上无负环的情况

Bellman-Ford

  1. 如果从s到t的最短路存在，那么Bellman-Ford算法结束时一定有t.d=dis(s,t)。
  2. 如果从s到t没有路<-> Bellman-Ford算法结束时有t.d=\infty。
  3. 如果从s到t有路，但是没有最短路，说明存在一条s到t的路径经过负环。

对于Bellman-Ford算出来的v,d如何区分是第一种情况还是第三种情况？

当 算法结束是，若t.d<\infty则从s可以到t，且t.d 小于等于 从s到t的不超过n-1条边的路径中最短的那条路径的长度。