Kiểm tra tồn tại đường đi dài hơn k từ đỉnh nguồn trong Python

Cho đồ thị, đỉnh nguồn và số k (độ dài đường đi). Kiểm tra có đường đi đơn (không chu trình) từ nguồn đến đỉnh bất kỳ có độ dài > k không.

Ví dụ: Đồ thị 9 đỉnh, source=0, k=64 → True (đường đi 0-7-1-2-8-6-5-3-4 độ dài 68 > 64).

Thuật toán DFS với backtracking

1. Biểu diễn đồ thị bằng danh sách kề adj[u] = [(v, w), ...].
2. Hàm solve(source, k, path):
   • Nếu k ≤ 0: return True.
   • Duyệt các đỉnh kề (v, w) của source.
   • Bỏ qua nếu v đã trong path.
   • Nếu w ≥ k: return True.
   • Đánh dấu v, đệ quy solve(v, k-w, path), bỏ đánh dấu (backtrack).
3. Khởi tạo path[source] = True, gọi solve(source, k, path).

Ví dụ code

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj = [[] for _ 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]:
                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] = True
        return self.solve(source, k, path)

nodes = 9
g = Graph(nodes)
edges = [(0,1,5),(0,7,9),(1,2,9),(1,7,12),(2,3,8),(2,8,3),(2,5,5),
         (3,4,10),(3,5,15),(4,5,11),(5,6,3),(6,7,2),(6,8,7),(7,8,8)]
for u,v,w in edges:
    g.insert_edge(u, v, w)
source = 0
k = 64
print(g.is_there_any_path(source, k))

Input

Đồ thị 9 đỉnh, source=0, k=64

Output

True