主成分分析程式的%w為為此圖的距離矩陣，%start為為起始端點下標，%MAX是數據輸入時的∞的實際值。
基本介紹
- 中文名：主成分分析程式
- %w：為此圖的距離矩陣
- %start：為起始端點下標
- %MAX：是數據輸入時的∞的實際值
主程式,初始化路由表,權值問題,具體實現過程,
主程式
function Dijkstra(w,start,MAX)
%w為此圖的距離矩陣
%start為起始端點下標（從1開始）
%MAX是數據輸入時的∞的實際值
%2011年6月19日17:02:03
len=length(w);
flag=zeros(len,2);
index=zeros(1,len);
index(1)=start;
初始化路由表
%根據路由類型初始化路由表
R=ones(len,2)*MAX;
R(1,1)=0;
R(1,2)=start;
port=zeros(1,len);
port(start)=0;
權值問題
%處理端點有權的問題
for i=1:len
tmp=w(i,i)/2;
if tmp~=0
w(i,:)=w(i,:)+tmp;
w(:,i)=w(:,i)+tmp;
flag(i,1)=1; %表示端i點有權值
flag(i,2)=tmp; %存儲端點權值的一半
end
w(i,i)=MAX;
end
s=sprintf('\tv%d',1:len);
s_tmp=sprintf('\t|%s\t%s\t',' 置定端',' 距離');
s=strcat(s,s_tmp);
s_tmp=sprintf('%s\t',' 路由 ');
s=strcat(s,s_tmp);
s_tmp=sprintf('\n----------------------------------------------------\n\t0');
s=strcat(s,s_tmp);
for i=1:len-1
s_tmp=sprintf('\t∞');
s=strcat(s,s_tmp);
end
s_tmp=sprintf('\t|\t%d\t%4.1f\t%d',start,0,start);
s=strcat(s,s_tmp);
disp(s);
具體實現過程
%Dijkstra算法具體實現過程
count=1;
while count<len
s='';
N=MAX; %暫存每次距離比較的較大值
x=1; %暫存每次距離比較的較大值的下標
for i=1:len
if isempty(find(index==i,1)) %將沒有在置定點的i值跳過
continue
end
for j=1:len
if ~isempty(find(index==j,1)) %將在置定點的j值跳過
continue
else
port(j)=R(i,1)+w(i,j); %新距離
end
if port(j)<R(j,1) %新舊路由距離比較，如果小，則更新
R(j,1)=port(j);
R(j,2)=i;
else
port(j)=R(j,1);
end
if port(j)<N %通過比較，得出一次循環中，最小的距離，將相應點置定
N=port(j);
x=j;
end
end
end
for k=1:len %輸出格式設定(考慮端權值)
if isempty(find(index==k,1))
if port(k)==MAX
s_tmp=sprintf('\t%s','∞');
else
if flag(k,1)
port(k)=port(k)-flag(k,2);
end
s_tmp=sprintf('\t%2.1f',port(k));
end
else
s_tmp=sprintf('\t%s','_');
end
s=strcat(s,s_tmp);
end
if flag(x,1)
R(x,1)=R(x,1)-flag(x,2);
end
s_tmp=sprintf('\t|\t%d\t%4.1f\t%d',x,R(x,1),R(x,2));
s=strcat(s,s_tmp);
disp(s);
%為下次的循環設定條件——更新置定點列表+count加1
count=count+1;
index(count)=x;
end
end
示例：
輸入：
b=[
0,9.2,1.1,3.5,100,100;
1.3,0,4.7,100,7.2,100;
2.5,100,0,100,1.8,100;
100,100,5.3,0,2.4,7.5;
100,6.4,2.2,8.9,0,5.1;
7.7,100,2.7,100,2.1,0
];
Dijkstra(b,1,100
