Dynamic programming solves a problem by storing solutions to overlapping subproblems and combining them according to a recurrence. Each dynamic programming state describes all information needed by subsequent choices. Evaluating states in an order where their dependencies are already available avoids recomputing the same subproblem. A typical optimization recurrence chooses the best transition; a decision recurrence instead combines feasible transitions with Boolean disjunction.
Use subset dynamic programming for a Hamiltonian path, with a Boolean dynamic programming state for each nonempty subset and . It is true exactly when there is a graph path using every vertex of once, using no other vertices, and ending at . The base and transition arewhere is the adjacency matrix of a directed graph.For correctness, a valid path ending at has some penultimate vertex ; removing yields exactly a path recorded by the corresponding predecessor state. Conversely, extending any true predecessor state by the edge produces a path visiting precisely once. Mathematical induction on proves the meaning of every state. Therefore the final disjunction is true exactly when a Hamiltonian path exists.
HamiltonianExists(A):
initialize every D[S,v] to false
for v in V:
D[{v},v] = true
for k = 2,...,n:
for S subset of V with |S| = k:
for v in S:
D[S,v] = any(D[S-{v},u] and A[u,v]
for u in S-{v})
return any(D[V,v] for v in V)There are possible states and at most predecessor checks per state. More exactly, the full set of ordered predecessor checks has size for . With constant-time adjacency matrix access and ordinary subset-indexed table access,The graph is normally assumed nonempty here. If the empty graph is admitted, return the chosen convention for its empty Hamiltonian path separately; it does not affect the bound.
A topological sort is a linear ordering of all vertices of a Directed acyclic graph in which every directed edge points from an earlier vertex to a later one. For example, with and , both and are topological sorts. They differ because neither edge nor directed path constrains the relative order of and .
Suppose a Directed acyclic graph has a Hamiltonian path . Every edge forces to precede in every topological sort. Transitivity forces the entire order , so the topological sort is unique and every consecutive pair is joined by the requisite edge. No edge can point backwards in this path order, since that edge together with part of the path would form a directed cycle.
Conversely, if a topological sort has an edge from every entry to the next, those edges form a graph path through all vertices exactly once. Thus the displayed order is itself a Hamiltonian path.
The unique topological ordering criterion says that uniqueness alone already forces the consecutive-edge condition. If were absent, swapping these adjacent entries would preserve every edge constraint: only their mutual order changes, and a reverse edge is already forbidden by the original topological sort. This would produce a second order. Consequently, for a Directed acyclic graph, having a Hamiltonian path, having a unique topological sort, and having consecutive edges in a topological sort are equivalent. The source's notation is read as “appears earlier”, consistent with its explicitly directed edges.
Compute any topological sort using a standard algorithm, then check its consecutive entries in the adjacency matrix:If all checks pass, the returned ordering is a Hamiltonian path. If a check fails but a Hamiltonian path existed, part (d) would force the computed topological sort to equal the unique path order, whose consecutive edges all exist. This contradiction proves the negative answer correct.
DAGHamiltonianPath(A):
order = TopologicalSort(A)
for j = 1,...,n-1:
if not A[order[j],order[j+1]]:
return "no Hamiltonian path"
return orderA standard topological sort scans all matrix rows and therefore takes time with this input representation; the subsequent edge checks take . The answer is consequently time, with auxiliary storage beyond the input matrix. An bound for an adjacency list must not be substituted for the stipulated adjacency matrix bound.
Articles by others on the same topic
There are currently no matching articles.