师：同学们，在这节课，我们将学习数据与结构的第三小节，通过取快递的最短路径案例，综合运用之前所学知识。取快递在现代生活中大家都很熟悉，假设我们收到很多快递信息，不同快递分布在不同门店。右边表格列出了每两个地点间所需花费的时间，我们的目标是用最短时间取到所有快递并回到家中。

　　大家自己思考下，怎么求出最短时间的路径呢？算出来了吗？答案是从家出发，经过a、C、b，再回到家；或者颠倒顺序，从家出发，先去b，然后去c，然后a，最后回到家。那这个答案怎么算出来的呢？运用之前所学数据结构的抽象思想，我们把家及快递门店抽象为顶点，各位置间的线路抽象为边，所花时间抽象为边上的权重，这样就得到了图结构，是不是很熟悉，就是上一课时讲的内容。

　　那如何求得取快递的最短路线呢？我们要列出每一种可能性，从家出发，把每条能走的路径都列出来。以第一条路径为例，从家出发，走到a，走到b，走到c，最后回到家。把边的权重写在“树的枝”上，最后相加得到每种可能性所花费的时间，经过比较，找到最短路径花费时间为17分钟，它的逆序路径也是17分钟。从这个解决办法能看出，图的问题可转化为树来求解。

　　接下来我们用Python代码实现这个过程。同学们先在Python中运行求最短路径的代码，观察运行结果，然后尝试读懂代码。我们先看程序主程序部分，第12行用字典表示刚才那张图的所有顶点、边以及权重。回顾一下，字典是键值对表示方法，用键表示一个顶点，再嵌套一个字典表示与它相连的顶点，相连顶点的权重作为值，写在冒号后面。如果一个顶点与多个顶点相连，就用逗号分隔键值对，最后得到第12行这样的表示方式。

　　这里给出了运行结果，大家大致浏览下，看看是不是刚才画树结构分析时所列的分析顺序。同学们仔细观察会发现，它实现了我们人工分析的过程，最后进行最短用时比较，输出了最短用时路线。回到程序，看13行，我们定义了变量mi，用于存储最短时间；14行定义变量Mir，用于存储最短路径，还定义了一个集合。回想下，集合中的数据元素不能重复，我们现在定义了包含所有点的全集。最后要打印一个函数，叫DFS，它有三个参数。我们从第一行看这个函数，分析它的三个参数，第一个参数v代表开始访问的第一个顶点，第二个参数s表示路径所花费的时间，这是个不断累计的过程，第三个参数r表示已经访问的顶点集合。接着看第二行代码，VSM、i还有Mir这三个变量是全局的。

　　第3行到第10行使用了if else语句。if语句这里，r是已访问的顶点集合，vs是所有顶点的集合，这句话意思是当访问完所有顶点才进行接下来的打印操作。我们从h点出发，还没走到下一个顶点，路径花费时间为0，当前顶点集合为h，所以不会执行if后面的语句，只会从else开始执行。else做了什么呢？看第7行代码for u in GV，这里v是h，for u in GV就列出了所有与h相接的顶点。看第12行表示的图结构，与h相接的顶点有a、b、c。for u in GV，就是要分别走这三条路径。