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

Imágen de perfil
Val: 2.436
Oro
Ha mantenido su posición en Python (en relación al último mes)
Gráfica de Python

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


Python

Publicado el 5 de Agosto del 2018 por Xve (291 códigos)
5.671 visualizaciones desde el 5 de Agosto del 2018
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(3)

Publicado el 5 de Agosto del 2018gráfica de visualizaciones de la versión: Versión 1
5.672 visualizaciones desde el 5 de Agosto del 2018
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 (3)

salva
21 de Octubre del 2018
estrellaestrellaestrellaestrellaestrella
Gracias!!!
Responder
Porfirio Choque Jimenez
3 de Mayo del 2019
estrellaestrellaestrellaestrellaestrella
Gracias por el aporte, me es de mucha ayuda en este lenguaje.
Responder
Francisco Mac Mac
21 de Noviembre del 2019
estrellaestrellaestrellaestrellaestrella
Muchas gracias amigo
Responder

Comentar la versión: Versión 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad

http://lwp-l.com/s4741