Código de Python - Algoritmo Bellman-Ford para encontrar el camino más corto

Imágen de perfil

Algoritmo Bellman-Ford para encontrar el camino más cortográfica de visualizaciones


Python

estrellaestrellaestrellaestrellaestrella(1)
Actualizado el 06 de Agosto del 2018 por xve (Publicado el 05 de Agosto del 2018)
1.347 visualizaciones desde el 05 de Agosto del 2018. Una media de 77 por semana
El algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford) genera el camino más corto en un grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo)

Bellman-Ford


https://es.wikipedia.org/wiki/Algoritmo_de_Bellman-Ford

Requerimientos

Python 3

Versión 1
estrellaestrellaestrellaestrellaestrella(1)

Actualizado el 06 de Agosto del 2018 (Publicado el 05 de Agosto del 2018)gráfica de visualizaciones de la versión: Versión 1
1.348 visualizaciones desde el 05 de Agosto del 2018. Una media de 77 por semana
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
"""
        B---1---E
       /|\     /|\
      9 | 3   5 | 7
     /  |  \ /  |  \
    A   6   D   3   G
     \  |  / \  |  /
      2 | 2   6 | 4
       \|/     \|/
        C---9---F
"""
import math
 
# Cada elemento de este diccionario contiene una posicion del camino, y como 
# valor tiene una lista con el calculo del camino mas corto, y el origen del
# mismo
valores={
    "a":[math.inf,""],
    "b":[math.inf,""],
    "c":[math.inf,""],
    "d":[math.inf,""],
    "e":[math.inf,""],
    "f":[math.inf,""],
    "g":[math.inf,""]
}
 
# aquí establecemos cada uno de los caminos en una sola dirección y el coste
# que tiene cada camino
caminos=[
    ["a","b",9],
    ["a","c",2],
    ["b","c",6],
    ["b","e",1],
    ["c","f",9],
    ["d","b",3],
    ["d","c",2],
    ["d","e",5],
    ["d","f",6],
    ["e","f",3],
    ["e","g",7],
    ["f","g",4]
]
 
def setValores(origen,destino,valor):
    """
    Función que actualiza el valor del diccionario valores, actualizando
    el valor al mas vajo y indicando de de que punto viene el camino mas corto
    Tiene que recibir:
        origen -> punto inicial
        destino -> punto final
        valor -> valor de ese tramo + el valor que tiene el origen
    Devuelve True o False, dependiendo si ha disminuido el valor entre dos puntos
    """
    if valor<valores[destino][0]:
 
        # guardamos el nuevo valor mas bajo
        valores[destino][0]=valor
 
        # guardamos de donde viene el valor mas bajo
        valores[destino][1]=origen
        return True
    return False
 
# definimos el inicio y el destino
inicio="a"
final="g"
 
valores[inicio][0]=0
 
# realizamos un bucle hasta que no haya ningun otro cambio de valores
while True:
    cancel=True
 
    # recorremos cada uno de los caminos
    for i in caminos:
 
        # enviamos los datos del camino
        if setValores(i[0],i[1],valores[i[0]][0]+i[2]):
            cancel=False
 
        # enviamos los datos del camino de forma invertida
        if setValores(i[1],i[0],valores[i[1]][0]+i[2]):
            cancel=False
 
    # finalizamos el bucle cuando ya no hay ningun cambio en los valores
    if cancel:
        break
 
# iniciamos la busqueda del camino mas corto
camino=[final]
 
while True:
    if camino[-1]==inicio:
        break
    camino.append(valores[camino[-1]][1])
 
print("El camino mas corto desde el punto '{}' y el punto '{}' es: {}".format(inicio, final, camino[::-1]))



Comentarios sobre la versión: Versión 1 (1)

salva
21 de Octubre del 2018
estrellaestrellaestrellaestrellaestrella
Gracias!!!
Responder

Comentar la versión: Versión 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad

http://lwp-l.com/s4741  
Revisar política de publicidad