Floyd-Warshall算法描述
1)適用范圍：
a)APSP(All Pairs Shortest Paths)
b)稠密圖效果最佳
c)邊權(quán)可正可負(fù)
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)算法結(jié)束：dis即為所有點(diǎn)對的最短路徑矩陣
3)算法小結(jié)：此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。時(shí)間復(fù)雜度O(n^3)。
考慮下列變形：如(I,j)∈E則dis[I,j]初始為1,else初始為0，這樣的Floyd算法最后的最短路徑矩陣即成為一個(gè)判斷I,j是否有通路的矩陣。更簡單的，我們可以把dis設(shè)成boolean類型，則每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”來代替算法描述中的藍(lán)色部分，可以更直觀地得到I,j的連通情況。
標(biāo)簽：
Floyd-Warshall
Shortest
Pairs
Paths
上傳時(shí)間：
2013-12-01
上傳用戶：dyctj
實(shí)驗(yàn)源代碼
//Warshall.cpp #include<stdio.h> void warshall(int k,int n) { int i , j, t; int temp[20][20]; for(int a=0;a<k;a++) { printf("請輸入矩陣第%d 行元素:",a); for(int b=0;b<n;b++) { scanf ("%d",&temp[a][b]); } } for(i=0;i<k;i++){ for( j=0;j<k;j++){ if(temp[ j][i]==1) { for(t=0;t<n;t++) { temp[ j][t]=temp[i][t]||temp[ j][t]; } } } } printf("可傳遞閉包關(guān)系矩陣是:\n"); for(i=0;i<k;i++) { for( j=0;j<n;j++) { printf("%d", temp[i][ j]); } printf("\n"); } } void main() { printf("利用 Warshall 算法求二元關(guān)系的可傳遞閉包\n"); void warshall(int,int); int k , n; printf("請輸入矩陣的行數(shù) i: "); scanf("%d",&k);
四川大學(xué)實(shí)驗(yàn)報(bào)告 printf("請輸入矩陣的列數(shù) j: "); scanf("%d",&n); warshall(k,n); }
標(biāo)簽：
warshall
離散
實(shí)驗(yàn)
上傳時(shí)間：
2016-06-27
上傳用戶：梁雪文以
function [alpha,N,U]=youxianchafen2(r1,r2,up,under,num,deta)
%[alpha,N,U]=youxianchafen2(a,r1,r2,up,under,num,deta)
%該函數(shù)用有限差分法求解有兩種介質(zhì)的正方形區(qū)域的二維拉普拉斯方程的數(shù)值解
%函數(shù)返回迭代因子、迭代次數(shù)以及迭代完成后所求區(qū)域內(nèi)網(wǎng)格節(jié)點(diǎn)處的值
%a為正方形求解區(qū)域的邊長
%r1,r2分別表示兩種介質(zhì)的電導(dǎo)率
%up,under分別為上下邊界值
%num表示將區(qū)域每邊的網(wǎng)格剖分個(gè)數(shù)
%deta為迭代過程中所允許的相對誤差限
n=num+1; %每邊節(jié)點(diǎn)數(shù)
U(n,n)=0; %節(jié)點(diǎn)處數(shù)值矩陣
N=0; %迭代次數(shù)初值
alpha=2/(1+sin(pi/num));%超松弛迭代因子
k=r1/r2; %兩介質(zhì)電導(dǎo)率之比
U(1,1:n)=up; %求解區(qū)域上邊界第一類邊界條件
U(n,1:n)=under; %求解區(qū)域下邊界第一類邊界條件
U(2:num,1)=0;U(2:num,n)=0;
for i=2:num
U(i,2:num)=up-(up-under)/num*(i-1);%采用線性賦值對上下邊界之間的節(jié)點(diǎn)賦迭代初值
end
G=1;
while G>0 %迭代條件：不滿足相對誤差限要求的節(jié)點(diǎn)數(shù)目G不為零
Un=U; %完成第n次迭代后所有節(jié)點(diǎn)處的值
G=0; %每完成一次迭代將不滿足相對誤差限要求的節(jié)點(diǎn)數(shù)目歸零
for j=1:n
for i=2:num
U1=U(i,j); %第n次迭代時(shí)網(wǎng)格節(jié)點(diǎn)處的值
if j==1 %第n+1次迭代左邊界第二類邊界條件
U(i,j)=1/4*(2*U(i,j+1)+U(i-1,j)+U(i+1,j));
end
if (j>1)&&(j U2=1/4*(U(i,j+1)+ U(i-1,j)+ U(i,j-1)+ U(i+1,j));
U(i,j)=U1+alpha*(U2-U1); %引入超松弛迭代因子后的網(wǎng)格節(jié)點(diǎn)處的值
end
if i==n+1-j %第n+1次迭代兩介質(zhì)分界面（與網(wǎng)格對角線重合）第二類邊界條件
U(i,j)=1/4*(2/(1+k)*(U(i,j+1)+U(i+1,j))+2*k/(1+k)*(U(i-1,j)+U(i,j-1)));
end
if j==n %第n+1次迭代右邊界第二類邊界條件
U(i,n)=1/4*(2*U(i,j-1)+U(i-1,j)+U(i+1,j));
end
end
end
N=N+1 %顯示迭代次數(shù)
Un1=U; %完成第n+1次迭代后所有節(jié)點(diǎn)處的值
err=abs((Un1-Un)./Un1);%第n+1次迭代與第n次迭代所有節(jié)點(diǎn)值的相對誤差
err(1,1:n)=0; %上邊界節(jié)點(diǎn)相對誤差置零
err(n,1:n)=0; %下邊界節(jié)點(diǎn)相對誤差置零
G=sum(sum(err>deta))%顯示每次迭代后不滿足相對誤差限要求的節(jié)點(diǎn)數(shù)目G
end
標(biāo)簽：
有限差分
上傳時(shí)間：
2018-07-13
上傳用戶：Kemin
