Pythonのソースからkを超える長さのパスがあるかどうかを確認します

グラフがあり、ソース頂点と数値kもあるとします。 kは、ソースから宛先までのグラフのパスの長さです。ソースから始まり、他の頂点（宛先として）で終わる単純なパス（サイクルなし）を見つけることができるかどうかを確認する必要があります。グラフを以下に示します-

したがって、入力がSource =0、k =64のような場合、0から7から1から2から8から6から5から3から4の単純なパスが存在するため、出力はTrueになります。このパスの長さは合計です。 64以上の68の距離。

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

• 順序ノードxノードの隣接行列adjを使用してグラフを定義し、エッジコストで埋めます

• 関数solve（）を定義します。これは、ソース、k、パスを取ります

• k <=0の場合、

  • Trueを返す

• i：=0

• iはadj[source]のサイズと同じではありませんが、実行してください

  • v：=adj [source、i、0]

  • w：=adj [source、i、1]

  • i：=i + 1

  • path [v]がTrueの場合、

    • 次のイテレーションに行く

  • w> =kの場合、

    • Trueを返す

  • path [v]：=True

  • Solve（v、k-w、path）がtrueの場合、

    • Trueを返す

  • path [v]：=False

• Falseを返す

• メインの方法から、次のようにします-

• path：=ノードと同じサイズのリスト、次にfalse値で埋める

• path [source]：=1

• リターンソルブ（ソース、k、パス）

例

理解を深めるために、次の実装を見てみましょう-

class Graph:
   def __init__(self, nodes):
      self.nodes = nodes
      self.adj = [[] for i in range(nodes)]
   def insert_edge(self,u, v, w):
      self.adj[u].append([v, w])
      self.adj[v].append([u, w])
   def solve(self,source, k, path):
      if (k <= 0):
         return True
      i = 0
      while i != len(self.adj[source]):
         v = self.adj[source][i][0]
         w = self.adj[source][i][1]
         i += 1
         if (path[v] == True):
            continue
         if (w >= k):
            return True
         path[v] = True
         if (self.solve(v, k-w, path)):
            return True
         path[v] = False
      return False
   def is_there_any_path(self,source, k):
      path = [False]*self.nodes
      path[source] = 1
      return self.solve(source, k, path)

nodes = 9
g = Graph(nodes)
g.insert_edge(0, 1, 5)
g.insert_edge(0, 7, 9)
g.insert_edge(1, 2, 9)
g.insert_edge(1, 7, 12)
g.insert_edge(2, 3, 8)
g.insert_edge(2, 8, 3)
g.insert_edge(2, 5, 5)
g.insert_edge(3, 4, 10)
g.insert_edge(3, 5, 15)
g.insert_edge(4, 5, 11)
g.insert_edge(5, 6, 3)
g.insert_edge(6, 7, 2)
g.insert_edge(6, 8, 7)
g.insert_edge(7, 8, 8)
source = 0
k = 64
print(g.is_there_any_path(source, k))

入力

nodes = 9
g = Graph(nodes)
g.insert_edge(0, 1, 5)
g.insert_edge(0, 7, 9)
g.insert_edge(1, 2, 9)
g.insert_edge(1, 7, 12)
g.insert_edge(2, 3, 8)
g.insert_edge(2, 8, 3)
g.insert_edge(2, 5, 5)
g.insert_edge(3, 4, 10)
g.insert_edge(3, 5, 15)
g.insert_edge(4, 5, 11)
g.insert_edge(5, 6, 3)
g.insert_edge(6, 7, 2)
g.insert_edge(6, 8, 7)
g.insert_edge(7, 8, 8)
source = 0
k = 64

出力

True