Floyd-Warshall算法描述
1)適用范圍：
a)APSP(All Pairs Shortest Paths)
b)稠密圖效果最佳
c)邊權可正可負
2)算法描述：
a)初始化：dis[u,v]=w[u,v]
b)For k:=1 to n
For i:=1 to n
For j:=1 to n
If dis[i,j]>dis[i,k]+dis[k,j] Then
Dis[I,j]:=dis[I,k]+dis[k,j]
c)算法結束：dis即為所有點對的最短路徑矩陣
3)算法小結：此算法簡單有效，由于三重循環結構緊湊，對于稠密圖，效率要高于執行|V|次Dijkstra算法。時間復雜度O(n^3)。
考慮下列變形：如(I,j)∈E則dis[I,j]初始為1,else初始為0，這樣的Floyd算法最后的最短路徑矩陣即成為一個判斷I,j是否有通路的矩陣。更簡單的，我們可以把dis設成boolean類型，則每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”來代替算法描述中的藍色部分，可以更直觀地得到I,j的連通情況。
求標準偏差
> function c=myfunction(x)
> [m,n]=size(x)
> t=0
> for i=1:numel(x)
> t=t+x(i)*x(i)
> end
> c=sqrt(t/(m*n-1))
function c=myfunction(x)
[m,n]=size(x)
t=0
for i=1:m
for j=1:n
t=t+x(i,j)*x(i,j)
end
end
c=sqrt(t/(m*n-1
求標準偏差
> function c=myfunction(x)
> [m,n]=size(x)
> t=0
> for i=1:numel(x)
> t=t+x(i)*x(i)
> end
> c=sqrt(t/(m*n-1))
function c=myfunction(x)
[m,n]=size(x)
t=0
for i=1:m
for j=1:n
t=t+x(i,j)*x(i,j)
end
end
c=sqrt(t/(m*n-1
求標準偏差
> function c=myfunction(x)
> [m,n]=size(x)
> t=0
> for i=1:numel(x)
> t=t+x(i)*x(i)
> end
> c=sqrt(t/(m*n-1))
function c=myfunction(x)
[m,n]=size(x)
t=0
for i=1:m
for j=1:n
t=t+x(i,j)*x(i,j)
end
end
c=sqrt(t/(m*n-1
求標準偏差
> function c=myfunction(x)
> [m,n]=size(x)
> t=0
> for i=1:numel(x)
> t=t+x(i)*x(i)
> end
> c=sqrt(t/(m*n-1))
function c=myfunction(x)
[m,n]=size(x)
t=0
for i=1:m
for j=1:n
t=t+x(i,j)*x(i,j)
end
end
c=sqrt(t/(m*n-1
Instead of finding the longest common
subsequence, let us try to determine the
length of the LCS.
Then tracking back to find the LCS.
Consider a1a2…am and b1b2…bn.
Case 1: am=bn. The LCS must contain am,
we have to find the LCS of a1a2…am-1 and
b1b2…bn-1.
Case 2: am≠bn. Wehave to find the LCS of
a1a2…am-1 and b1b2…bn, and a1a2…am and
b b b
b1b2…bn-1
Let A = a1 a2 … am and B = b1 b2 … bn
Let Li j denote the length of the longest i,g g
common subsequence of a1 a2 … ai and b1 b2
… bj.
Li,j = Li-1,j-1 + 1 if ai=bj
max{ L L } a≠b i-1,j, i,j-1 if ai≠j
L0,0 = L0,j = Li,0 = 0 for 1≤i≤m, 1≤j≤n.
