A symmetric shortest-path table routing is a set of paths between all pairs of nodes in a graph such that the set is closed under path reversal, each path is a shortest path in the graph, and all paths with the same destination form a tree with a sink at the destination. Such a routing can be found for any finite, connected, undirected, positive-weighted graph by “salting” the edge weights so that all the shortest salted paths are unique while each one remains a shortest path in the original graph. A conjecture arises about whether every possible symmetric shortest-path table routing can be selected in this way by some edge weight salting. It turns out that this conjecture is false. This paper describes the search for counterexamples.

}, author = {Thomas L. Rodeheffer}, month = {May}, number = {MSR-TR-2013-58}, publisher = {Microsoft Technical Report}, title = {The Symmetric Shortest-Path Table Routing Conjecture}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=193114}, year = {2013}, }