Re: Shortest path with intermediate nodes algorithm

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?

Please, don't hesitate to tell me if I am saying something stupid and
thank-you very much for your answers.

.

Relevant Pages

  • 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)
  • Re: Graph Algorithm Question
    ... is there an algorithm to do the following: ... However the graph should contain no directed ... cycle whose weight is negative. ... If all the edges weighs are positive then shortest path from X to X is ...
    (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: which algorithm fits...
    ... >> for example, the 60th shortest path, that makes finding the right path ... >The most important thing that is still not known is how much memory you can ... >you can either do a depth first search, ... the algorithm appears to need some way to ...
    (comp.programming)
  • Re: Shortish paths
    ... Remember I'm not asking for an algorithm, just for advice on what to ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)