老师
同学们好，欢迎来到江苏省名师空中课堂，那在这一课时我们将要学习数据与结构的第三小节，那在这一刻时，我们会使用一个案例，也就是取快递的最短路径，来综合运用我们之前所学的知识。取快递对于每个人在现代生活中都是非常熟悉的一个环节，那我们现在假设自己就是这个人。然后今天我们收到了很多的快递信息，但是有一个问题，我们收到的不同快递，它们分布在了不同的快递门店，那右边这张表格列出了每两个地点当中需要花费的时间。现在我们需要想达到一个目标，就是使用最短的时间取到所有的快递，然后回到家中。
老师
请同学们自己动动脑筋想想，我们怎么可以求出来这一个最短时间的路径？答案，你算出来了吗？这道题的答案是从家出发，然后经过 a C、b，然后再回到家，或者是把这个顺序颠倒过来，从家出发，先去b，然后去c，然后a，最后回到家。那我们这个答案是怎么算出来的？我们看一下运用到我们之前所学的数据结构的抽象的思想。我们可以把家以及快递门店抽象为一个顶点，然后把每个位置当中的线路抽象为一条边，那所花的时间就可以抽象为边上的权重。于是我们得到了这样的一张图，这张图是不是就变得熟悉了？就是我们上一课时所讲的图结构。
老师
那么接下来我们要如何求得取快递的最短路线，我们要列出每一种可能性，也就是从家出发。每一种可以走的路径我们都需要列出来。当列出来之后，以第一条路径为例，从家出发，然后走到a，走到b，走到c，最后回到家。然后我们编的权重可以把它写在树的枝上面，最后相加，可以得到每一种可能性所花费的时间。经过比较，我们找到了最短的路径所花费的时间，这里是 17 分钟，相应的它的逆序的路径也是 17 分钟。那从这个解决的办法中我们可以看到图的问题可以转化为数来求解。那接下来我们要用一个 Python 的代码去实现这个过程，请同学们先在 Python 中运行这个求最短路径的代码，然后去观察运行的结果。运行出来之后，我们要尝试去读懂代码。
老师
首先我们先来看这个程序的主程序部分。先看第 12 行，就是用字典来表示了刚才那张图的所有顶点边以及权重。大家可以回顾一下字典的表示方法是键值对的表示方法，用键来表示一个顶点，然后再嵌套一个字典来表示与它相连相连的顶点，相连顶点的权重表示为值，也就是在冒号的后面，如果一个顶点与许多的顶点相连接，我们就可以用逗号把它们键值对给分隔开来。最后就得到了第 12 行这样的表查看隐藏内容