| Autor |
Mensaje |
MakeSurf
Nivel 4
Registrado: 19 Feb 2009
Mensajes: 97
Carrera: Informática
|
|
Hola a todos!
Alguien podria explicarme como funciona el algoritmo de Ford para hallar el camino mas corto entre dos vertices?. Estuve leyendo pero no me quedan claras un par de cosas, principalmente cuando cambia el valor de J? o sea cuando determino q se dio una vuelta ? a q se refieren con dar una vuelta?. Lo q no se tampoco es si inicialmente tengo q cambiar el valor de lamda para todos los vertices o solo aquellos que forman un camino. Estoy un poco confundido con este algoritmo y en todos lados dice lo mismo si aclarar mis dudas y no encuentro un ejemplo claro, asiq si no es demaciado pedir y alguien lo puedo explicar con un ejemplo muchisimas gracias. saludos.
|
|
|
|
|
|
 |
    |
|
SaaS
Nivel 7
Edad: 34
Registrado: 17 Dic 2008
Mensajes: 310
Ubicación: San Martín
Carrera: Informática
|
|
Como te va??
El algoritmo Bellman-Ford es relativamente simple... pero a veces lo expresan de una manera muuuuy rebuscada... basicamente es lo siguiente:
Etiquetás todos los vértices con infinito excepto el origen... que es aleatorio...lo elegís vos...
Para todo vértice actualizas la etiqueta de sus adyacentes... solo actualizando en caso de que la etiqueta actual sea mayor que la nueva...o sea... la nueva menor que la actual... como en Djistra..
Esto lo repetís n menos un veces siendo n la cantidad de vértices...
Después podes chequear si hay ciclos negativos... te fijas en cada vértice si su distancia obtenida es mayor que la distancia al adyacente más el peso de la arista que las une... eso para cada adyacente y cada vértice... en caso de que así sea tenes un ciclo negativo...
Todo esto lo podes expresar mucho mas formalmente y es ahí cuando parece mucho mas complicada la expresión de lo que realmente es... pero si tenes claro esto sale ...
Saludos 
|
|
|
|
|
|
  |
  |
|
MakeSurf
Nivel 4
Registrado: 19 Feb 2009
Mensajes: 97
Carrera: Informática
|
|
| Gracias por la respuesta! Pero aun me queda una duda, haciendo como decis sale facilemente y ademas como lo estas viendo podes ver la existencia de ciclos negativos, pero segun el algoritmo dado en clase esto se detemina por el valor de una J la cual aumenta de valor, mi problema es q no se cuando es o bajo q condicon aumenta de valor esa J, ya q en caso de J = | V | entonces existe ciclo negativo y termina el algoritmo. >Saludos
|
|
|
|
|
|
| |
|
|
SaaS
Nivel 7
Edad: 34
Registrado: 17 Dic 2008
Mensajes: 310
Ubicación: San Martín
Carrera: Informática
|
|
el algoritmo es masomenos así:
1. seteas todos los vértices en infinito
2. seteas el de origen en 0..
3. j=0
4. j = j + 1
5. para todo vértice v... sea S el conjunto vértices adyacentes a v (no se si es adyacencia... la cosa es que la arista sale de v y termina en w...los w). Para todo w en S actualizas la etiqueta.
6. Si j = cantidad de vértices menos uno pasas a 7... sino volves a 3
7. para todo vértice chequeas q la dsitancia obtenida NO sea mayor que la del adyacente mas el peso... si es así tenes un ciclo sino pasas a 8.
8. las etiquetas de cada vértice son la distancia mínima del origen al vértice...
como ves... j suma 1 cada vez que volvés a recorrer los todos los vértices... o sea... si tenés un grafo de 198 vértices ...puede q encuentres la mejor distancia a la primera vuelta (j=1)... sin embargo.. el algoritmo así como está... va a repetirse 197 veces...(hasta j=197)...
|
|
|
|
|
|
| |
|
|
SaaS
Nivel 7
Edad: 34
Registrado: 17 Dic 2008
Mensajes: 310
Ubicación: San Martín
Carrera: Informática
|
|
| rendís el martes makesurf??
|
|
|
|
|
|
| |
|
|
MakeSurf
Nivel 4
Registrado: 19 Feb 2009
Mensajes: 97
Carrera: Informática
|
|
| si estoy tratando de rendir nose si llego pero tratare
|
|
|
|
|
|
| |
|
|
MakeSurf
Nivel 4
Registrado: 19 Feb 2009
Mensajes: 97
Carrera: Informática
|
|
| |
|
|
SaaS
Nivel 7
Edad: 34
Registrado: 17 Dic 2008
Mensajes: 310
Ubicación: San Martín
Carrera: Informática
|
|
estamos en la misma... vamos a ver que sale 
me expliqué con lo de ford??
|
|
|
|
|
|
| |
|
|
GREgO
Nivel 8
Registrado: 21 Abr 2009
Mensajes: 771
Ubicación: New Belsen
Carrera: Electrónica
|
|
| Yo también espero llegar más o menos al martes. Si puedo, arranco hoy con los algoritmos.
|
|
|
|
_________________
El ser humano primero cree en Papá Noel,
Después en Dios,
Luego en la Izquierda,
Y finalmente advierte que la posta es Hermanos Bladimir
................
Ya salió la Bladimir Papel nº 3! Conseguila en el baño de tu Ugi's!
|
|
| |
 |
