网站商城建设实训心得,怎么做天猫内部券网站,沈阳网站建设制作公司,wordpress 书籍主题----用教授的方式学习。
目录
12.1图的最优化问题
12.1.1最短路径：深度优先搜索和广度优先搜索 12.1图的最优化问题
我们下面研究另一种最优化问题。假设你有一个航空公司航线的价格列表，其中包括美国任意两个城市之间的航班价格。假设有3个城市A、B和C，从A出发经过B到达…----用教授的方式学习。
目录
12.1图的最优化问题
12.1.1最短路径：深度优先搜索和广度优先搜索 12.1图的最优化问题
我们下面研究另一种最优化问题。假设你有一个航空公司航线的价格列表，其中包括美国任意两个城市之间的航班价格。假设有3个城市A、B和C，从A出发经过B到达C的价格是从A到B的价格加上从B到C的价格。你可能会有以下几个问题：
·某两个城市之间最少的停留次数是多少？
· 某两个城市之间最便宜的飞机票价是多少？
· 某两个城市之间，如果停留次数不超过两次，那么最便宜的飞机票价是多少？
· 如果想访问多个城市，那么最便宜的路线是什么？
所有这些问题（以及许多其他问题）都可以轻松转化为图的问题。
图是由边连接起来的节点对象的集合，边也可称为弧，节点也可称为顶点。如果边是单向的，则图称为有向图。在有向图中，从节点n1到n2有一条边，我们就称n1为源节点或父节点，n2为目标节点或子节点。
以下定义了几个类，分别实现了对应于节点、加权边和普通边的抽象类型。
class Node(object): def __init__(self, name): """假设name是字符串""" self.name = name def getName(self): return self.name def __str__(self): return self.name
class Edge(object): def __init__(self, src, dest): """假设src和dest是节点""" self.src = src self.dest = dest def getSource(self): return self.src def getDestination(self): return self.dest def __str__(self): return self.src.getName() + '-' + self.dest.getName()
class WeightedEdge(Edge): def __init__(self, src,
