Re: Shortest path with intermediate nodes algorithm

OK, now I get it. Thanks for this detailed explanation.

No, because you don't need ALL the shortest distances, just the shortest
distances for interesting nodes.

Let V be the full set of thousands of vertices. Let U={u1,u2,...,un} be
the set of "interesting" vertices, the start, end, and required
intermediate vertices, which you have indicated may have about 20 elements.

To do the conversion to TSP you only need the full graph based on U, not
the full graph based on V. Start by building the graph M with U as the
vertices, and no edges.

Take e.g. Dijkstra's single-source shortest path algorithm. Run it with
u1 as source, but stop as soon as every element of {u2,u3,...,un} has a
known shortest path. Add edges to M between u1 and each of the other
elements of u, with weight equal to the shortest distance.

Now repeat for each ui in U, but stop as soon as every element of U with
index greater than i has been assigned a shortest distance.

The truncation does not affect the computational complexity. Each time,
an element for which you need the shortest distance could be the last
one to be completed. However, I suspect it may improve performance in
practice.

With thousands of nodes, unless you already have a lot of edges, it
would be worth while to use e.g. a Fibonacci heap implementation of
Dijkstra's algorithm, complexity O(|E| + |V|log|V|), where E is the
original graph's edge set.

After |U|-1 iterations of this, M is the full graph with U as
vertices, and edge weights equal to the shortest distance between the
edge's nodes in the original graph. The whole conversion is
O(|U|(|E| + |V|log|V|)).

You would gain two benefits by doing the conversion:

1. The heuristic has a far smaller graph to consider.

2. The new problem is a very well studied one, with several heuristics.

Patricia

.

Relevant Pages

  • Re: Deriving power from broadcast signals
    ... conductivity and distance from the source of radiation. ... field strength is considered to be that part of the vertical component ... log-log graph paper and each is to be used for the range of frequencies ... inverse distance field is 100 mV/m at 1 kilometer. ...
    (sci.electronics.design)
  • Re: The Einstein Cult Index
    ... with distance, velocity, acceleration, pressure, temperature, etc. ... all remote oscillators in the universe change, ... and the DNA, Quantum Mechanics, and Classical Physics models ... shortest distance between two points is a curved line. ...
    (sci.physics)
  • Re: New challenge to Einstein from experiment?
    ... Just use odometer (distance), ... Th drawing above is a graph of the distance on the ... horizontal axis versus time on the vertical axis. ... >> would stretch along the energy axis to the point ...
    (sci.physics)
  • Re: New challenge to Einstein from experiment?
    ... Just use odometer (distance), ... Th drawing above is a graph of the distance on the ... horizontal axis versus time on the vertical axis. ... >> would stretch along the energy axis to the point ...
    (sci.astro)
  • Re: average distance in a graph
    ... starting from a conjecture by Peter Winkler that every graph has a ... Mean distance and the `four-thirds conjecture'. ... Combinatorics, graph theory, and computing, Proc. ...
    (sci.math.research)