The longest path problem, while NP-hard in general, is actually pretty easy to solve on directed acyclic graphs, which is what we have here:
- Directed: out of two neighbouring states, one is before the other in the alphabet, so the travel direction is one-way
- Acyclic: Since we can't go backwards in the alphabet, we can't get back to any state we've already visited
Let's see if we can't run the algorithm manually.
First, we'll need to find a topological order (no paths backwards anywhere in the list) for the states. There are several simple ways to find one on any DAG, but in our case, the alphabetical order already guarantees this property, so we get past this step for free.
Then, for each state, we check all the incoming paths (ie. that state's neighbours that are earlier than it in the alphabet). We set the state's LPEH (Longest Path Ending Here) as the maximum LPEH of the incoming paths, plus one. We also record the incoming path(s) we used for future reference.
State Best Neighbour(s) LPEH
- - - - - - - - - - - - - - - - - - - - -
Alabama - 1
Alaska - 1
Arizona - 1
Arkansas - 1
California Arizona 2
Colorado Arizona 2
Connecticut - 1
Delaware - 1
Florida Alabama 2
Georgia Florida 3
Hawaii - 1
Idaho - 1
Illinois - 1
Indiana Illinois 2
Iowa Illinois 2
Kansas Colorado 3
Kentucky Indiana 3
Louisiana Arkansas 2
Maine - 1
Maryland Delaware 2
Massachusetts Connecticut 2
Michigan Indiana 3
Minnesota Michigan 4
Mississippi Louisiana 3
Missouri Kansas,Kentucky 4
Montana Idaho 2
Nebraska Missouri 5
Nevada California 3
New Hampshire Massachusetts 3
New Jersey Delaware 2
New Mexico Colorado 3
New York Massachusetts, NJ 3
North Carolina Georgia 4
North Dakota Minnesota 5
Ohio Kentucky, Michigan 4
Oklahoma Missouri 5
Oregon Nevada 4
Pennsylvania Ohio 5
Rhode Island New York 4
South Carolina North Carolina 5
South Dakota Nebraska, ND 6
Tennessee Missouri, NC 5
Texas Oklahoma 6
Utah Nevada, New Mexico 4
Vermont New Hampshire, NY 4
Virginia Tennessee 6
Washington Oregon 5
West Virginia Virginia 7
Wisconsin Minnesota 5
Wyoming South Dakota 7
Then we pick the state(s) with the largest LPEH, and trace our route backwards using the Best Neighbour(s) list:
* West Virginia - Virginia - Tennessee - North Carolina - Georgia - Florida - Alabama
* West Virginia - Virginia - Tennessee - Missouri - Kansas - Colorado - Arizona
* West Virginia - Virginia - Tennessee - Missouri - Kentucky - Indiana - Illinois
* Wyoming - South Dakota - Nebraska - Missouri - Kansas - Colorado - Arizona
* Wyoming - South Dakota - Nebraska - Missouri - Kentucky - Indiana - Illinois
* Wyoming - South Dakota - North Dakota - Minnesota - Michigan - Indiana - Illinois
And unless we made a mistake along the way (not at all impossible, this is clearly a job for computers), reading those from right to left we get the complete list of the possible maximum routes.
For the question about "is the answer the same (but reversed) if the alphabet were reversed: Yes. All the same links would be there, every single one of them reversed. (Incidentally, this means we can also run the algorithm "in reverse gear" to find the answer, which is useful sometimes.)