Talk:Shortest path problem

From Wikipedia, the free encyclopedia

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)

[edit] 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)

[edit] 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)

[edit] 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)