Content deleted Content added
Rating article for WikiProject Mathematics. Quality: B / Priority: Low / Field: discrete (script assisted). Please report any errors on my talk page. |
Path vs. walk |
||
Line 77:
:This problem is [[NP-hard]], which can be shown via a reduction to the [[longest path problem]].
~ [[User:Booyabazooka|Booya <sup>Bazooka</sup>]] 20:50, 5 October 2009 (UTC)
== Path vs. Walk ==
The article consistently mentions ''path'' (which, by definition, is required to not duplicate any vertex) when it means ''walk'' (any sequence of adjacent edges, repeating vertices are possible). This should be imho fixed... In fact, Bellman-Ford algorithm finds shortest walks of length at most n. Requiring shortest ''paths'' is what makes the problem hard.
| |||