Editing LongestPath
The famous NP-complete problem (see Wiki:NpComplete) of finding the longest path within a graph -- that is, the longest series of steps from vertex to vertex without visiting any vertex more than once. : Also the subject of [http://www.poppyfields.net/filks/00155.html The Longest Path], a FilkSong of Billy Joel's "The Longest Time" Finding long paths in the FunWiki link graph was as an alternate challenge to WikiDegreesOfSeparation, because many of the shortest-path problems raised on that page were solvable by simple algorithms. As an NP-complete problem, LongestPath is effectively unsolvable by known algorithms on a graph the size of FunWiki. As opposed to the ''maximum shortest paths'' found on WikiDegreesOfSeparation, longest path candidates may be as meandering as they like, so long as they don't hit a node more than once. Example: * <nowiki> CampaignList -> PamelaRettig -> BrianRoney -> KissiWeb -> MichaelVrable -> HonorShowering -> MicahSmukler -> AnaGrams -> ChrisHanusa -> AskFunWiki -> FunWiki -> AboutFunWiki -> RobAdams -> EastDorm -> EastDormPresidents -> RobPrestegard -> RobPrestezog -> BadIdea -> DumbAss -> ShamikMaitra -> EastDormLounge -> BrideOfPinbot -> PinBitch -> EastiePerson -> CategoryHomePage -> JustinPava -> FunBallPeople -> AndrewSchoonmaker -> FunFact -> VenusDeMuddFountain -> TheRatio -> LookBook -> FreshMen -> FreshMan -> SillyFrosh -> AlexBobbs -> StarWars -> MaryPeter -> CaseDorm -> AtwoodDorm -> HarveyMuddCollege -> OutsideTheBubble -> TheBubble -> RealWorld -> BigRoom -> TheSun -> UndocumentedFeatures -> ManyOthers</nowiki> This path has 48 vertices and is not nearly as long as it might be. Constructing it was extremely boring, however. This is a task for the patient and/or obsessed mind. ---- Note: I've surrounded the above list in <nowiki> tags (and someone has helped me do the same on the StronglyConnectedComponents page) so that the pages don't have such a hefty impact on the very link graph they analyze. It also helps decrease the server load and response time.
Summary:
This change is a minor edit.
(Visit
Preferences
to set your user name.)
![[Home]](funwiki.png)
Editing LongestPath