Re: Graph optimization

Thad Smith wrote:
amol.panchabhai@xxxxxxxxx wrote:
I have a black box with a complex internal circuitry that is
represented in the form of a graph. I have to abstract the graph by
reducing the number of internal points and constructing cumulative
paths from each input to every possible output in case a path exists (a
series combination of edges). Each edge of the graph has a weight
associated with it. I have to add up all the weights to form the
resultant path.

Again what information do you have? If you know the graph and the
edge weights, you can use Dijkstra's algorithm for shortest path, if
that is what you are seeking.

I agree that the original poster's description isn't very clear, but
it sounds like they are trying to find many shortest paths (for all
possible combinations of inputs and outputs). Although Dijkstra's
algorithm is going to be the best for finding the shortest path
between a single pair of points, it seems there could be something
better for finding the shortest paths between several pairs of
points.

For example, consider a graph that looks like this:

(A, D): 5
(B, D): 3
(C, D): 2

(D, E): 10
(D, F): 15
(E, G): 9
(F, G): 11

(G, H): 1
(G, I): 2
(G, J): 4

You can see that finding the shortest path from A, B, or C to H, I, or J
is going to involve solving the subproblem of finding the shortest path
from D to G, since all paths from A, B, or C to H, I, or J will go
through D and then G. Repeatedly applying Dijkstra's algorithm (once
for each pair of nodes) would mean doing the work of solving this
subproblem multiple times.

On the other hand, Dijkstra's algorithm is probably fast enough...

- Logan
.

Relevant Pages

  • Re: Problem on an nxn grid
    ... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • 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: Shortest Path finding with mutating weights
    ... > Dijkstra's algo can be used to find shortest path between 2 nodes in ... > a weighted graph. ... > How to find shortest paths in a graph with mutating weights? ... Connections from one time slice to the another ...
    (comp.theory)
  • Re: a recurring favourite: shortest route :)
    ... fine if I check SPfor every point within the maximum range. ... If you could elaborate on how exactly your 'graph' of stars is stored, ... I could probably outline a way to implement Dijkstra's algorithm for you. ... and if you like the last point before that one in this shortest path. ...
    (comp.programming)
  • Re: Shortest path via ...
    ... Is the problem of finding the shortest path between two specific nodes ... in the graph that MUST include a specific set of /edges/, ... What's the algorithm you propose for the "nodes" case? ... and keeps refining the path every iteration. ...
    (comp.programming)