最短路径问题
下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，
连线上的数值代表道路长度。
现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设
DiS［x］为城市x到城市E的最短路径长度（x表示任意一个城市）；
map[i，j]表示i，j两个城市间的距离，若map[i，j]=0，则两个城市不通；
我们可以使用回溯法来计算DiS［x］：
var
S：未访问的城市集合；
function search(who{x})：integer； {求城市who与城市E的最短距离}
begin
if Who＝E Then Search←0 {找到目标城市}
Else begin
min←maxint； {初始化最短路径为最大}
for i 取遍所有城市 Do
if（map[Who，i]＞0{有路}）and（i S{未访问}）
then begin
S←S－[i]； {置访问标志}
j←map[Who，i]+ search(i)； {累加城市E至城市Who的路径
长度}
S←S＋[i]； {回溯后，恢复城市i未访问状态}
if j＜min Then min←j； {如果最短则记下}
end；{then}
search←min； {返回最短路径长度}
End；{else}
End；{search}
begin
S←除E外的所有城市；
Dis[a]←search（a）； {计算最短路径长度}
输出Dis[a]；
end．{main}
这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都
要访问，所以时间复杂度为O（n！），这是一个“指数级”的算法。那么，还有没有效率更
