【最短路径问题】
    下图给出了一张地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度，求从A地到E地的最短路径。

【分析】本题可以利用深度搜索法求解，伪代码如下：
var
  s:未访问的城市集合;
  dist[i,j]:存储任意两个城市间的距离数组; {0表示不连通}
function search(city):integer;  {求城市city到城市E的最短距离}
  begin
    if city=E then search←0;
    else begin
           min:=maxint;
           for i取遍所有城市 do
             if dist[city,i]>0 and (i∈s)
             then begin
                    s←s-[i];
                    j←dist[city,i]+search(i);  {递归调用搜索过程}
                    s←s+[i];
                       if j<min then min←j;
                  end;
            search←min;
     end;
begin
  s←除E外所有城市；
  dist[A,E]←search(A);
end.

【效率评价】采用深度搜索的时间复杂度是W(n!)，效率很低。主要的原因就在于重复计算了很多路径值。如果把每次计算得到的最短距离保存下来就可以节省很多时间，于是产生了动态规划的思路。
【动态规划】从城市A出发，按照与城市A的路径长度划分阶段。
    阶段0包含的出发城市有{A}
    阶段1包含的城市有{B1，B2}
    阶段2包含的城市有{C1，C2，C3，D，C4}
    阶段3包含的城市有{D1，D2，D3}
    阶段4包含的城市有{E}
    这种划分的性质如下：
   （1）阶段 i 的取值只与阶段 i+1 有关，阶段 i+1 的取值对阶段 i 的取值产生影响；
   （2）每个阶段的顺序是确定的，不可以调换任两个阶段的顺序。
    从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市A，得到如下算法：
   
    map[i,j]←两个城市之间的距离数组
    dist[E]←0；
    for k←3 downto 0 do
      for x 取遍k阶段的所有城市 do
         begin
           dist[x]←∞；
           for y取遍k+1阶段的所有城市 do
              if dist[y]+map[x,y]<dist[x]
                 then dist[x]←dist[y]+map[x,y];
         end;
    输出dist[A];