This questions is based on a dispute, whether it would be possible to calculate 'nice' routes in Manhattan, if the road network is assumed to be a rectangular grid and, that 'nice' means that there is maximally one change between going in east-west direction and going in north-south direction, if the road-network graph only modeled the adjacency-relations between vertices and edges and contained no other information than the edge lengths.
As it turned out, the problem can be solved by incorparating a shortest-path count into e.g. Dijkstra's shortest path algorithm.

Another observation was, that a graph doesn't contain even cycles if every shortest path is unique (that observation could be used in algorithms aiming at finding a maximal bipartite spanner by removing a minimal set of vertices).

I have however not been able to find any mention of shortest-path counting as a means of solving certain problems of graph theory and I would like to know whether other problems are known, that benefit from shortest-path counting.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.