这里介绍怎么求k短路
A*搜索 估价函数f[i]=g[i]+h[i];
在这里g[i]表示到达点i当前路径长，h[i]表示点i到达终点的最短距离
在搜索中，每次都取队列估价函数值最小的点，然后把它所能到达的点更新进入队列
显然这需要一个优先队列来维护（heap）
当终点第k次出队时，当前路径长度就是k短路
1 const max=1000000000; 2 type link=^node; 3 node=record 4 po,len:longint; 5 next:link; 6 end; 7 point=record 8 data,num:longint; 9 end; 10 var w,ow:array[0..1010] of link; 11 v:array[0..1010] of boolean; 12 d:array[0..1010] of longint; 13 heap:array[0..1004010] of point; //堆维护估价函数值 14 st,en,i,n,m,j,t,k,x,y,z,s:longint; 15 p:link; 16 17 procedure sift(x:longint); //堆的下沉 18 var i,j:longint; 19 begin 20 i:=x; 21 j:=i*2; 22 while j<=t do 23 begin 24 if (j+1<=t) and (heap[j].data>heap[j+1].data) then inc(j); 25 if heap[i].data>heap[j].data then 26 begin 27 swap(heap[i],heap[j]); 28 i:=j; 29 j:=i*2; 30 end 31 else exit; 32 end; 33 end; 34 35 procedure up(x:longint); //堆的上浮 36 var i,j:longint; 37 begin 38 i:=x; 39 j:=i div 2; 40 while j>0 do 41 begin 42 if heap[i].data<heap[j].data then 43 begin 44 swap(heap[i],heap[j]); 45 i:=j; 46 j:=i div 2; 47 end 48 else exit; 49 end; 50 end; 51 52 procedure add(x,y:longint;var q:link); 53 var p:link; 54 begin 55 new(p); 56 p^.po:=y; 57 p^.len:=z; 58 p^.next:=q; 59 q:=p; 60 end; 61 62 procedure dij; //求点到终点的距离 63 var p:link; 64 begin 65 fillchar(v,sizeof(v),false); 66 v[en]:=true; 67 for i:=1 to n do 68 d[i]:=max; 69 d[en]:=0; 70 p:=ow[en]; 71 while p<>nil do 72 begin 73 d[p^.po]:=min(d[p^.po],p^.len); //用邻接表重要的细节 74 p:=p^.next; 75 end; 76 for i:=1 to n-2 do 77 begin 78 x:=max; 79 y:=0; 80 for j:=1 to n do 81 if not v[j] and (d[j]<x) then 82 begin 83 x:=d[j]; 84 y:=j; 85 end; 86 if x=max then exit; 87 v[y]:=true; 88 p:=ow[y]; 89 while p<>nil do 90 begin 91 d[p^.po]:=min(d[p^.po],p^.len+x); 92 p:=p^.next; 93 end; 94 end; 95 end; 96 97 function astar(st,ed:longint):longint; 98 var p:link; 99 begin 100 heap[1].data:=d[st]; 101 heap[1].num:=st; 102 t:=1; 103 s:=0; 104 astar:=-1; 105 while t<>0 do 106 begin 107 x:=heap[1].num; //退队 108 y:=heap[1].data-d[x]; 109 swap(heap[1],heap[t]); 110 dec(t); 111 sift(1); 112 if x=en then 113 begin 114 s:=s+1; 115 if s=k then exit(y); 116 end; 117 p:=w[x]; 118 while p<>nil do //更新所有能到达的点入队 119 begin 120 inc(t); 121 heap[t].num:=p^.po; 122 heap[t].data:=y+p^.len+d[p^.po]; 123 up(t); 124 p:=p^.next; 125 end; 126 end; 127 end; 128 129 begin 130 readln(n,m); 131 for i:=1 to m do 132 begin 133 readln(x,y,z); 134 add(x,y,w[x]); 135 add(y,x,ow[y]); //注意有向需反向建边，快速求点到终点的距离 136 end; 137 readln(st,en,k); 138 if st=en then inc(k); //注意终点与起点重合时，路径为0的不算 139 dij; 140 writeln(astar(st,en)); 141 end.
而对于poj3255，求无向图的次短路也可以用A*，在n<=5000时还是可以过的，注意那时候就不需要反向建边了
k短路算法还是很好理解的