Editing Shortest path problem (section)

===Paths with constraints===
Unlike the shortest path problem, which can be solved in polynomial time in graphs without negative cycles, shortest path problems which include additional constraints on the desired solution path are called [[Constrained Shortest Path First]], and are harder to solve. One example is the constrained shortest path problem,<ref>{{cite journal |last1=Lozano |first1=Leonardo |last2=Medaglia |first2=Andrés L |title=On an exact method for the constrained shortest path problem |journal=Computers & Operations Research |date=2013 |volume=40 |issue=1 |pages=378–384 |doi=10.1016/j.cor.2012.07.008}}</ref> which attempts to minimize the total cost of the path while at the same time maintaining another metric below a given threshold. This makes the problem [[NP-complete]] (such problems are not believed to be efficiently solvable for large sets of data, see [[P = NP problem]]). Another [[NP-complete]] example requires a specific set of vertices to be included in the path,<ref>{{cite book |last1=Osanlou |first1=Kevin |last2=Bursuc |first2=Andrei |last3=Guettier |first3=Christophe |last4=Cazenave |first4=Tristan |last5=Jacopin |first5=Eric |title=2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) |chapter=Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search |date=2019 |pages=3519–3525 |doi=10.1109/IROS40897.2019.8968113 |arxiv=2108.01036 |isbn=978-1-7281-4004-9 |s2cid=210706773 }}</ref> which makes the problem similar to the [[Traveling Salesman Problem]] (TSP).  The TSP is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start. The problem of [[Longest path problem|finding the longest path]] in a graph is also NP-complete.