Tengo un grafo no dirigido a $G = (V, E)$ con nodos $V$ y los bordes $E$. Cada nodo $v$ tiene asociado un número de $n_v \in \mathbf{Z}$
Vamos a definir para cualquier par de nodos de $v, w \in V$ conectados por una arista $e \in E$, que a la red en el nodo $v$ con el nodo $w$ significa que establecemos $n_v = 0$ y establezca $n_w = n_w + n_v$. También definimos que el coste de una operación de compensación es $|n_v|f(e) \geq 0$ donde $f : E \rightarrow[0,\infty)$ es una función que describe el costo unitario de compensación de saldos entre el $v, w$.
Como un ejemplo:
En la imagen de arriba, los grandes números en cada nodo $v$ representa a $n_v$, y el de los números pequeños a lo largo de cada vértice $e$ representa a $f(e)$.
La Pregunta
Sólo por la compensación de los nodos, deseo hacer nodo $Z$ (verde) el único no-cero nodo. También quiero este hecho a un costo mínimo.
¿Alguien sabe de un algoritmo que hace esto a un costo mínimo?
En el ejemplo anterior, debemos neto nodo $A$ $C$ (con un costo de $|-2|\times1$) y $B$ $C$ (con un costo de $|-3|\times1$). Todos los nodos aparte de $Z$ entonces $0$, con un costo total de $5$.
La motivación
El uso de una aplicación para la motivación, imaginen que son una obra de caridad la distribución de la medicina a través de las ciudades en un país con un brote viral. La situación está evolucionando rápidamente ya que el virus se propaga o como la gente a estar mejor, y por lo que algunas ciudades pueden encontrar que tienen una escasez de medicina, mientras que otros tienen exceso de medicamento.
La situación puede verse como:
Tenemos que pasar de la medicina, desde donde hay un excedente de donde hay una escasez. La medicina puede transportarse de una ciudad a otra a través de la interconexión de carreteras. Hay un costo de transporte que participan en el transporte de cada unidad de medicamento. Equivalentemente, podemos mover a la gente de una ciudad hospital a otro (se supone el mismo coste del transporte como la medicina para la simplicidad, es decir, el grafo no dirigido caso).
Queremos asegurar que todas las ciudades tienen ni un superávit ni una escasez de la medicina. Cualquier excedente debe ser trasladado de nuevo al depósito. La escasez también debe ser trasladado de nuevo al depósito (esto representa el escenario cuando necesitamos crear y distribuir la nueva medicina de la medicina depot).
