無向グラフの頂点がPythonでより低コストのパスを持っているかどうかを調べるプログラム

重み付きの無向グラフが与えられたとします。 2つの頂点とコスト「制限」を入力として受け取り、入力として指定されたコストよりも低いコストパスが存在するかどうかを確認する関数クエリを実装する必要があります。パスが存在する場合はtrueを返し、そうでない場合はfalseを返します。

したがって、入力が次のような場合

クエリは（0、2、10）、（3、1、30）、（4、3、30）です。

その場合、出力は次のようになります

False
True
True

コスト10の頂点0から2の間にパスがないため、最初のクエリの結果はFalseです。

コスト10の頂点3から1の間に、30未満のパスがあるため、2番目のクエリの結果はTrueになります。

3番目のクエリの結果はTrueです。これは、コスト30の頂点4から3の間に、30に等しいパスがあるためです。

これを解決するには、次の手順に従います-

• 重み：=グラフ内のさまざまな重みを含むリスト

• 接続：=ウェイトの接続を含むリスト

• 関数query（）を定義します。これにはp、q、limitが必要です

  • index：=ここでの重みの位置制限は、ソートされた順序を維持する左側に挿入できます

  • インデックスが0と同じ場合、

    • Falseを返す

  • connection [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))

出力

False
True
True