Editing Shortest path problem (section)

==Related problems==
For shortest path problems in [[computational geometry]], see [[Euclidean shortest path]].

The shortest multiple disconnected path <ref>{{cite journal |doi=10.1016/j.cpc.2005.01.020 |title=Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems |year=2005 |first=Martin |last=Kroger |journal=Computer Physics Communications |volume=168 |issue=3 |pages=209–232 |bibcode=2005CoPhC.168..209K }}</ref> is a representation of the primitive path network within the framework of [[Reptation theory]]. The [[widest path problem]] seeks a path so that the minimum label of any edge is as large as possible.

Other related problems may be classified into the following categories.

===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.

===Partial observability===
The [[Canadian traveller problem]] and the stochastic shortest path problem are generalizations where either the graph is not completely known to the mover, changes over time, or where actions (traversals) are probabilistic.<ref>{{cite journal |last1=Bar-Noy |first1=Amotz |last2=Schieber |first2=Baruch |title=The canadian traveller problem |journal=Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms |date=1991 |pages=261–270 |citeseerx=10.1.1.1088.3015 }}</ref><ref>{{cite conference |last1=Nikolova |first1=Evdokia |last2=Karger |first2=David R |title=Route planning under uncertainty: the Canadian traveller problem |book-title=Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI) |pages=969–974 |url=https://www.aaai.org/Papers/AAAI/2008/AAAI08-154.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.aaai.org/Papers/AAAI/2008/AAAI08-154.pdf |archive-date=2022-10-09 |url-status=live}}</ref>

===Strategic shortest paths===
{{unreferenced section|date=December 2015}}
Sometimes, the edges in a graph have personalities: each edge has its own selfish interest. An example is a communication network, in which each edge is a computer that possibly belongs to a different person. Different computers have different transmission speeds, so every edge in the network has a numeric weight equal to the number of milliseconds it takes to transmit a message. Our goal is to send a message between two points in the network in the shortest time possible. If we know the transmission-time of each computer (the weight of each edge), then we can use a standard shortest-paths algorithm. If we do not know the transmission times, then we have to ask each computer to tell us its transmission-time. But, the computers may be selfish: a computer might tell us that its transmission time is very long, so that we will not bother it with our messages.  A possible solution to this problem is to use [[Vickrey–Clarke–Groves mechanism#quickest paths|a variant of the VCG mechanism]], which gives the computers an incentive to reveal their true weights.

=== Negative cycle detection ===
In some cases, the main goal is not to find the shortest path, but only to detect if the graph contains a negative cycle. Some shortest-paths algorithms can be used for this purpose:

* The [[Bellman–Ford algorithm]] can be used to detect a negative cycle in time <math>O(|V||E|)</math>.
* Cherkassky and Goldberg<ref>{{Cite journal |last1=Cherkassky |first1=Boris V. |last2=Goldberg |first2=Andrew V. |date=1999-06-01 |title=Negative-cycle detection algorithms |url=https://doi.org/10.1007/s101070050058 |journal=Mathematical Programming |language=en |volume=85 |issue=2 |pages=277–311 |doi=10.1007/s101070050058 |s2cid=79739 |issn=1436-4646}}</ref> survey several other algorithms for negative cycle detection.