CODEWITHSUNDEEP
algorithmgraph
Andrés
Andrés

Reputation: 881

Find a node in a Graph that minimizes the distance between two other nodes

I have a directed weighted graph G, with V vertices and E edges. Given two nodes in the graph, let's say A, and B, and given the weight of an edge A-B denoted as w(A, B), I need to find a node C so that max(w(A, C), w(B, C)) is minimal among all possibilities. By possibilities I mean all the values C can take. I don't know if it is completely clear, if it's not, I'll try to be more precise.

Upvotes: 1

Views: 2007

Answers (2)

mcdowella
mcdowella

Reputation: 19601

If by w(A, C) you really mean just the weight of an edge, then check all the nodes directly connected to A in turn, for total cost at worst the size of the graph, which is about as good as you could expect, assuming that you always need to read in the graph.

If by w(A, C) you mean the cost of the least cost path from A to C note that most path-finding algorithms, like http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm, in fact calculate the cost of the least cost path from A to every other node. You can solve your problem by looking at each node in turn if you have both the costs of getting from A to each node and the costs of getting from each node to B.

So do one run to work out the costs from A to every other node, then reverse the edges in the node and do another run to work out the least cost path from B to every other node in the reversed graph. Then for each node you have the cost of the least cost w(A, C) and the least cost w(C, B) so you can check each node in turn to see which is the best.

If your graph contains cycles, then you need something like http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm. If it has negative cycles, you are going to have a problem.

Upvotes: 2

Andrew Templeton
Andrew Templeton

Reputation: 1696

Not extremely clear what you asking, but here is one method for weighted distances: Treat it like a distance problem in R^n, where the actual rectilinear distance from C in any dimension is multiplied by the weight of that dimension of the path to obtain weighted distance. Make the entire expression the sum of the weighted distances and use the second-derivative test for maximization of this expression.

Cheers, Andrew

Upvotes: 0

Related Questions