A game for the Traveling Salesman to play

Suppose we have a general graph of “cities” (nodes) and “roads” (edges) connecting some but not necessarily all pairs of cities, and we know with certainty the distance along a given road. In this world they have also invented the magical technology of bridges, and so some of the roads may cross without intersecting in the plane.

You may think I’m going to be describing the Traveling Salesman problem, but nope. Though there is a salesman here, and he is in a car and is able to travel, this one has gotten super bored on his long and unfulfilling journeys.

See, your modern Traveling Salesman has a GPS in his company car. He’d be stupid not to. It helps a lot. It helps so much in fact that it frees him from the sort of constant mental linear programming he was doing in the 1980s, and leaves him time to just drive and watch the scenery and hear fascinating podcasts and marvel at how similar radio stations are to one another. He has also listened to all the recorded books in the world.

Anyway, one of the mental games he has recently started playing is one he calls “teasing the GPS”.

His GPS routing algorithm is very good. No matter where his car is on the road graph, when he pushes the “route!” button, he is shown a colored path from his current position to the destination, and it is always the shortest path.

This has been very useful, but it’s left him even more bored. One day he pushes the button again after he sets off, and he notices that the shortest route doesn’t change. Which is even more boring, if you think about it.

So the other day he came up with a challenge for himself (and his GPS) that he calls “branching paths”. In this he intentionally ignores the path his GPS tells him to take, and instead tries to drive some other direction, pushing the GPS button as he goes, until he finds the exact place where the GPS route from some position along some road \(\vec{x}_a\) is different from the GPS route from an adjacent position \(\vec{x}_b\).

Then he pulls over the car, and takes a photo of the GPS showing both exactly equal routes highlighted on his GPS map, and takes a picture of his surroundings, and posts it to his Tumblr. So that’s fun, at least for a while, and he has met some nice people through Tumblr meetups.

But playing “branching paths” has lodged in his mind this sense that, in the road graph he has spent so much of his life driving, there are certain roads he sees often… but also others that he’ll never see at all.

One day not long ago he realized that the colored blue lines his GPS shows him, when it suggests a route from some here to some fixed destination there, could be thought of as “using up” those roads. He gets out the paper road map he has from the old days, and he colors in those roads on his map. And the next time he pushes the “route!” button on the GPS and gets a new path to the destination, he colors those roads in as well. Big black felt-tip marker lines, the sort that soak through the map, because that means “used up” doesn’t it?

One day when he’s buying gas, he glances over at the roadmap covered in partially-colored lines, and he poses himself a challenge.

“I’ll set a single destination for the GPS to track. It won’t even have to be at a city; a lot of the places I go are actually in the middle of long roads. And then I’ll have the GPS calculate the shortest route (or routes, if there are multiple routes the same length), and I’ll block out those portions of the road system on a fresh paper map from the rental agency. Then I’ll drive somewhere else, and push the GPS along the way, until some new shortest route from where I am to the destination is colored. And I’ll block out those road segments from the new GPS path. And so on.”

A look of determination comes on his face.

“And I’ll keep doing that, without changing the destination, until every stretch of every road in this territory is blocked out on my paper map.”

He smiles.

“And then I’ll be done. Fuck this driving shit. A fucking robot could do it. And also it can be a new Tumblr. They’ll love it.”

---

Given a general graph, not necessarily even planar (they have bridges you know), and some arbitrary destination along an edge somewhere or at a node, and an equally-arbitrary initial car position, where does the Salesman have to drive so that every segment of every road falls on at least one shortest path to the destination?

---

Also:

Given blah blah all the same stuff, where are the specific locations on the graph where the GPS path changes? Is there anything interesting about their relative positions? Can you find all of them? Are there any with higher multiplicity than two—that is where there are three or more equal-length shortest paths to the destination?