小朋友们好，大朋友们好！

我是猫妹，一名爱上Python编程的小学生。

【资料图】

和猫妹学Python，一起趣味学编程。

今日主题

什么是有向加权图？

如何查找最小路径？

如何用迪杰斯特拉算法求解最小路径。

你听过别针换别墅的故事吗？

美丽国外卖员凯尔·麦克唐纳利用互联网，用一枚红色曲别针开始与人交换，最终没花一分钱，换回一套漂亮的双层公寓！

交换路径是这样的：

一枚红色曲别针->一支鱼形钢笔->一个陶瓷门把手->烤炉->一个发电机->百威啤酒桶->一辆旧的雪地汽车->敞篷车->一份唱片合同->一栋双层别墅一年居住权

问题来了

咱们今天要做一个类似题目，不是直接换，是需要加钱的换。

如下图，你有一个别针，最终想换成摩托车。

当你用别针换限量版海报时，需要加钱5元。其他类似。

到底该怎么换呢？

上面这种图叫做有向权图，每条边都有有方向的，每条边上的数字叫做开销或者权重。

有向权图，查找找最小开销路线，最短路径算法。

在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。

有向权图的表示

我们可以用Python中字典来表示有向权图图：

最短路径

Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。

Dijkstra算法是很有代表性的最短路径算法。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra

艾兹格·W·迪科斯彻（Edsger Wybe Dijkstra1930年5月11日-2002年8月6日）是一位荷兰计算机科学家和数学家，被认为是计算机科学中最重要的人物之一。他在编程语言、程序设计方法、操作系统、分布式系统、并发性、软件工程等领域做出了杰出贡献。

1951年，Dijkstra进入阿姆斯特丹自由大学学习理论物理学，并于1956年获得博士学位。他曾经是荷兰数学中心的主任，也曾在阿姆斯特丹、伊利诺伊、德克萨斯州、新南威尔士等地的大学任教。

Dijkstra被广泛认为是算法和数据结构领域的创始人之一。他发明了许多著名的算法，例如Dijkstra算法、银行家算法和优先级队列。这些算法被广泛应用于图形理论、操作系统、网络路由等领域。

除此之外，Dijkstra还提出了结构化程序设计的概念，鼓励程序员将程序分解成小的模块，以便更易于理解和维护。这一思想对今天的软件工程实践仍具有深远的影响。

Dijkstra还是荷兰皇家科学院和美国国家工程院的成员，曾获得图灵奖、ACM杰出科学家奖等多项荣誉。

2002年8月6日，与癌症抗争多年后，在荷兰Nuenen自己的家中去世，享年72岁。

他是计算机先驱之一，他开发了程序设计的框架结构。

Edsger Wybe Dijkstra于1930年5月11日生于Rotterdam，他的父亲，Douwe Wybe Dijkstra是一位化学家，他的母亲，Brechtje Cornelia Kruyper是一位数学家，这种充满科学气息的家庭背景对于他的职业生涯乃至他的整个人生都有着深刻的影响。

主要成就

1.提出“goto有害论”;

2.提出信号量和PV原语;

3.解决了“哲学家就餐”问题;

4.Dijkstra最短路径算法和银行家算法的创造者;

5.第一个Algol 60编译器的设计者和实现者;

6.THE操作系统的设计者和开发者;

与高德纳并称为我们这个时代最伟大的计算机科学家的人。

上述诸多成就，都可以在大学计算机教材中学到哦！必考内容！

手动计算

先在一个张表格中把别针达到每个节点的开销和前向节点列出来。

对于不能直接到手的东西，都属于未知数。随着交换的进行，这张表中的未知将越来越少。

开始交换时，每次都选择开销最小的物品进行。

上图中，海洋世界门票开销最小，0。

第一次更新和前向节点如下(选择最小的0)：

别针->海洋世界门票->滑板车：30

别针->海洋世界门票->变形金刚玩具：35

第二次更新和前向节点如下(选择最小的5)：

别针->限量版海报->滑板车：20

别针->限量版海报->变形金刚玩具：25

综上两图，目前最小开支为20(别针->限量版海报->滑板车)

第三次更新和前向节点如下：

别针->限量版海报->滑板车->摩托：就是最小路径，花费220。

别针->限量版海报->变形金刚->摩托：就是最小路径，花费300。

神奇吧？

用Python实现

代码比较烧脑，可以多看几遍，结合注释，如下：

执行结果如下：

当前节点：别针 ，总开销为：0

当前节点：海洋世界门票 ，总开销为：0

当前节点：限量版海报 ，总开销为：5

当前节点：滑板车 ，总开销为：20

当前节点：变形金刚玩具 ，总开销为：25

当前节点：摩托 ，总开销为：220

最低开销为：220

{"限量版海报": "别针", "海洋世界门票": "别针", "滑板车": "限量版海报", "变形金刚玩具": "限量版海报", "摩托": "滑板车"}

好了，我们今天就学到这里吧！

如果遇到什么问题，咱们多多交流，共同解决。

我是猫妹，咱们下次见！