Talk:Shortest path problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Priority
 Field:  Discrete mathematics
WikiProject Computer science (Rated Start-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.

2007-2002 in approximately random order[edit]

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. ( 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. 07:32, 9 May 2006 (UTC)

single-pair vs. single-source[edit]

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

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

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 (talk) 11:07, 13 June 2008 (UTC)

Caption on the pic[edit]

"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 (talk) 18:42, 26 August 2010 (UTC)

sloppy addition[edit]

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.[citation needed]"
  • The correct second statement might be: However there are dedicated single-pair algorithms for some special graph classes, such as such as trees,[citation needed] linear graphs[citation needed] and cycle graphs[citation needed].

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

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. (talk) 08:29, 7 January 2013 (UTC)jp

Gif animation[edit]

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

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

Faster all-pairs shortest paths via circuit complexity <> Probably not but perhaps of interest to someone (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[edit]

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:

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

You may set the |checked=, on this template, to true or failed to let other editors know you reviewed the change. If you find any errors, please use the tools below to fix them or call an editor by setting |needhelp= to your help request.

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

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

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