%Dijkstra最短路算法Matlab程序用于求從各點(diǎn)之間的最短路距離
%D為鄰接矩陣需要輸入
%d為s到其它各點(diǎn)最短距離
%pre記載了最短路徑生成路線(xiàn)
clear?all
clc
D=[0?6?inf?inf?5?6?inf?5?inf
????6?0?9?inf?inf?9?inf?3?inf
????inf?9?0?7?inf?inf?4?inf?inf
????inf?inf?7?0?6?4?6?inf?3
????5?inf?inf?6?0?5?inf?inf?4
????6?9?inf?4?5?0?5?inf?inf
????inf?inf?4?6?inf?5?0?inf?inf
????5?3?inf?inf?inf?inf?inf?0?inf
????inf?inf?inf?3?4?inf?inf?inf?0];%這是鄰接矩陣
[mn]=size（D）;%m行n列，這里m=n=9
E=zeros（mn）;%E為任意兩點(diǎn)間最短距離矩陣
for?s=1:m
????%當(dāng)s=1時(shí)，就是求1這個(gè)點(diǎn)到其他各個(gè)點(diǎn)的最短距離，同理，當(dāng)s=2時(shí)，……=9時(shí)。
????d=inf.*ones（1m）;%初始化
????d（1s）=0;%s點(diǎn)到s點(diǎn)的最短距離為0
????ok=zeros（1m）;%初始化，用來(lái)記錄已經(jīng)求得最短路徑的點(diǎn)
????pre=zeros（1m）;%初始化
????while?length（find（ok==1））????????minD=inf;
????????for?k=1:m
???????????if?ok（k）==0&&minD>d（k）
???????????????minD=d（k）;
???????????????y=k;
???????????end
????????end
????????if?minD==inf
????????????break;
????????end
????????ok（y）=1;
????????for?i=1:m
????????????if?D（yi）~=inf
????????????????alt=d（y）+D（yi）;
????????????????if?alt????????????????????d（i）=alt;
????????????????????pre（i）=y;
????????????????end
????????????end
????????end
????end
???E（s:）=d;
end
E??%輸出最短距離矩陣E，正確解為E?=

????%?[0?????6????15????10?????5?????6????11?????5?????9
????%?6?????0?????9????13????11?????9????13?????3????15
????%?15?????9?????0?????7????13?????9?????4????12????10
????%?10????13?????7?????0?????6?????4?????6????15?????3
????%?5????11????13?????6?????0?????5????10????10?????4
????%?6?????9?????9?????4?????5?????0?????5????11?????7
????%?11????13?????4?????6????10?????5?????0????16?????9
????%?5?????3????12????15????10????11????16?????0????14
????%?9????15????10?????3?????4?????7?????9????14?????0]

?屬性????????????大小?????日期????時(shí)間???名稱(chēng)
-----------?---------??----------?-----??----

?????文件???????1773??2009-10-25?23:36??xujinpeng_dijkstra\dijkstra.m

?????目錄??????????0??2009-10-25?23:39??xujinpeng_dijkstra

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

?????????????????1773????????????????????2