Re: Shortish paths

The actual input patterns are something I will only learn if I decide
the project is feasible and invest the effort to collect them.

Remember I'm not asking for an algorithm, just for advice on what to
read to avoid re-inventing the wheel and get ideas.

Patricia


Casey Hawthorne wrote:
Do you have a small sample of what the input(s) are and what the
output(s) should be in each case.

For how many nodes and how many edges will the actual algorithm run
on.


On Thu, 10 Dec 2009 07:16:00 -0800, Patricia Shanahan <pats@xxxxxxx>
wrote:

That is very interesting. I do have secondary criteria for selecting a
single path from among all solutions, so I could use this idea removing
edges in reverse order of secondary desirability, and stop when I get a
solution that is both in range and has no seriously undesirable edges.

Indeed, I could begin the search in a subgraph that has only the nicest
edges, and back off the required edge quality until there is a solution.

However, I don't think it would find a path containing a cycle. All
results would have to be the shortest path in some graph, just not the
original graph. In my problem, it is OK for a vertex to appear twice.
Three times would be a bit too much.

Does anyone know of any literature on finding cycles containing a
particular vertex?

Patricia


Casey Hawthorne wrote:
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
--
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
    ... 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: 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)