Re: Shortest path with intermediate nodes algorithm

acamposr@xxxxxxxxx wrote:
All of them or some of them?...

A.L.
And if more than one of them, is the order fixed?

All of them in any order (the shortest order).


In that case, isn't it equivalent to traveling salesman?

First calculate the shortest paths between each pair of mentioned nodes,
using e.g. an all-pairs shortest paths algorithm.

Construct a new graph that just contains A, B, N1, N2, ..., with edges
connecting all vertices, (X,Y) edge weight equal to the cost of the
shortest path from X to Y in the original graph.

Then use any traveling salesman heuristic to solve the new problem.

Patricia





.