python graph 算法 + 卡车运输问题

更详细说明请加Q

Project Part 2
• 第2部分有两个task。
o 在这两个任务中，我们都说地图是无向加权图G，用图的边缘及其权重的元组的Python列表表示。 G中的每个元组（u，v，w）表示从顶点u到顶点v有一条边，使得边的权重为w。由于图形是无向的，因此您还需要考虑权重为w的从v到u的边。
o 给定从位置v1到位置vn的路径[v1，v2，...，vn]，我们说路径的权重或从v1到vn的距离（采用该路径）是路径上所有边的权重之和。（请注意，这不是加权图的标准表示形式。您可能会发现将输入图转换为邻接矩阵的邻接表很有帮助。）
o 假设：
 地图是连接的，即任何两个位置之间至少有一条路径。
 每个边缘的权重都是非负的。
o 示例：
 下图表示为[(ups,b,7), (ups,c,5), (b,c,8), (b,d,9), (c,d,2)]
 从ups到b再到d点的路径为[ups, b, d]

 

• Task 1 (part2Task1.py)
o 给定一张地图，其中一个确切的位置是邮政局，请以邮政局为源，实施BFS，DFS和Dijkstra三种算法。
o 具体来说，编写三个函数bfs，dfs和dijkstra。每个功能的输入包括
 地图G；
 邮局office 。
o 输出是一个名为path的Python dictionary ，其中的key是地图G中的位置，因此loc的path [loc]值是从办公室到loc的路径，该路径是通过相应算法计算得出的。 另外，path [office] = [office]。
 对于BFS和DFS，可以从所访问位置的顺序重建从办公室到每个位置的路径。
 对于Dijkstra的算法，从办公室到每个位置loc的路径是从办公室到loc的最短路径。
o 提示：
 如果有多个位置可供选择，请按字母顺序选择它们。
 对于此任务，我们不关心运输package。 我们需要做的就是遍历所有位置。您不需要Package或Truck类。
o 举例：
 鉴于下面的地图，ups是唯一的邮局，



 BFS：第一级只包含ups。 第二级包含b和c，它们的前身是ups。 第三级包含d和前任b，因为b在c之前排队。 因此，输出为
•
 DFS：输出为
•
 Dijkstra：从ups开始，我们从ups到其他每个位置的最短路径计算为：
•
 

• Task 2 (part2Task2.py)
o 给定具有多个邮局的地图，请将所有邮局中的所有包裹递送到其正确地址。
o 具体来说，编写一个函数deliveryService。该函数具有三个输入：
 一个地图G；
 卡车 truck；
 Python列表package，其中包括所有涉及的package，即所有office里的所有package。
o 输出是一对（deliveredTo，stop），其中
 deliveryTo是一个Python dictionary，其keys为package ids（不是package），而值为地址，因此deliveryTo [id] = addr表示名字为ID的package将交付给addr。 （输出的这一部分用于测试包裹是否已交付到正确的地址。）
 stop是一个Python list，其中包含卡车按顺序进行的所有停靠点。例如，如果将卡车在地址addr1初始化，则开车至ups1，然后开车至addr2，因此 stop = [addr1，ups1，addr2]。 （输出的这一部分用于计算卡车行驶的里程。）
o 限制：
 如果卡车在loc 1，则只有在地图上连接了loc 1和loc 2时，它才能行驶到loc 2。
 不要更改
• 输入图中的任何内容；
• 包裹的收货address和id，
• 在不正确使用removePackage功能的情况下不要更改package的office；
• 在不正确使用driveTo功能的情况下不要更改卡车的位置
 不要从packages参数中删除项目。
o 提示：
 尽量减少代码的运行时间和卡车的行驶里程