用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，并写出执行算法过程中各步的状态。 用Dijkstra算法求附图中从点a到其它各节点的最短路径，...
\u8bd5\u5229\u7528Dijkstra\u7b97\u6cd5\u6c42\u56fe\u4e2d\u4ece\u9876\u70b9a\u5230\u5176\u4ed6\u5404\u9876\u70b9\u95f4\u7684\u6700\u77ed\u8def\u5f84\uff0c\u5199\u51fa\u6267\u884c\u7b97\u6cd5\u8fc7\u7a0b\u4e2d\u5404\u6b65\u7684\u72b6\u6001\u30021 c:2
2 c:2 f:6
3 c:2 f:6 e:10
4 c:2 f:6 e:10 d:11
5 c:2 f:6 e:10 d:11 g:14
6 c:2 f:6 e:10 d:11 g:14 b:15
\u7ed3\u679c\u5982\u4e0b\u56fe\uff1a
举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 迪科斯彻算法可以用来找到两个城市之间的最短路径。
迪科斯彻算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到v的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到u的路径。这条路径的长度是d+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d达到它最终的值的时候每条边(u,v)都只被拓展一次。
算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。program dijkstra;
var
state:array[1..100]of boolean;
data:array[1..100,1..100]of longint;
n,i,j,k,min,node:longint;
begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
fillchar(data, sizeof(data), 0);
fillchar(state,sizeof(state),0);
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(data[i,j]);
if data[i,j]=0 then data[i,j]:=maxint;
end;
state[1]:=true;
for k:=2 to n do
begin
min:=maxint;
{查找权值最小的点为node}
node:=1;
for i:=2 to n do
if (data[1,i]<min)and(state[i]=false) then
begin
min:=data[1,i];
node:=i;
end;
{更新其他各点的权值}
state[node]:=true;
for j:=1 to n do
if (data[1,node]+data[node,j]<data[1,j]) and (state[j]=false) then
data[1,j]:=data[1,node]+data[node,j];
end;
for i:=1 to n-1 do
if data[1,i]<>maxint then
write(data[1,i],' ')
else
write(-1,' ');
writeln(data[1,n]);
close(input);
close(output);
end.
绛旓細Dijkstra锛氭眰鍗曟簮銆佹棤璐熸潈鐨勬渶鐭矾銆傛椂鏁堟ц緝濂斤紝鏃堕棿澶嶆潅搴︿负O锛圴*V+E锛夈傛簮鐐瑰彲杈剧殑璇濓紝O锛圴*lgV+E*lgV锛=>O锛圗*lgV锛夈傚綋鏄█鐤忓浘鐨勬儏鍐垫椂锛屾鏃禘=V*V/lgV锛屾墍浠绠楁硶鐨勬椂闂村鏉傚害鍙负O锛圴^2锛夈傝嫢鏄枑娉㈤偅濂戝爢浣滀紭鍏堥槦鍒楃殑璇濓紝绠楁硶鏃堕棿澶嶆潅搴︼紝鍒欎负O锛圴*lgV + E锛夈備互涓婂唴瀹...
绛旓細杩厠鏂姞锛Dijkstra锛绠楁硶(鏈鐭矾寰勭畻娉)鏄敱鑽峰叞璁＄畻鏈虹瀛﹀鑹惧吂鏍悸疯开绉戞柉褰诲彂鐜扮殑銆傜畻娉曡В鍐崇殑鏄湁鍚鍥句腑浠绘剰涓や釜椤剁偣涔嬮棿鐨勬渶鐭矾寰勯棶棰樸備妇渚嬫潵璇达紝濡傛灉鍥句腑鐨勯《鐐硅〃绀哄煄甯傦紝鑰岃竟涓婄殑鏉冮噸琛ㄧず钁楀煄甯傞棿寮杞﹁缁忕殑璺濈銆 杩鏂交绠楁硶鍙互鐢ㄦ潵鎵惧埌涓や釜鍩庡競涔嬮棿鐨勬渶鐭矾寰勩傝开绉戞柉褰荤畻娉曠殑杈撳叆鍖呭惈浜嗕竴...
绛旓細Dijkstra绠楁硶涓鑸殑琛ㄨ堪閫氬父鏈変袱绉嶆柟寮忥紝涓绉嶇敤姘镐箙鍜屼复鏃舵爣鍙锋柟寮忥紝涓绉嶆槸鐢∣PEN,CLOSE琛ㄧ殑鏂瑰紡锛岃繖閲屽潎閲囩敤姘镐箙鍜屼复鏃舵爣鍙风殑鏂瑰紡銆傛敞鎰忚绠楁硶瑕佹眰鍥句腑涓嶅瓨鍦ㄨ礋鏉冭竟銆傚皢T涓《鐐规寜閫掑鐨勬搴忓姞鍏ュ埌S涓紝淇濊瘉锛氫粠婧愮偣V0鍒癝涓叾浠栧悇椤剁偣鐨勯暱搴﹂兘涓嶅ぇ浜庝粠V0鍒癟涓换浣曢《鐐圭殑鏈鐭矾寰勯暱搴︺傛瘡涓《鐐瑰搴斾竴...
绛旓細璺緞鎼滅储涓父鐢ㄧ殑Dijkstra绠楁硶鏄湪鍥捐〃涓壘鍒板崟婧愭渶鐭矾寰勭殑鏂规硶銆侱ijkstra绠楁硶鏄绠楁満绉戝涓潪甯歌憲鍚嶅拰閲嶈鐨勭畻娉曚箣涓锛屼富瑕佺敤浜庤В鍐冲浘璁轰腑鐨勫崟婧愭渶鐭矾寰勯棶棰樸傝繖閲岀殑“鍗曟簮”鎸囩殑鏄粠涓涓寚瀹氱殑璧峰鑺傜偣锛堟垨绉颁负“婧”鑺傜偣锛夊嚭鍙戯紝鎵惧埌鍒拌揪鍥句腑鎵鏈夊叾浠栬妭鐐圭殑鏈鐭矾寰勩傝繖涓畻娉曠殑...
绛旓細1 c:2 2 c:2 f:6 3 c:2 f:6 e:10 4 c:2 f:6 e:10 d:11 5 c:2 f:6 e:10 d:11 g:14 6 c:2 f:6 e:10 d:11 g:14 b:15
绛旓細缁撴灉濡涓嬪浘锛
绛旓細鏄竴涓В鍐冲姞鏉冨浘锛堜笉鍚礋鏉冮噸鐨勮竟锛涓粠涓涓《鐐瑰埌鍏朵綑鍚勪釜椤剁偣鏈鐭矾寰勯棶棰樼殑绠楁硶銆Dijkstra绠楁硶鏄竴涓泦 璐績绠楁硶 锛 骞垮害浼樺厛鎼滅储锛圔FS锛 鍜 鍔ㄦ佽鍒 浜庝竴韬殑鏈鐭矾寰勭畻娉曘侱ijkstra绠楁硶鐨勪富瑕佺壒鐐规槸浠庤捣婧愮偣寮濮嬶紝閲囩敤璐績绠楁硶鐨勭瓥鐣ワ紝姣忔閬嶅巻鍒板鐐硅窛绂绘渶杩戜笖鏈闂繃鐨勯《鐐圭殑閭绘帴椤剁偣锛岀洿鍒...
绛旓細Dijkstra(杩澃鏂壒鎷)绠楁硶鏄吀鍨嬬殑鍗曟簮鏈鐭矾寰勭畻娉曪紝鐢ㄤ簬璁＄畻涓涓妭鐐瑰埌鍏朵粬鎵鏈夎妭鐐圭殑鏈鐭矾寰勩備富瑕佺壒鐐规槸浠ヨ捣濮嬬偣涓轰腑蹇冨悜澶栧眰灞傛墿灞曪紝鐩村埌鎵╁睍鍒扮粓鐐逛负姝傛敞鎰忚绠楁硶瑕佹眰鍥句腑涓嶅瓨鍦ㄨ礋鏉冭竟銆傝G=(V,E)鏄竴涓甫鏉冩湁鍚戝浘锛屾妸鍥句腑椤剁偣闆嗗悎V鍒嗘垚涓ょ粍锛岀涓缁勪负宸叉眰鍑烘渶鐭矾寰勭殑椤剁偣闆嗗悎锛堢敤S琛ㄧず...
绛旓細浠ヤ笅鍥句负渚嬶紝瀵Dijkstra绠楁硶鐨勫伐浣滄祦绋嬭繘琛屾紨绀猴紙浠ラ《鐐 涓鸿捣鐐癸級锛氭敞锛 01锛 鏄凡璁＄畻鍑烘渶鐭矾寰勭殑椤剁偣闆嗗悎锛 02锛 鏄湭璁＄畻鍑烘渶鐭矾寰勭殑椤剁偣闆嗗悎锛 03锛 琛ㄧず椤剁偣 鍒伴《鐐 鐨勬渶鐭窛绂讳负3 绗1姝 锛氶夊彇椤剁偣 娣诲姞杩 绗2姝 锛氶夊彇椤剁偣 娣诲姞杩 锛屾洿鏂 涓《鐐规渶鐭窛绂...
绛旓細Dijkstra绠楁硶鐨勫叿浣撴楠わ細Dijkstra绠楁硶鍙堢О涓哄崟婧愭渶鐭矾寰勶紝鎵璋撳崟婧愭槸鍦ㄤ竴涓湁鍚鍥句腑锛屼粠涓涓《鐐瑰嚭鍙戯紝姹傝椤剁偣鑷虫墍鏈夊彲鍒拌揪椤剁偣鐨勬渶鐭矾寰勯棶棰樸傝G=锛圴锛孍锛夋槸涓涓湁鍚戝浘锛孷琛ㄧず椤剁偣锛孍琛ㄧず杈广傚畠鐨勬瘡涓鏉¤竟锛坕锛宩锛夊睘浜嶦锛岄兘鏈変竴涓潪璐熸潈W锛圛,j锛夛紝鍦℅涓寚瀹氫竴涓粨鐐箆0锛岃姹傛妸浠巚0...
