在Python中找出无向图中是否存在顶点的较低代价路径的程序

假设我们有一个加权的无向图。我们必须实现一个名为query的函数，它将两个顶点和一个成本“限制”作为输入并检查是否存在比输入成本更低的路径。如果存在路径，则返回true，否则返回false。

因此，如果输入如下所示

并且查询为（0,2,10），（3,1,30），（4,3,30）。

那么结果将是

False
True
True

第一个查询的结果为False，因为没有从顶点0到顶点2成本为10的路径。

第二个查询的结果为True，因为顶点3到顶点1的成本为10的路径存在，小于30。

第三个查询的结果为True，因为顶点4到顶点3的成本为30的路径存在，等于30。

为了解决这个问题，我们将按照以下步骤进行 –

weights := 包含图中不同权重的列表
connections := 包含权重的连接的列表
定义函数query()。这将获取p，q，limit
- index := 在此处可以将limit插入到左侧以维护排序顺序
- 如果index和0相同，则
  - 返回False
- 如果connections [index-1，p]与connections [index-1，q]相同，则返回True

示例

让我们看一下以下实现，以获得更好的理解：

import bisect
class Solution(object):

   def __init__(self, n, edgeList):
      def find(node):
         if parent[node]!=node:
            parent[node] = find(parent[node])
         return parent[node]

      def union(x,y):
         parent[find(y)] = find(x)
         return

      parent = {i:i for i in range(n)}
      edgeList.sort(key = lambda x:x[2])
      self.connections = []
      self.weights = []
      for index,(i,j,weight) in enumerate(edgeList):
         union(i,j)
         if index!=len(edgeList)-1 and weight == edgeList[index+1][2]:
            continue
         self.weights.append(weight)
         self.connections.append([find(i) for i in parent])


   def query(self, p, q, limit):
      index = bisect.bisect_left(self.weights,limit)
      if index==0:
         return False
      return self.connections[index-1][p] == self.connections[index-1][q]

ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])
print(ob.query(0, 2, 10))
print(ob.query(3, 1, 30))
print(ob.query(4, 3, 30))

输入

ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])
print(ob.query(0, 2, 10))
print(ob.query(3, 1, 30))
print(ob.query(4, 3, 30))