数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究Python程序：查找从起始节点到结束节点的受限路径数量
假设我们有一个无向加权连通图。该图有n个节点，编号从1到n。从起点到终点的路径是一个节点序列，例如[z0, z1, z2, ..., zk]，其中z0是起始节点，zk是结束节点，并且在zi和zi+1之间存在一条边，其中0 <= i <= k-1。路径的距离是路径边上权重值的总和。令dist(x)表示节点n和节点x之间的最短距离。受限路径是一种特殊路径，它也满足dist(zi) > dist(zi+1)，其中0 <= i <= k-1。因此，我们必须找到从节点1到节点n的受限路径的数量。如果答案太大，则返回答案模10^9 + 7。
因此，如果输入如下所示：
则输出将为3，因为存在三条受限路径 (1,2,5), (1,2,3,5), (1,3,5)。
为了解决这个问题，我们将遵循以下步骤：
graph := 由给定边列表生成的图的邻接表
paths := 一个大小为(n+1)并填充0的数组
paths[n] := 1
dists := 一个大小为(n+1)并填充-1的数组
q := 一个队列，初始插入(0, n)
当q不为空时，执行以下操作：
(dist, node) := q的第一个元素，并将其从q中移除
如果dists[node]不等于-1，则
进入下一个迭代
dists[node] := dist
对于graph[node]的每个相邻节点v和权重w，执行以下操作：
如果dists[v]等于-1，则
将(dist + w, v)插入q
否则，当dists[v] < dists[node]时，
paths[node] := paths[node] + paths[v]
如果node等于1，则
返回paths[node] mod 10^9+7
返回0
示例
让我们看看下面的实现，以便更好地理解：
from collections import defaultdict from heapq import heappop, heappush def solve(n, edges): graph = defaultdict(dict) for u, v, w in edges: graph[u][v] = w graph[v][u] = w paths = [0] * (n+1) paths[n] = 1 dists = [-1] * (n+1) q = [(0, n)] while q: dist, node = heappop(q) if dists[node] != -1: continue dists[node] = dist for v, w in graph[node].items(): if dists[v] == -1: heappush(q, (dist + w, v)) elif dists[v] < dists[node]: paths[node] += paths[v] if node == 1: return paths[node] % (10**9 + 7) return 0 n = 5 edges = [(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)] print(solve(n, edges))
输入
5,[(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)]
输出
3
更新于：2021年10月6日
202 次浏览
广告