User:Thore Husfeldt/Path Algorithms

This is supposed to become a section under Path (graph theory)

Algorithms

In an unweighted graph, a path between two given vertices can be found in polynomial time using Depth first search, and the shortest path between to given vertices can be found using breadth first search. If the graph edges are weighted with positive values Dijkstra’s algorithm finds a shortest path between two given vertices. If the graph contains edges with negative weights, but no cycle has negative total weight, the Bellman–Ford algorithm finds a shortest path between to given vertices.

Most problems about finding paths in graphs are computationally hard. Finding a longest path in a graph is a canonical NP-hard problem, even if the graph is undirected an unweighted. In particular, the case of detecting if there is a path of maximal length, equivalently detecting a Hamiltonian cycle, is a canonical hard problem that appears on Karp’s 21 NP-complete problems. The fastest known algorithm to find a Hamiltonian path requires time $O(2^{n}n^{2})$ and polynomial space.

By a simple reduction, the shortest path problem for graphs that allow negative weight cycles is equivalent to the longest path problem and therefore NP-hard as well.