Re: Shortest path with intermediate nodes algorithm

acamposr@xxxxxxxxx wrote:
Well, Dijkstra's algorithm gives you back a shortest path tree. So, you
only need to run it once per intermediate node.

But... to run a TSP algorithm I'd need to get the shortest path from
each node to all the other ones so I get a full graph.

And if I run and all-pairs shortest path algorithm, I will get the
shortest path from each node from all the other ones in the graph (not
only the intermediate nodes)... so I could run taht algorithm only once
and store that distances: Distance[V,W] for all pair of vertices V,W.
But do you really recommend me that in a road map with thousands of
vertices?

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: A question about Dijkstras algorithm
    ... > Can we modify dijkstra's shortest path algorithm to find the shortest ... > path in a direct acyclic graph with all edges have positive weights? ... In fact, findind the longest path in a graph is an NP-Complete problem, ...
    (comp.theory)
  • Re: Shortish paths
    ... original graph. ... The functionality of Dijkstra's original algorithm can be extended ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Shortish paths
    ... For how many nodes and how many edges will the actual algorithm run ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Representing a Tree in Python
    ... other nodes in the graph. ... Dijkstra code you are using it may be possible to help you with the ... finds shortest path between only two nodes. ... And what is the best way to represent a tree in Python?. ...
    (comp.lang.python)
  • Re: Graph optimization
    ... represented in the form of a graph. ... I have to add up all the weights to form the ... algorithm is going to be the best for finding the shortest path ...
    (comp.programming)