Re: Shortest path with intermediate nodes algorithm

acamposr@xxxxxxxxx wrote:
Patricia Shanahan wrote:
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.

I am not sure it will be efficient, because I will have thousands of
nodes and arcs. An all-pairs algorithm would calculate the paths
between one source to *all* the nodes in the graph (if I am wrong,
please tell me). Using an point-to-point algorithm (like Dijkstra's or
A*) implies I will have to run it for each pair of intermediate nodes.
If have 20 intermediate nodes or more, it could be very very long.

Well, Dijkstra's algorithm gives you back a shortest path tree. So, you only need to run it once per intermediate node.
Isn't there any specific algorithm for this problem? I liked your idea,
but I see those disadvantages. However, the second part (traveling
salesman) can be very fast with an heuristic algorithm, but the first
one...


IMHO, a O(|IN|*|N|^2) preprocessing phase (where IN is the set of intermadiate node) is reasonable if we take into account that the problem is NP-hard.

The real problem I see is if you are constrained to visit each node of the original graph once. In that case, the reduction that Patricia is suggesting may lead to visiting a node twice.

Gregoire Dooms has implemented a global constraint that can be used for solving this particular problem. Path(G,n1,n2,I,w) holds if G is a simple path from n1 to n2 which total weight is I under the weight function w (http://cpgraph.info.ucl.ac.be/).

The idea would be to reduce the upper bound until no solution is found. Then, you will know that the last solution you found is the best one.

Luis
.

Relevant Pages

  • Re: Dijkstras algorithm for shortest paths
    ... which is the implementation of Dijkstra's algorithm for finding ... {Dijkstra computes the cost of the shortest paths ... imagine any way to find a shorter distance after this. ...
    (comp.programming)
  • Re: Shortest path with intermediate nodes algorithm
    ... All of them in any order (the shortest order). ... First calculate the shortest paths between each pair of mentioned nodes, ... using e.g. an all-pairs shortest paths algorithm. ...
    (comp.theory)
  • Re: Help to make a better shortest route program
    ... between two cities. ... long to execute. ... generally look at your algorithm and make it better. ... Shortest: integer; ...
    (comp.lang.pascal.misc)
  • Re: TSP in CL &/or Screamer
    ... Get a good initial guess using heuristic algorithm. ... Start generating the first permutation. ... check whether this might be the shortest path. ...
    (comp.lang.lisp)
  • Re: Solution for the Traveling Salesman Problem
    ... a node (city) cannot be on more than two edges. ... Your procedure need not produce a tour (a closed ... What happens when we apply your algorithm to these ... then that is the shortest tour. ...
    (sci.math)