- 前言
- 一、最短通路
- 题目描述
- 输入
- 输出
- 解题思路
- 代码
- 顶点
- 边
- 图
- Solution
- 运行测试
- 二、关键通路
- 题目描述
- 输入
- 输出
- 解题思路
- 代码
- 顶点
- 邻接表顶点
- 图
- 给定两点通过递归找出路径
- Solution（涉及排序）
- 运行测试
- 总结
前言
离散数学尹宝林第三版 书上第十章10.1 10.3 的通用算法（python给出）
一、最短通路 题目描述
给定一个带权有向图，试求从顶点 s s s到 t t t的最短通路
输入第一行四个由空格隔开的整数 n n n (顶点个数), m m m (边数), s s s (起点), t t t (终点)组成； 之后的 m m m 行，每行三个正整数 a a a , b b b , c c c ，表示一条从顶点 a a a 到顶点 b b b 长度为 c c c 的边。
输出一共两行 第一行：路径，从源点到终点依次输出所经过得节点；第二行：一个整数，表示从 s s s 到 t t t 的最短路长度。数据保证仅一条通路。
解题思路直接使用顶点和边的集合来建立图，用通常解法，即Bellman-Ford算法来求解最短路径，对所有边进行Relax操作，算法复杂度为 O ( V E ) O(VE) O(VE)，下面给出代码。
代码 顶点class GraphVertex:
def __init__(self, index):
self.index = index
self.d = float('inf')
self.pi = None
边
class GraphEdge:
def __init__(self, u, v, w):
self.e = (u, v)
self.w = w
图
class Graph:
def __init__(self, vertex_size, edge_size):
self._VertexSize = vertex_size
self._EdgeSize = edge_size
self._V = [GraphVertex(0)]
self._E = []
for __i in range(1, vertex_size + 1):
self._V.append(GraphVertex(__i))
def insert(self, __a, __b, __c):
self._E.append(GraphEdge(self._V[__a], self._V[__b], __c))
def get_vertex(self, node_index: int) -> GraphVertex:
return self._V[node_index]
@staticmethod
def __relax(u, v, w):
if v.d > u.d + w:
v.d = u.d + w
v.pi = u
def bellman_ford(self, __s: GraphVertex) -> bool:
__s.d = 0
for __i in range(1, self._VertexSize):
for __j in self._E:
self.__relax(__j.e[0], __j.e[1], __j.w)
for __i in self._E:
if __i.e[1].d > __i.e[0].d + __i.w:
return False
return True
Solution
def find_path(__s: GraphVertex, __t: GraphVertex) -> None:
path = [__t]
__i = __t
while __i.pi != __s:
path.append(__i.pi)
__i = __i.pi
path = path[::-1]
print(__s.index, *[_.index for _ in path])
print(__t.d)
运行测试
if __name__ == '__main__':
n, m, s, t = map(int, input().split())
G = Graph(n, m)
s = G.get_vertex(s)
t = G.get_vertex(t)
for i in range(m):
a, b, c = map(int, input().split())
G.insert(a, b, c)
G.bellman_ford(s)
find_path(s, t)
二、关键通路
题目描述
朱憨憨要去虫虫的工厂打工，工厂给他安排了一个求关键通路的任务。朱憨憨很是苦恼：面对繁杂的工厂流水线，他是真的不知道怎么求，聪明的你能帮帮他吗？
输入第一行是四个由空格隔开的整数 n n n (节点个数), m m m (边数), s s s (源点), t t t (终点)。此后的 m m m 行，每行三个正整数 a a a, b b b, c c c, 表示一条从节点 a a a 到节点 b b b 的一条长度为 c c c 的边。（节点个数小于 15 个）
输出第一行输出关键通路的长度；
第二行到第 n + 1 n+1 n+1 行输出每一个顶点的 T E TE TE, T L TL TL 和缓冲时间；
最后一行按Hint中所给格式，输出所有的关键通路。（若有多条，则根据关键通路中节点的个数排序进行输出，长度相同则按字典序排）
解题思路对所有顶点进行拓扑排序，可以得到每个顶点的最早完成时间 ( T E o f V ) (TEspace ofspace V) (TE of V)和一个出栈序列，借由它们可以解出每个顶点的最迟完成时间 ( T L o f V ) (TLspace ofspace V) (TL of V)，又由 T E o f V TEspace ofspace V TE of V和 T L o f V TLspace ofspace V TL of V可以解出每条边的最早完成时间 ( T E o f E ) (TEspace ofspace E) (TE of E)和每条边的最迟完成时间 ( T L o f E ) (TLspace ofspace E) (TL of E)，通过对于每个顶点比较它的 T E o f E TEspace ofspace E TE of E和它邻接顶点的 T L o f E TLspace ofspace E TL of E，若相等，则可以添加进关键路径中。最后输出关键通路转化为输出一个图中两个顶点之间的所有通路问题，按输出格式使用key进行排序，输出格式这里不再给出，下面给出代码。
代码 顶点class GraphVertex:
def __init__(self, index):
self.index = index
self.indegree = 0
self.d = 0
self.adj = []
邻接表顶点
class GraphAdjNode:
def __init__(self, to, w):
self.to = to
self.w = w
图
class Graph:
def __init__(self, vertex_size, edge_size):
self.VertexSize = vertex_size
self.EdgeSize = edge_size
self.V = [GraphVertex(0)]
for __i in range(1, vertex_size + 1):
self.V.append(GraphVertex(__i))
def insert(self, __a, __b, __c):
self.V[__a].adj.append(GraphAdjNode(self.V[__b], __c))
self.V[__b].indegree += 1
def __topological_sorting(self) -> list:
etv = [0 for _ in range(self.VertexSize + 1)]
stack = []
out_of_stack_list = []
stack.append(self.V[1])
while stack:
__t = stack.pop()
out_of_stack_list.append(__t)
for __i in __t.adj:
__i.to.indegree -= 1
if 0 == __i.to.indegree:
stack.append(__i.to)
if etv[__t.index] + __i.w > etv[__i.to.index]:
etv[__i.to.index] = etv[__t.index] + __i.w
return [etv, out_of_stack_list]
def critical_path(self) -> list:
[etv, out_of_stack_list] = self.__topological_sorting()
ltv = [etv[self.VertexSize] for _ in range(self.VertexSize + 1)]
out_of_stack_list.pop()
while out_of_stack_list:
__t = out_of_stack_list.pop()
for __i in __t.adj:
if ltv[__i.to.index] - __i.w < ltv[__t.index]:
ltv[__t.index] = ltv[__i.to.index] - __i.w
ete = []
lte = []
cur = -1
__path = []
for __i in self.V:
for __j in __i.adj:
cur += 1
ete.append(etv[__i.index])
lte.append(ltv[__j.to.index] - __j.w)
if ete[cur] == lte[cur]:
__path.append([__i, __j.to, __j.w])
__j.to.d = __i.d + __j.w
return [etv[1:], ltv[1:], __path]
给定两点通过递归找出路径
def find_a_path(start, end, __stack, __ans):
__stack.append(start)
if start == end:
__ans.append([_.index for _ in __stack])
__stack.pop()
return
for __i in start.adj:
if __i.to in __stack and __i.to != end:
continue
find_a_path(__i.to, end, __stack, __ans)
__stack.pop()
Solution（涉及排序）
def find_all_path(__n: int, __path: list) -> list:
g = Graph(__n, len(__path))
__ans = []
__stack = []
for __i in range(g.EdgeSize):
g.insert(__path[__i][0].index, __path[__i][1].index, __path[__i][2])
find_a_path(g.V[1], g.V[-1], __stack, __ans)
return sorted(__ans, key=lambda x: (len(x), *x))
运行测试
if __name__ == '__main__':
n, m, s, t = map(int, input().split())
G = Graph(n, m)
s = G.V[s]
t = G.V[t]
for i in range(m):
a, b, c = map(int, input().split())
G.insert(a, b, c)
[TE, TL, Path] = G.critical_path()
print(f'Dis={G.V[-1].d}')
print(*['Node {}: TE= {:3d} TL= {:3d} TL-TE= {}'.format(i + 1, TE[i], TL[i], TL[i] - TE[i]) for i in
range(G.VertexSize)], sep='n')
print(find_all_path(n, Path))
总结
保持好的代码风格，仅提供实现接口，将尽量少的实现细节交给使用者。（转载请注明作者）