|
MakeSurf
Nivel 4
Registrado: 19 Feb 2009
Mensajes: 97
Carrera: Informática
|
|
| Bueno intentemos para el martes y si va mal nos juntamos en la semana para la ultima fecha. Si ahi agarre la mano con Ford. saludos
|
|
|
|
|
|
| |
|
|
mTswap
Nivel 3
Edad: 36
Registrado: 19 Feb 2010
Mensajes: 20
|
|
| Che para MakeSurf, prlea, Grego y todos q quieran unirse q les parece si nos juntamos el lunes para repasar todo antes del coloquio.Estoy en la misma q ustedes me falta todavía ver los algoritmos de caminos y toda la parte de redes de transporte igual pienso presentarme este martes.Avisen a q hora les vendría bien.
|
|
|
|
|
|
  |
|
|
SaaS
Nivel 7
Edad: 34
Registrado: 17 Dic 2008
Mensajes: 310
Ubicación: San Martín
Carrera: Informática
|
|
dale capo... en la biblio a la hora que les parezca... yo estaba estudiando con 2 pibes tmb q no andan por el foro así que les digo ....
yo el lunes creo q no tengo nada q hacer q no sea posponible así que tiren horario y caigo... tmpco voy a ir a las 8 de la matina pero caigo en la biblio
|
|
|
|
|
|
| |
|
|
MakeSurf
Nivel 4
Registrado: 19 Feb 2009
Mensajes: 97
Carrera: Informática
|
|
| yo me bajo che para el martes pq el mismo dia tengo que dar el oral de analisis numerico, hoy me llego la nota de aprobado el escrito. si llegan a juntarce para la siguiente fecha avisen me q me prendo de toque. mucha suerte este martes!!!
|
|
|
|
|
|
| |
|
|
GREgO
Nivel 8
Registrado: 21 Abr 2009
Mensajes: 771
Ubicación: New Belsen
Carrera: Electrónica
|
|
| prlea escribió:
|
dale capo... en la biblio a la hora que les parezca... yo estaba estudiando con 2 pibes tmb q no andan por el foro así que les digo ....
yo el lunes creo q no tengo nada q hacer q no sea posponible así que tiren horario y caigo... tmpco voy a ir a las 8 de la matina pero caigo en la biblio
|
Bueno, para no crear taaanto Offopic propongo que decidamos si nos juntamos o no, en este thread.
|
|
|
|
_________________
El ser humano primero cree en Papá Noel,
Después en Dios,
Luego en la Izquierda,
Y finalmente advierte que la posta es Hermanos Bladimir
................
Ya salió la Bladimir Papel nº 3! Conseguila en el baño de tu Ugi's!
|
|
| |
|
|
MakeSurf
Nivel 4
Registrado: 19 Feb 2009
Mensajes: 97
Carrera: Informática
|
|
| Si es despues del martes si, o sea para la ultima fecha, me dicen el dia y hs y ahi estare.
|
|
|
|
|
|
| |
|
|
|
|
