1
Dualidad:Dualidad:Problema del camino ms cortoProblema del camino ms corto
(*) Basado en parte:Combinatorial Optimization: Algorithms and Complexity.Papadimitriou y Steiglitz
2
Problema primalProblema primal Ya teniamos la formulacin del problema primal
Donde: x son las aristas en el camino ms corto c costo de las aristas b flujo producido en los nodos A matriz de indicidencias
3
Problema dualProblema dual Tomando la forma dual para un problema LP
con igualdad
Haciendo el cambio de variable: =
4
EjemploEjemplo Consideremos el siguiente grafo:
1
2
3
4
1
22
3
1
5
Formal PrimalFormal Primal Se tienen
6
Forma DualForma Dual El sistema de ecuaciones
se descompone en:
La funcin objetivo es maximizar
7
Complementary SlacknessComplementary Slackness Las condiciones para un problema LP nos dan
en particular de la 2a condicin se desprende: Cuando una arista est en el camino ms corto
(xij=1) la restriccin se debe cumplir con igualdad: i-j=cij
Cuando i-j
9
Ilustracin de la operacin del Ilustracin de la operacin del algoritmoalgoritmo
Click to add an outline
10
Implementacin distribuidaImplementacin distribuida Cada nodo i pregunta el valor j de sus vecinos. El nodo i actualiza su la distancia mnima a t
tomando el menor valor de sus vecinos, ms la distancia del nodo vecino al nodo i:
i=minj{cij+j}.
Algoritmo de Bellman-FordAlgoritmo de Bellman-FordProtocolos de enrutamiento por distancia vectorial: RIPProtocolos de enrutamiento por distancia vectorial: RIP
Top Related