直接上代码（已测试通过）
另外，还有好多图，以及解答过程中的一些想法和思考，我写成博文了，请参阅：
一道物流运输规划题目的求解
# !/usr/bin/env python
# coding:utf-8
"""
1、利用复合数据类型表达有向图，要求每条边同时具有空间距离和时间距离。
2、编写Path类表示路径。该类应包括用复合数据类型表示的具体路径和费用，应具有增加节点产生新路径的方法。产生路径后，费用同步更新，且为只读属性。
3、编写有向图类DirectedGraph。该类应具有存储有向图数据的属性，具有产生所有可行路径的私有方法，具有从所有可行路径中搜索出空间和时间最短路径并打印到控制台的方法。
4、对于任意两个节点，输出空间和时间最短路径和费用。
"""
import math
from typing import NamedTuple
from zjgLib import *
class DirectedGraph(object):
__graph: dict = {} # {'A': {'B': (3, 6), 'C': (3, 8), 'D': (5, 2)}, ...}
_node = set() # {'A', 'B', ...}
DirectPath = NamedTuple('DirectPath', startnode=str, endnode=str, distance=int, time=int)
_dps = [] # direct paths
_path = [] # 临时路径
__results = []
# 构造函数，利用原始图初始化有向图类
def __init__(self, d):
if isinstance(d, dict):
self.__graph = d
else:
self.__graph = dict()
print('Sth error')
self.__parse()
# 解析节点、路径等的私有方法，构造中间数据包(_node, _dps)。
# 构造中间数据包不是必须的。当对程序运行的（时间、空间）要求有不同的需求时，可以优化。
def __parse(self):
for _key in self.__graph:
_startnode = _key
self._node.add(_key)
for _key1 in self.__graph[_key]:
_endnode = _key1
self._node.add(_key1)
_distance = self.__graph[_key][_key1][0]
_time = self.__graph[_key][_key1][1]
self._dps.append(self.DirectPath(_startnode, _endnode, _distance, _time))
# 通过递归生成所有可能的路径(其中包含了无效路径)
def __generatePath(self, start, end, path=[]):
if path.__len__() == 0:
path.append(list(start))
self.__generatePath(start, end, path)
else:
for en in path:
_current = en[-1]
if _current == '*':
pass
elif _current == end:
en.append('*')
else:
_nextnode = self._getNext(_current)
_en0 = en + []
for _en1 in _nextnode:
if _en1 in en:
if _en0 + list('*') not in path:
path.append(_en0 + list('*'))
else:
if _en0 + list(_en1) not in path:
path.append(_en0 + list(_en1))
path.remove(_en0)
self.__generatePath(start, end, path)
# 给定节点node，返回它所有可能的下一个节点的列表。
def _getNext(self, node):
_next = list(filter(lambda _en1: _en1.startnode == node, self._dps))
return [_en2.endnode for _en2 in _next]
# 给定路径 path, 计算路径的空间距离、时间距离
def _disofpath(self, path):
_disspace = 0
_distime = 0
for i in range(len(path)-1):
_li = list(filter(lambda _en1: _en1.startnode == path[i] and _en1.endnode == path[i+1], self._dps))
_disspace += _li[0].distance
_distime += _li[0].time
return _disspace, _distime
# 搜索start到end之间最短的路径，并输出
def searchPath(self, start, end):
path = []
self.__generatePath(start, end, path)
path = list(filter(lambda _en: _en[-1] == '*' and _en[-2] == end, path))
self.__results = [en[:-1] for en in path]
self.__results.sort(key=lambda x: len(x)) # 按所有路径的长度进行排序
print('The path from ', start, ' to ', end, ' is:')
_mindis = 1e99
_mintime = 1e99
for _path in self.__results:
_dis, _time = self._disofpath(_path)
_path.append((_dis, _time))
_mindis = _dis if _dis < _mindis else _mindis
_mintime = _time if _dis < _mintime else _mintime
if len(self.__results) == 0:
print('None')
else:
for _path in self.__results:
_flag = ''
if _path[-1][0] == _mindis:
_flag = '★'
if _path[-1][1] == _mintime:
_flag += '●'
print('{0}{1}'.format(_path, _flag))
print(f'Note: ★——distance Min, ●——time Min')
print(f'Min distance is {_mindis}, Min time is {_mintime}')
return self.__results
# 增加节点：如果start不存在，直接增加；如果start存在，而end 不存在，增加；两者都存在，后者更新前者。
def AddNode(self, d):
for en in d:
if self.__graph.get(en) is None:
self.__graph[en] = d[en]
else:
for en1 in d[en]:
self.__graph[en][en1] = d[en][en1]
self.__parse()
for en in self.__graph:
print(en, self.__graph[en])
def main():
d = {'A': {'B': (3, 6), 'C': (3, 8), 'D': (5, 2)},
'B': {'E': (5, 8)},
'C': {'D': (6, 1), 'F': (8, 3)},
'D': {'B': (7, 4), 'E': (11, 4), 'G': (4, 9)},
'E': {'D': (9, 2)},
'F': {'D': (3, 1), 'G': (2, 7)},
'G': {'E': (5, 8)}}
g = DirectedGraph(d)
path = g.searchPath('A', 'G')
# 演示节点增加
e = {'H': {'E': (6, 5), 'F': (3, 8)},
'A': {'G': (9, 7)},
'B': {'E': (5, 18)}
}
g.AddNode(e)
path = g.searchPath('A', 'E')
# 演示全部节点的：所有路径、最短距离、最短时间。如需要，转变为类方法。
for start in g._node:
for end in g._node:
if end != start:
g.searchPath(start, end)
print('-'*40)
if __name__ == '__main__':
main()
说明
- 类的构造
__init__ 没什么说的，很简单
一如既往地纠结：变量定义用什么好？类的属性、局部封装、
用了 _node {} 存放节点名称
_dps[]，用了NamedTuple，刚学，热乎的，所以显摆一下，觉得没什么，就是使程序可读性变强了。 - 正是使用了以上两个中间变量，所以解析函数
__parse变得较为简单。
它的功能是，将已知条件转化成四元列表（起点、下一结点、距离、时间），都是相邻的节点。 - 下面是求所有路径的递归函数
__generatePath
这个是整个方案的核心
写了两版，对自己都不太满意。
很想学大佬那样，用简洁的几个字符搞定复杂的问题，可惜没那能耐。（再说，内心真实的想法是内存不要钱、计算机够快，多定义几个冗余变量，如果有助于逻辑简化，值！）
两点说明：一是改变了提问者的函数参数设置，其实我还想再省，path可以用 self._path，其实完全不用变量也可以。要是我，个人习惯，不喜欢参数。总觉得自由一些。二是，返回值，由于是递归，不好在此设置，所以设置在searchPath 了，return self.__results。 - 用了两个局部函数：
_getNext 和 _disofpath searchPath 就简单了，这个基本是输出了。想玩什么花样都在这里玩。- 应提问者要求，增加了
AddNode 节点方法。感觉这个是多余。
有这功夫，干脆数据前处理，对类DirectedGraph重新初始化，反正_Parse的开销都很小。 - 好了，罗里吧嗦说这么多了。毕竟是练习题，如果真要用于全国2000+个城市节点的物流管理，还得推倒重写。只是有一些借鉴意义罢了。
本文由 大侠(AhcaoZhu)原创，转载请声明。
链接: https://blog.csdn.net/Ahcao2008
解题不易，请支持：一道物流运输规划题目的求解https://blog.csdn.net/Ahcao2008/article/details/129190761
