dijkstra算法（Pascal描述）

[delphi] view plain copy

1. const  
2. dim=6;  
3. max=200;  
4.   
5. var  
6. cost:array[1..dim,1..dim] of integer;  
7. i,j:integer;  
8.   
9. isfound:array[1..dim] of boolean;  
10. distance:array[1..dim] of integer;  
11. v0:integer;  
12. vtemp:integer;  
13. min:integer;  
14. counter:integer;  
15. c:integer;  
16.   
17. begin  
18. writeln('*** result ***');  
19. assign(input,'in.txt');  
20. reset(input);  
21. for i:=1 to 6 do  
22. begin  
23.     for j:=1 to 6 do  
24.     begin  
25.         read(input,cost[i,j]);  
26.         write(cost[i,j]:5);  
27.     end;  
28.     writeln;  
29. end;  
30.   
31. {init}  
32. v0:=1;  
33. for i:=1 to dim do  
34. begin  
35.     distance[i]:=cost[v0,i];  
36.     isfound[i]:=false;  
37. end;  
38.   
39. distance[v0]:=0;  
40. isfound[v0]:=true;  
41.   
42. {search}  
43.   
44. for counter:=1 to dim do  
45. begin  
46.     min:=max;  
47.     for i:=1 to dim do  
48.     begin  
49.         if (distance[i]<min) and (not isfound[i]) then  
50.         {if there is a path though i,j}  
51.         begin  
52.             min:=distance[i];  
53.             vtemp:=i;  
54.         end;  
55.     end;  
56.       
57.     writeln;  
58.     isfound[vtemp]:=true;  
59.       
60.     {update}  
61.     for i:=1 to dim do  
62.     begin  
63.         if (min+cost[vtemp,i]<distance[i]) and (not isfound[i]) then  
64.         begin  
65.             distance[i]:=min+cost[vtemp,i];  
66.             for c:=1 to dim do  
67.             begin  
68.                 write(distance[c]:5);  
69.             end;  
70.             writeln;  
71.         end;  
72.     end;  
73. end;  
74.   
75. for i:=1 to dim do  
76. begin  
77.     write(isfound[i]:5);  
78. end;  
79. writeln;  
80.   
81. for i:=1 to dim do  
82. begin  
83.   
84.     write(distance[i]:5);  
85. end;  
86. writeln;  
87. readln;  
88. end.