问题描述：
上述问题可以使用动态规划的方法来解决。
下面是解决思路的具体介绍：
1. 最优子结构:
假设d[i][j]表示从起点1出发到达i及j两个顶点的最短路程之和。为此可以假设K为此段路程上与j相加的节点，则d[i][j] = d[i][k] + len[k][j]。证明：若存在一个更短的路径d[i][k]，则就应该存在更短的路径d[i][j]，，这与假设矛盾，因此得证。下面来寻找j相邻的节点，其中若i<j-1，则显然k=j-1,若i=j-1，则显然k属于(1,j-2)之间，为此得到如下的递推关系：d[i][j] = d[i][j-1]+len(j,j-1) i<j-1;d[i][j] = min(d[i][k] + len(k,j)),k属于(1,j-2)。最终输出的d[n-1][n]即可。对于路径的输出，只需要记录每次与j相邻的节点即可，也即记录k的值。具体实现稍后补充！！
版权声明：本文为博主原创文章，未经博主允许不得转载。
一只小狗在沙漠中旅行，找到了电线杆，结果还是憋死了，
