Talk:Shortest path problem

2007-2002 in approximately random order

Shouldn't there be a section where various practical adaptions and optimizations can be discussed? For instance, finding the shortest path between a pair of vertex by using two dijkstras (forward and backward) simultaneously? rasmusdf 08:30, 14 June 2007 (UTC)

---

The algorithms doesn't really make clear what the shortest path actually is. Also, do we need f ≥ 0?

---

The algorithm given is not correct. For instance, if A is connected to B with cost 1 and B connected to C with cost 1 and A connected to C with cost 3, then the algorithm (for n = A and n' = C) will find the "shortest path" A-C with cost 3, even though A-B-C is shorter. AxelBoldt

---

Right you are :-( Next try JeLuF

---

Should there be "see also" here for Traveling salesman problem? David 10:48 Aug 9, 2002 (PDT)

---

The general definition at the top references a set of vertices V, but then chooses nodes n and n' from N. This is inconsistent.

Fixed. (204.50.113.28 22:34, 11 September 2006 (UTC))

---

Is the Spanish reference really appropriate on the English Wiki? I'm sure there are many decent English references available. 24.7.106.155 07:32, 9 May 2006 (UTC)

single-pair vs. single-source

“It turns out that there are no algorithms for solving the single-pair problem that are asymptotically faster than algorithms that solve the single-source problem.” [1]

Has that been proven, or do they just imply no-one has invented such an algorithm? Roman V. Odaisky 17:39, 24 May 2007 (UTC)

The wording seems to vaguely imply a proof ("it turns out" is a phrase rigorous mathematics people often use, and it doesn't use the word "known"), but I'll be damned if I have a source handy. Dcoetzee 07:59, 25 May 2007 (UTC)

TSP wording

I reverted back from this wording "[TSP] is not able to be perfectly solved on large graphs in a reasonable time" to the earlier wording "[TSP] is not known to be efficiently solvable." This version is more correct as it has the uncertainty, and I think the wording is cleaner. Also, I'm not sure we want to get into detail about all the caveats here—approximations and small instances and "reasonable time", plus special cases that are easier, or the average case time, etc.... Leave that all to the articles on the topic. But in the spirit of the revision I reverted, I added another wikilink that will hopefully fill in those details. --Nethgirb 20:21, 9 July 2007 (UTC)

TSP Classification Error

In the article, it is said that TSP is NP-Complete whereas it is "only" NP-Hard which is much worst since it is not even in NP

Cipher1024 (talk) 05:58, 15 May 2008 (UTC)

This is not really true. NP-Completeness deals with decision problems (the answer is yes or no), so saying "TSP is NP-Complete" is shorthand for saying "the decision version of TSP is NP-Complete". This is standard usage and is spelled out explicitly at Travelling salesman problem. Given that this is not a core issue for this article I think we can stick with the shorthand which is correct and more informative. --Nethgirb (talk) 09:56, 15 May 2008 (UTC)

Far from me be the idea of arguing more than is necessary but I'd like learn something if I am to be corrected. So here I would say that the view that TSP is NP-Hard is simpler since it does not refer to the specificities of the NP-Complete class namely that it applies to decision problems. To put TSP in NP-Complete, one has to introduce the variation of TSP which is a decision problem. Am I missing something here? Cipher1024 (talk) 03:42, 16 May 2008 (UTC)

I could go either way personally. To say "TSP is NP-complete", meaning "the decision version of TSP is NP-complete," implies something additional about the easiness of TSP: that a solution can be verified against a bound in polynomial time. However, seeing as the point here is that "TSP is harder to solve than SPP", the lower-bound "NP-hard" statement seems just as informative and concise. On the other hand, saying that both TSP and LPP are NP-complete allows a more direct comparison of those two problems (after all, the halting problem is NP-hard too, but it's rather more difficult than TSP). Dcoetzee 07:38, 16 May 2008 (UTC)

I suppose that for NP-hardness you don't need to know about the decision version of TSP so you could say that the NP-complete statement is more complicated. But let's put this in perspective: when you consider all you need to know to understand NP-hard or NP-complete, the decision-version bit of it is only about 3% of it. I.e., it's only so very slightly more complicated. Moreover, essentially everyone who has an idea what NP-hard means will also have an idea what NP-complete means; these are core concepts in computer science and they are essentially always introduced together.

So to me the added value of the greater information content vastly outweighs the very slight additional definition that you need to know. Anyway if the reader doesn't know, they can look it up...on wikipedia.... :-)

Along the lines of what Dcoetzee said, let me point out that the NP-completeness statement is worth it. Cipher1024 wrote above that it is "only" NP-Hard which is much worst since it is not even in NP. This is exactly the incorrect impression that readers might get if we said only that it was NP-Hard. The "show me the path" version is, in fact, not much worse than the decision version, because you can easily recover the full path by making a few judicious subroutine calls to the decision version. --Nethgirb (talk) 08:41, 16 May 2008 (UTC)

"The problem of finding the longest path in a graph is also NP-complete." can we have a citation for this? —Preceding unsigned comment added by 219.88.197.233 (talk) 11:07, 13 June 2008 (UTC)

Caption on the pic

"A graph with 6 vertices and 7 edges" But the graph actually has 14 edges since the distance between two vertices need not be commutative. Is this nit worth picking? Dmforcier (talk) 18:22, 8 August 2010 (UTC)

I don't understand your objection. The graph pictured has 7 edges. Counting the number of edges in a graph doesn't really have anything to do with distance. Are you talking about directed graphs? Meaning that a single undirected edge is really two directed edges? All of the graph theory books and papers I've ever read would count the number of edges in that graph as 7. —Preceding unsigned comment added by 131.136.242.1 (talk) 18:42, 26 August 2010 (UTC)

sloppy addition

the following recent addition removed from the article.

Actually, there isn't an algorithm to directly solve the single-pair shortest path problem on general graph. Finding single-pair shortest path would be done by solving single-source shortest path problem. However, there are algorithms to solve single-pair shortest path on special graphs, such as tree, linear graph and cycle graph.

It has several issues.

• The corrected first statement would be something like this: "All known algorithms for single-pair shortest path in general graphs are in fact algorithms for single-source shortest path problem, which can be stopped once the destination vertex is reached."
• The correct second statement might be: However there are dedicated single-pair algorithms for some special graph classes, such as such as trees, linear graphs and cycle graphs.

As you maight have noticed, these staements reqire citaitions. Please provide them and re-add accoringly into the article. - Altenmann >t 05:01, 18 November 2012 (UTC)

The first statement is not true. See e.g. bidirectional search. Perhaps what is meant is that there is no known single-pair shortest path algorithm whose worst case running time is better than that of the known single-source shortest path algorithms. —David Eppstein (talk) 07:27, 18 November 2012 (UTC)

Well, it is not exactly not true. While I admit I forgot to mention the runtime issue, the bidirrectional search is nothing but a heuristic in which two searches stop a bit earlier. Here again, which bidir search will be worst-case better than the Dijkstra-based one? - Altenmann >t 05:18, 19 November 2012 (UTC)

By the way, what's screwed up with the references in the table? And what's the mess with "Roadnetworks"? - Altenmann >t 05:18, 19 November 2012 (UTC)

The references in the Shortest path problem#Directed graphs with nonnegative weights table are not in the article; clicking on them seeks an anchor that is not on the page. I added Bellman with ref=harv, so clicking Bellman 1958 now works. Is that your concern? Glrx (talk) 16:25, 20 November 2012 (UTC)

Edit Made to "Perturbation Theory" Section Under Algorithms

Under the "Algorithms" section, perturbation theory is listed and it links to the Wiki article on perturbation theory. However, the wiki page on perturbation theory has absolutely no mention of perturbation theory on graphs for shortest path algorithms, and is devoted to the standard applications of perturbation theory only. Therefore, I am adding a "citation needed", even though the article links to the Wiki page, and I am also questioning whether the link to the Wiki page is even appropriate (but leaving it for now) until someone adds to that article "perturbation theory on graphs" or some other section that is relevant to the shortest path problem. 99.116.177.3 (talk) 08:29, 7 January 2013 (UTC)jp

Gif animation

I've made an animation to show the difference between algorithms: Bellman–Ford and Dijkstra. Do you have any comments for animation? Do you have any objections not to include animation to article? Artyom Kalinin (talk) 06:32, 10 December 2013 (UTC)

Shortest path Dijkstra vs BellmanFord

I find it hard to understand. Basically I think you have to already know the algorithms pretty well just to be able to figure out which of the two is which. In addition: What does a vertex being blue represent, in Bellman-Ford, since that algorithm does not have a concept of a vertex being finished? Why are you illustrating two algorithms neither of which is the best choice for the type of graph you use as an example? (It's a directed acyclic graph, for which a linear time algorithm is possible.) Why does your animation of Bellman-Ford only make one pass through the graph, and why do you think an input for which it gets the correct answer after only one pass is illustrative of how the algorithm works? —David Eppstein (talk) 07:00, 10 December 2013 (UTC)

Thanks for the answer. I studied this topic again and agree with you, that this animation is not suitable for Bellman-Ford algorithm.Artyom Kalinin (talk) 16:58, 16 December 2013 (UTC)

algebraic path problem

I should note here that Jungnickel's 4th ed. (2013) also covers the algebraic path problem (p. 97-102) although he uses rather quaint terminology from an algebraic perspective and still adds some restrictions that aren't really needed since Mohri's paper. So I'm not sure I want to cite/recommend Jungnickel's book as source for this particular topic. JMP EAX (talk) 22:31, 18 August 2014 (UTC)

The most recent paper that Jungnickel cites on that topic dates to 1986, which probably explains the issue. JMP EAX (talk) 22:38, 18 August 2014 (UTC)

Not my area, however is this useful or relevant

Faster all-pairs shortest paths via circuit complexity <http://arxiv.org/abs/1312.6680> Probably not but perhaps of interest to someone 92.25.12.77 (talk) 19:01, 16 November 2015 (UTC)

It's a theoretical rather than practical advance, but probably worth mentioning in the article (in the tables of results for all pairs, both undirected and directed). —David Eppstein (talk) 19:23, 16 November 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Shortest path problem. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20140821054702/http://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf to http://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 02:31, 3 December 2017 (UTC)

Diagram Scale

The Shortest Path node diagram provided seems to have a scale issue that is misleading in it's purpose when first looking at the objective of the article. The node distances for paths "10" and "11" are clearly not to scale to those marked "3" and "4". This throws off the reader in general, since the first initial observer's solution looking at the shortest distance path, is A-B-D-F, just based on relative scale alone. I think this detracts from the overall objective of the diagram - to demonstrate the optimal shortest path. SquashEngineer (talk) 13:20, 18 April 2019 (UTC)

Display of square roots

The square roots have the wrong format in sections like https://en.wikipedia.org/wiki/Shortest_path_problem#Directed_graphs_with_arbitrary_weights_with_negative_cycles

I think \sqrt should be used instead. Otherwise, the square roots will look off in other themes. Comeza (talk) 12:24, 1 June 2022 (UTC)

Linear programming formulation (Shortest path problem)

@David Eppstein removed the section on the ‎Linear programming formulation citing "unsourced and the wrong way to formulate this as an LP" and "No, it doesn't. Shortest path is just a standard LP. Find distances from start to all vertices minimizing sum of distances such that for each edge x→y, dist(y) ≤ dist(x) + length(x→y). No integer requirements anywhere". However, both these comments seem false to me. The most natural way to convert this problem into an LP is by first formulating it as an ILP (See section 10.2 of Optimization by K. Aardal et al.). This ILP can then be relaxed into an LP which will have the same optimal solution (see sections 10.2.1 and 10.2.2 of Optimization by K. Aardal et al..). The formulation of this LP as I read it at https://en.wikipedia.org/w/index.php?title=Shortest_path_problem&oldid=1126582726 is correct. The following formulations are equivalent to those on https://en.wikipedia.org/w/index.php?title=Shortest_path_problem&oldid=1126582726.

ILP Formulation:

Let (D, s, t, c) be an instance of Shortest Path, with A(D) the arc-set of D and n = |A(D)|. Let A be the node-arc incidence matrix of D where the first row corresponds to s and the last row corresponds to t. Then the corresponding ILP is the following:

${\begin{aligned}\min \sum _{(u,v)\in A(D)}c_{uv}f_{uv}\\{\text{ s.t. }}\quad A{\boldsymbol {f}}={\begin{bmatrix}1\\0\\\vdots \\0\\-1\\\end{bmatrix}}\\{\boldsymbol {f}}\in \{0,1\}^{n}\\\end{aligned}}$

The decision variables are the fuv = f(u,v), which take value 1 if the arc (u, v) is in the shortest path, and 0 otherwise. All these decision variable together form a vector f.

LP formulation:

Let (D, s, t, c) be an instance of Shortest Path. Then the LP relaxation where fuv ∈ {0, 1} is replaced with fuv ≥ 0 has an optimal solution with fuv ∈ {0, 1}. For the proof see

Primal:

${\begin{aligned}\min \sum _{(u,v)\in A(D)}c_{uv}f_{uv}\\{\text{ s.t. }}\quad A{\boldsymbol {f}}={\begin{bmatrix}1\\0\\\vdots \\0\\-1\\\end{bmatrix}}\\{\boldsymbol {f}}\geq \mathbf {0} \\\end{aligned}}$

Dual:

${\begin{aligned}\max \pi _{s}-\pi _{t}\\{\text{ s.t. }}\pi ^{\top }A\leq {\boldsymbol {c}}\\\pi \in \mathbb {R} ^{m}\\\end{aligned}}$

The decision variables in the dual are the $\pi _{u}$ for all u ∈ V. The restrictions in the dual make sure that each $\pi _{u}-\pi _{s}$ is at most the length of the shortest path from s to u. This means that any feasible dual solution essentially consists of an upper bound for the shortest path from s to u for each u ∈ V.

Not familiar with Wikipedia conventions so just putting this out there. BoostBack (talk) 14:43, 2 January 2023 (UTC)

The most natural way of formulating shortest paths as an LP is to make a variable for each pairwise distance between distinct vertices, require d(u,v) ≤ length(uv) when uv is an edge and d(u,v) ≤ d(u,x)+length(xv) otherwise, and ask to maximize the sum of the distances. No integer restriction needed. Works for all pairs or single source. —David Eppstein (talk) 17:06, 2 January 2023 (UTC)

I see, that seems very similar to this equivalent formulation of the dual to the LP? Where $\pi$ can be interpreted as labels for the distances and $l_{uv}$ the arc lengths.

${\begin{aligned}\max \pi _{s}-\pi _{t}\\{\text{ s.t. }}\pi _{u}-\pi _{v}\leq l_{uv}\\\pi \in \mathbb {R} ^{m}\\\end{aligned}}$

Then there, "d(u,v) ≤ length(uv) when uv is an edge" and "d(u,v) ≤ d(u,x)+length(xv) otherwise" follows from complementary slackness with the primal minimization problem like this:

$\pi _{u}\leq l_{uv}+\pi _{v}{\text{ for each (u,v) }}\in A{\text{ (using the dual constraints)}}$

$\pi _{u}=l_{uv}+\pi _{v}{\text{ for each (u,v) }}\in A{\text{ on the path (CS)}}$

So I think this is just comes down to duality? In my opinion, presenting the minimization as the primal seems as a more natural or intuitive start because the problem formulation is in terms of minimization. And in that case, the most intuitive start is using the integer restriction which can later be relaxed.

Thank you for your response, I could definitely be very wrong about all of this. BoostBack (talk) 18:08, 2 January 2023 (UTC)

Your last sentence suggests that you are trying to work from first principles rather than published sources. That is the wrong way to go about generating content for Wikipedia. —David Eppstein (talk) 19:02, 2 January 2023 (UTC)

I see, I shall refrain from editing but want to mention the importance of the entry of the LP formulation. It is referred to on multiple other webpages which now refer to the deleted section:

comparison of simplex and shortest path method, https://news.ycombinator.com/item?id=11845095.

This missing link is what caused me to investigate why it was gone in the first place. There are many other sources discussing this LP formulation of the shortest path problem, next to those from which I took the dual formulation (Optimization by K. Aardal et al.). However, I don't know how to properly edit the section so leaving this here for reference for further work. BoostBack (talk) 20:30, 2 January 2023 (UTC)