Ma tla b 是當今使用最為廣泛的數學軟件,它具有相當強大的數值計算、數據處理、系統
分析、圖形顯示、甚至符號運算功能,是一個完整的數學平臺,但是它不能實現端口操作和
實時控制Borland C + +Builder是一種新穎的可視化編程語言,可方便實現交互界面、數據
采集和端口操作等,但是它在數值處理分析和算法工具等方面,效率遠遠低于Matlab語言
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的連通情況。
采用3D Bresenham算法在兩點間劃一直線
% This program is ported to MATLAB from:
% B.Pendleton. line3d - 3D Bresenham s (a 3D line drawing algorithm)
% ftp://ftp.isc.org/pub/usenet/comp.sources.unix/volume26/line3d, 1992
%
% Which is referenced by:
% Fischer, J., A. del Rio (2004). A Fast Method for Applying Rigid
% Transformations to Volume Data, WSCG2004 Conference.
% http://wscg.zcu.cz/wscg2004/Papers_2004_Short/M19.pdf