2

我正在实施 dijkstras 算法来计算最短路径。我的问题是是否有一种更简洁的方法来实现以下理解（即没有if [b for a,b in G[x] if a not in X]!=[]]附加到最后）。

在下面，G 是一个图，其中它的键是图节点，每个节点都有一个表示其连接边的元组列表。所以每个元组都包含信息：（连接节点，到连接节点的距离）。X 是算法已经查看过的一组节点，A 是将那些已经找到的节点映射到距起始节点最短距离的字典，在本例中为节点 1。

更新：对不起，我给出了一个有效的例子，如果理解的最后一部分被删除，这是一个不起作用的例子。

G = {1: [(2, 20), (3, 50)], 2: [(3, 10), (1, 32)], 3: [(2, 30), (4, 10)], 4: [(1, 60)]}
X = {1,2,3}
A = {1: 0, 2: 20, 3:30}

mindist = min([A[x] + min([b for a,b in G[x] if a not in X]) for x in X if [b for a,b in G[x] if a not in X]!=[]])

问题是如何将 mindist 写成可以处理的理解min([[],[some number],[])。

最后一部分， if [b for a,b in G[x] if a not in X]!=[]] 只是删除了空列表，所以 min 不会失败，但是有没有更好的方法来编写该理解，所以没有空列表。

4

4 回答 4

2

Here's an idea:

minval = [float('+inf')]
min(A[x] + min([b for a, b in G[x] if a not in X] + minval) for x in X)
=> 40

The trick? making sure that the innermost min() always has a value to work with, even if it's a dummy: a positive infinite, because anything will be smaller than it. In this way, the outermost min() will ignore the inf values (corresponding to empty lists) when computing the minimum.

于 2013-08-09T22:59:49.450 回答
1

首先，空列表在布尔值中被认为是错误的，因此您不需要针对[];测试不等式。if [b for a,b in G[x] if a not in X]足够的。

您真正想要做的是生成一次内部列表，然后一次性测试和计算最小值。使用额外的内部“循环”执行此操作：

mindist = min(A[x] + min(inner) 
              for x in X 
              for inner in ([b for a,b in G[x] if a not in X],) if inner)

for inner over (...,)循环遍历生成列表一次的单元素元组，因此您可以在计算要传递给外部调用if inner的结果之前测试它是否为空 () 。A[x] + min(inner) min()

请注意，您不需要对该外部循环进行列表推导；这是一个生成器表达式，可以节省您构建一个列表对象，然后再次丢弃该对象。

演示：

>>> G = {1: [(2, 20), (3, 50)], 2: [(3, 10), (1, 32)], 3: [(2, 30), (4, 10)], 4: [(1, 60)]}
>>> X = {1,2,3}
>>> A = {1: 0, 2: 20, 3:30}
>>> min(A[x] + min(inner) 
...               for x in X 
...               for inner in ([b for a,b in G[x] if a not in X],) if inner)
40
于 2013-08-09T22:48:44.000 回答
1

好的，我不得不解开那个疯狂的列表理解来弄清楚你在说什么——我认为这大约是相同的代码：

dists = []
for x in X:
    newdists = [b for a,b in G[x] if a not in X]
    if len(newdists) > 0
        dists.append(A[x] + min(newdists))
mindist = min(dists)

这是一种消除相关测试的方法：

import sys

def newMin(values):
    if len(values) == 0:
        return float('inf')
    else:
        return min(values)

mindist = min(A[x] + newMin([b for a,b in G[x] if a not in X]) for x in X)

print mindist

输出：

40
于 2013-08-09T22:51:49.233 回答
0

这不是一个完整的解决方案，但由于您只是摆脱空列表，您可以缩短条件。空列表被评估为 False。包含任何内容的列表被评估为真。只需提供列表作为条件。这适用于所有空的内置数据类型。

于 2013-08-09T22:45:21.560 回答