Search code examples
graphgraph-algorithmmathematical-optimization

minimize the difference between adjacent vertices for an un-directed graph

Suppose we have a undirected graph enter image description here and each vertex enter image description here has a initial weight enter image description here. The weight for each vertex is actually a rotation (in radium). I want to minimize the difference between enter image description here and enter image description here, enter image description here such that the difference enter image description here is less than enter image description here. In order to adjust the difference enter image description here, we are allowed to add or subtract multiples of enter image description here to enter image description here as needed, i.e. enter image description here.

I was wondering if there is a graph or optimization related method can solve this kind of problem?

Solution

  • Your question is a little bit confusing, but have you tried these algorithms?

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