@zqbinggong
2018-03-24T13:14:55.000000Z
字数 3228
阅读 1416
矩阵乘法
Floyd-Warshall算法
Johnson算法
算法导论
.
if i == j
print i
else if pi[ij] = nil
print no path
else
print-path(Pi,i,pi[ij])
print j
extended-shortest-paths(L,W)
n = L.rows
let L' to be a new n by n matrix
for i = 1 to n
for j = 1 to n
l'[ij] = 00
for k = 1 to n
l'[ij] = min(l'[ij], l[ik]+w[kj])
return L'
使用重复平方技术——
faster-all-pathsirs-shortest-paths(W)
n = W.rows
L_1 = W
m = 1
while m < n-1
let L_2m = extended-shortest-paths(L_m,L_m)
m = 2m
return L_m
思考下,为什么两种动态规划的时间相差一个量级(不考虑重复平方技术)呢?
关系式:
自底向上
floyd-warshall(W)
n = W.rows
D_0 = W
for k = 1 to n
let D_k be a new matrix
for i = 1 to n
for j = 1 to n
5中关系式
return D_n
transitive-closure(G)
n = |G.V|
let T_0 be a new matrix and initialize it obey formula dexcribed as 4
for k = 1 to n
let T_k be a new matrix
for i = 1 to n
for j = 1 to n
关系式4
return T_n
Johnson(G,w)
compute G'
if bellman-ford(G',s) == false
print "the input graph contains a negative-weight cycle"
else
for each vertex v in G.E
set h(v) to the value computed by the bellman-ford algorithm
for each edge(u,v) in G'.E
w'(u,v) = w(u,v) + h(u) - h(v)
let D be a new n by n matrix
for each vertex v in G.E
run dijkstra(G,w',u) to compute delta(u,v) for all v in G.V
for each vertex in G.V
d[uv] = delta(u,v) + h(v) - h(u)
return D