%Dijkstra
clear;clc;
format?compact;
%M=inf;
%%%?????輸入鄰接矩陣a??????%%%
a=inf（2424）;
a（13）=450;a（32）=80;a（34）=1150;a（45）=1100;
a（56）=202;a（67）=20;a（78）=195;a（89）=306;a（510）=1200;
a（511）=720;a（1113）=520;a（1112）=690;a（1314）=170;
a（1415）=88;a（1516）=462;a（1417）=690;a（1418）=160;
a（1819）=70;a（1820）=320;a（2021）=160;a（2122）=70;
a（2123）=290;a（2324）=30;
for?i?=?1:24????%針對無向圖，化為對稱陣
????for?j?=?1:24
????????if（a（ij）?~=?inf）
????????????a（ji）?=?a（ij）;
????????end
????end
end
%%%??????輸入鄰接矩陣a??????%%%
v0=13;%輸入源點

n?=?length（a）;
dist?=?inf（1n）;%初始距離設為無窮大
path?=?zeros（1n）-1;%初始值設為-1，-1表示不可達
s=false（1n）;%s（i）=1表示i點在S中logic比double節約空間，whos

%s（v0）=true;
%dist=a（v0:）;
path（v0）=v0;dist（v0）=0;
for?i?=?1:n
????%m?=?min（dist（~s））;%找到s集之外的點到v0距離的最小值m
????%v?=?find（dist==m1）;%找到對應m的點
????m?=?inf;
????for?w?=?1:n
????????if?（~s（w）?&&?（dist（w）?????????????v?=?w;
????????????m?=?dist（w）;
????????end
????end
????s（v）?=?true;
????for?w=1:n
????????if（~s（w）?&&?m+a（vw）?????????????dist（w）?=?m+a（vw）;
????????????path（w）=v;
????????end
????end
end
dist
%path
disp（‘path:‘）;
for?i?=?1:n
????if?i?~=?v0
????????fprintf（1‘%d?to?%d?:‘v0?i）;
????????print_path（v0ipath）;
????????disp（‘?‘）;
????end
end

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????259??2011-07-22?15:43??print_path.m

?????文件???????1372??2011-07-22?22:12??Dijkstra2.m

-----------?---------??----------?-----??----

?????????????????1631????????????????????2