Dijkstra.pas 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150
  1. Program Dijkstra;
  2. Const
  3. Fin = 'input.in';
  4. Maxn = 10000;
  5. Type
  6. Link = ^Node;
  7. Node = Record
  8. v, w: Longint; {顶点和费用}
  9. Next: Link;
  10. End;
  11. Var
  12. Q, {最短路估计值最小堆}
  13. Q_Pos, {每个顶点在堆中的位置}
  14. Dist, {最短路估计值}
  15. Fa: Array[1 .. Maxn]of Longint; {每个顶点的前趋顶点}
  16. Map: Array[1 .. Maxn]of Link; {用临接表记录的图}
  17. n, m, s, t, Q_Tot: Longint;
  18. Procedure Init; {读入}
  19. Var
  20. i, a, b, c: Longint;
  21. p: Link;
  22. Begin
  23. Assign(Input, Fin);
  24. Reset(Input);
  25. Read(n, m, s, t);
  26. For i:= 1 to m do
  27. Begin
  28. Read(a, b, c);
  29. {将每条无向边拆成两条有向边插入}
  30. New(p);
  31. p^.v:= b; p^.w:= c;
  32. p^.Next:= Map[a];
  33. Map[a]:= p;
  34. New(p);
  35. p^.v:= a; p^.w:= c;
  36. p^.Next:= Map[b];
  37. Map[b]:= p;
  38. End;
  39. Close(Input);
  40. End;
  41. Procedure Swap(i, j: Longint); {交换堆中的两个元素i,j}
  42. Var
  43. k: Longint;
  44. Begin
  45. k:= Q[i]; Q[i]:= Q[j]; Q[j]:= k;
  46. Q_Pos[Q[i]]:= i;
  47. Q_Pos[Q[j]]:= j;
  48. End;
  49. Procedure Updata(i: Longint); {将顶点i上升到合适位置}
  50. Var
  51. j: Longint;
  52. Begin
  53. j:= i Shr 1;
  54. While (j >= 1) and (Dist[Q[j]] > Dist[Q[i]]) do
  55. Begin
  56. Swap(i, j);
  57. i:= j; j:= i Shr 1;
  58. End;
  59. End;
  60. Procedure Relax(i, j, w: Longint); {松弛操作}
  61. Begin
  62. If w >= Dist[j] Then Exit;
  63. Dist[j]:= w;
  64. Fa[j]:= i;
  65. Updata(Q_Pos[j]);
  66. End;
  67. Procedure Heapfy(i: Longint); {将顶点i下降到合适位置}
  68. Var
  69. j: Longint;
  70. Begin
  71. Repeat
  72. j:= i;
  73. {与左儿子比较}
  74. If (i Shl 1 <= Q_Tot) and (Dist[Q[i Shl 1]] < Dist[Q[i]])
  75. Then i:= i Shl 1;
  76. {与右儿子比较}
  77. If (i Shl 1 < Q_Tot) and (Dist[Q[i Shl 1 + 1]] < Dist[Q[i]])
  78. Then i:= i Shl 1 + 1;
  79. If i <> j then Swap(i, j);
  80. Until (i = j);
  81. End;
  82. Procedure Main;
  83. Var
  84. i: Longint;
  85. p: Link;
  86. Begin
  87. {最短路估计值初始化}
  88. For i:= 1 to n do
  89. Begin
  90. Q[i]:= i;
  91. Q_Pos[i]:= i;
  92. Dist[i]:= $FFFFFF;
  93. End;
  94. Swap(1, s); {将源点交换到堆顶}
  95. Q_Tot:= n; {堆的总元素设为顶点总数n}
  96. Dist[s]:= 0;
  97. {Dijkstra算法主过程}
  98. While Q_Tot > 1 do
  99. Begin
  100. i:= Q[1]; {取出堆顶元素}
  101. {删除取出的元素}
  102. Swap(1, Q_Tot);
  103. Dec(Q_Tot);
  104. Heapfy(1); {维护新堆}
  105. {对i连出的每条边进行松弛操作}
  106. p:= Map[i];
  107. While p <> Nil do
  108. Begin
  109. If (Q_Pos[p^.v] <= Q_Tot) then Relax(i, p^.v, Dist[i] + p^.w);
  110. p:= p^.Next;
  111. End;
  112. End;
  113. End;
  114. Procedure Print(i: Longint); {递归输出最短路径方案}
  115. Begin
  116. If (i = s)
  117. Then Write(i)
  118. Else Begin
  119. Print(Fa[i]);
  120. Write('--->', i);
  121. End;
  122. End;
  123. Begin
  124. Init;
  125. Main;
  126. If (Dist[t] < $FFFFFF) then
  127. Begin
  128. Print(t);
  129. Writeln;
  130. Writeln('Total Cost: ', Dist[t]);
  131. End
  132. Else
  133. Writeln('No solution');
  134. End.