Re: Shortish paths

From Wikipedia

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm


The functionality of Dijkstra's original algorithm can be extended
with a variety of modifications. For example, sometimes it is
desirable to present solutions which are less than mathematically
optimal. To obtain a ranked list of less-than-optimal solutions, the
optimal solution is first calculated. A single edge appearing in the
optimal solution is removed from the graph, and the optimum solution
to this new graph is calculated. Each edge of the original solution is
suppressed in turn and a new shortest-path calculated. The secondary
solutions are then ranked and presented after the first optimal
solution.



On Wed, 09 Dec 2009 16:09:56 -0800, Patricia Shanahan <pats@xxxxxxx>
wrote:

I have a graph theory problem that is derived from a practical problem I
am trying to solve:

Given a directed weighted graph G(V,E), weight function W:E->R, an
ordered pair of nodes (s,e), and a real number range [min,max], find the
set of paths from s to e through G such that the total weight of each
path is in the range [min, max].

The solution does not need to be exact. It is sufficient if the result
usually contains most of the paths satisfying the conditions.

If you know of a good algorithm or heuristic for this, I would welcome a
pointer.

Otherwise, I am looking for guidance on what to read to get ideas about
it. I intend to begin by rereading the shortest path sections of Cormen
et. al. "Introduction to Algorithms".

The Wikipedia article http://en.wikipedia.org/wiki/Shortest_path_problem
also contains a link to
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8746&rep=rep1&type=pdf

BV Cherkassky, AV Goldberg, T Radzik: "Shortest paths algorithms: theory
and experimental evaluation", Mathematical programming, 1996

It seems to be fairly thorough, but is there something more recent I
should be reading instead? Is there a different direction I might start
from, other than shortest path?

Thanks,

Patricia
--
Regards,
Casey
.

Relevant Pages

  • 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: 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
    ... 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)
  • Re: Correctness of Dijkstra & A*
    ... overestimates the value of the shortest path from this node to the ... then the algorithm finds the optimal solution. ... but I need to know WHY the optimal solution always is found. ... Since I'm working with graph search, it needs to be consistent, so I'd like to be able to explain it with the assumption that it's consistent. ...
    (comp.graphics.algorithms)
  • 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)