longestpath

Longest path refers to the problem of finding a path in a graph that has maximum total length or weight. In weighted graphs, the length of a path is the sum of the weights of the edges along the path; in unweighted graphs, the length is typically the number of edges. A key distinction is between finding a longest simple path (one that visits vertices at most once) and a general walk, which may repeat vertices. The longest simple path is a classic computational problem with strong intractability in general graphs.

In general graphs, the longest path problem is NP-hard, and its decision version—whether there exists a simple path of length at least k—is NP-complete. This means there is no known polynomial-time algorithm for solving it on arbitrary graphs, and practical approaches rely on exact methods for small instances or heuristics for larger ones. In undirected graphs, the problem remains hard; even for many special cases, finding exact solutions is impractical at scale. Conversely, many useful variants assume a directed acyclic graph (DAG).

For DAGs, the problem becomes tractable. By performing a topological sort followed by dynamic programming, one can compute the longest path in linear time relative to the number of vertices and edges. The standard approach processes vertices in topological order, updating the longest distance to each successor as dist[v] = max(dist[v], dist[u] + w(u,v)). This yields the longest path from a given source or the overall longest path in the DAG, with time complexity O(V+E).

Applications include the critical path method in project scheduling, where activity dependencies form a DAG and the longest path determines project duration. Other uses appear in routing, bioinformatics, and puzzle-solving, where exact solutions are feasible only for smaller graphs or when the underlying structure is acyclic.