Re: Shortest path with intermediate nodes algorithm

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.

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...

.

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: 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)
  • Re: Dijkstras algorithm for shortest paths
    ... {Dijkstra computes the cost of the shortest paths ... for each vertex v in V-S do ... Before I did anything I'd try to make sure I understood the algorithm. ... I presume 'C' is a two-dimensional array that holds the distance between any ...
    (comp.programming)