Re: shortest path in bipartite directed graph

On Nov 1, 10:09 pm, klochner <kloch...@xxxxxxxxx> wrote:
Are there any specialized algorithms for shortest paths in a
bipartite graph?

Specifically, I have a bipartite graph with two directed
edges between each pair of nodes, with d(x,y) = -d(y,x),
and I want to compute all-pairs shortest paths. I was
going to use floyd-warshall but thought there may be a
better algorithm out there.

I'm not so sure you can use F-W if you have negative distances. (Or
Dijkstra's algorithm, either.) Directed cycles with a total distance
of 0 would at least slow these algorithms down.

You have to be careful about negative distances, because a directed
cycles with a negative total sum. If you have one of those, then there
is no algorithm, because the minimum distance is negative infinity,
and you need to trace an infinite number of edges to find this out.

I would then consider the properties of your distance function (on the
edges), and try to make an algorithm based on those.

--- Christopher Heckman

.

Relevant Pages

  • My OPE & the Euclicidean TSP
    ... A little while back I posted for a while on a creative algorithm I ... and the two travelers ... To make it easier to imagine let's say the nodes are cities, ... choosing them such that their physical distance ...
    (comp.lang.java.programmer)
  • [SUMMARY] Shirt Reader (#140)
    ... All of the solutions used some variant of the Metaphone algorithm to match words ... It also uses the Levenshtein distance algorithm to see how far ... The expectations.rb file just fills a global Hash with some test cases. ... It works by applying the sound algorithm to each words then building ...
    (comp.lang.ruby)
  • Re: Determine if a moving object will pass within range of point
    ... Here's the corrected algorithm (modified version of my earlier post, ... Let the radius of the earth RE = 3958 miles. ... Compute the great circle distance D in radians between IP and TP. ... intercept point is near the tangent of the intercept radius. ...
    (sci.geo.satellite-nav)
  • Re: Data Structure Suggestions
    ... Pugh describes an algorithm for index ... assumes the existance of a "distance" field at each level in each node. ... Well, if I already have the position information, I ... deleting and inserting items effects subsequent nodes' ...
    (comp.programming)
  • Re: What I learned from Class Viewer
    ... displaced by such a trivially easy algorithm? ... by simply assuming that the weight is a distance between nodes ... while is not a valid circuit as a node is omitted. ...
    (comp.lang.java.programmer)
Quantcast