In [1]:
import sys
# Importando algunas librerías que utilizaremos

# Networkx para grafos
import networkx as nx

# Pandas
import pandas as pd

# Mostrar imágenes
from IPython.display import HTML

# Mathplotlib
import matplotlib.pyplot as plt

%matplotlib inline
plt.rcParams['figure.figsize'] = (20.0, 10.0)
In [2]:
aero = pd.read_csv('aero.csv')
aero.head()
Out[2]:
codigo pais nombre
0 ABC España Aeropuesto de Albacete
1 AEP Argentina Aeroparque Jorge Newbery
2 ARI Chile Aeropuerto Internacional Chacalluta
3 ARN Suecia Aeropuerto de Estocolmo-Arlanda
4 ASU Paraguay Aeropuerto Internacional Silvio Pettirossi
In [3]:
aero.set_index(["codigo"], inplace=True)
aero.head()
Out[3]:
pais nombre
codigo
ABC España Aeropuesto de Albacete
AEP Argentina Aeroparque Jorge Newbery
ARI Chile Aeropuerto Internacional Chacalluta
ARN Suecia Aeropuerto de Estocolmo-Arlanda
ASU Paraguay Aeropuerto Internacional Silvio Pettirossi
In [4]:
aero.loc["MEX"]
Out[4]:
pais                                      México
nombre    Aeropuerto Internacional Benito Juárez
Name: MEX, dtype: object
In [5]:
vuelos = pd.read_csv("vuelos.csv")
vuelos.head()
Out[5]:
origen destino distancia tiempo
0 AEP ABC 10277.81 119
1 HEL DME 9865.13 329
2 BYJ HEL 9123.15 476
3 BUD VVI 7895.17 362
4 SAL HEL 2453.67 298
In [6]:
vuelos.describe()
Out[6]:
distancia tiempo
count 183.000000 183.000000
mean 7782.752022 343.557377
std 3089.699308 209.248487
min 1131.840000 58.000000
25% 5401.665000 155.000000
50% 7895.170000 314.000000
75% 9978.840000 507.000000
max 13650.880000 834.000000
In [7]:
DG=nx.DiGraph()
for row in vuelos.iterrows():
    DG.add_edge(row[1]["origen"],
                row[1]["destino"],
                distancia=row[1]["distancia"],
                tiempo=row[1]["tiempo"])
In [8]:
DG.nodes(data=True)
Out[8]:
NodeDataView({'AEP': {}, 'ABC': {}, 'HEL': {}, 'DME': {}, 'BYJ': {}, 'BUD': {}, 'VVI': {}, 'SAL': {}, 'CGN': {}, 'SDQ': {}, 'LGG': {}, 'BOG': {}, 'CCC': {}, 'FOR': {}, 'MGA': {}, 'LIM': {}, 'PTY': {}, 'BOD': {}, 'MVD': {}, 'JKF': {}, 'ARI': {}, 'AUA': {}, 'EDI': {}, 'ASU': {}, 'FCO': {}, 'KEF': {}})
In [9]:
nx.draw_circular(DG,
                 node_color="lightblue",
                 edge_color="gray",
                 font_size=24,
                 width=2, with_labels=True, node_size=3500,
)
In [10]:
list(nx.all_shortest_paths(DG, source="JKF", target="ABC", weight=None))
Out[10]:
[['JKF', 'AEP', 'ABC'], ['JKF', 'SAL', 'ABC']]
In [11]:
list(nx.all_shortest_paths(DG, source="BUD", target="SAL", weight=None))
Out[11]:
[['BUD', 'SAL']]
In [12]:
list(nx.all_shortest_paths(DG, source="CCC", target="AEP", weight=None))
Out[12]:
[['CCC', 'AEP']]
In [13]:
list(nx.all_shortest_paths(DG, source="CCC", target="ABC", weight=None))
Out[13]:
[['CCC', 'CGN', 'ABC'],
 ['CCC', 'BYJ', 'ABC'],
 ['CCC', 'SAL', 'ABC'],
 ['CCC', 'AEP', 'ABC'],
 ['CCC', 'SDQ', 'ABC'],
 ['CCC', 'BUD', 'ABC']]
In [14]:
list(nx.dijkstra_path(DG, source="CCC", target="ABC", weight="distancia"))
Out[14]:
['CCC', 'LIM', 'SAL', 'ABC']
In [15]:
list(nx.dijkstra_path(DG, source="CCC", target="ABC", weight="tiempo"))
Out[15]:
['CCC', 'BUD', 'ABC']
In [16]:
def show_path(path):
    total_tiempo = 0
    total_distancia = 0
    
    for i in range(len(path)-1):
        origen = path[i]
        destino = path[i+1]
        distancia = DG[origen][destino]["distancia"]
        tiempo = DG[origen][destino]["tiempo"]
        
        total_tiempo = total_tiempo+tiempo
        total_distancia = total_distancia+distancia
        print("    %s -> %s\n    - Distancia: %s Tiempo: %s minutos" % (
            aero.loc[origen]["pais"],
            aero.loc[destino]["pais"],
            distancia, tiempo)
        )
    
    print("\n     Total Distancia: %s Total Tiempo: %s minutos \n" % (
            total_distancia, total_tiempo)
    )
In [17]:
show_path(['CCC', 'LIM', 'SAL', 'ABC'])

    Cuba -> Perú
    - Distancia: 4651.85 Tiempo: 358 minutos
    Perú -> El Salvador
    - Distancia: 1784.99 Tiempo: 151 minutos
    El Salvador -> España
    - Distancia: 2354.46 Tiempo: 586 minutos

     Total Distancia: 8791.3 Total Tiempo: 1095 minutos
In [18]:
def get_all_shortest_paths(DiGraph, origen, destino):
    print("*** All shortest paths - Origen: %s Destino: %s" % (
        origen, destino
    ))
    for weight in [None, "distancia", "tiempo"]:
        print("* Ordenando por: %s" % weight)
        paths = list(nx.all_shortest_paths(DiGraph,
                                          source=origen,
                                          target=destino,
                                          weight=weight))
        for path in paths:
            print("   Camino óptimo: %s" % path)
            show_path(path)
In [19]:
def get_all_shortest_paths(DiGraph, origen, destino):
    print("*** All shortest paths - Origen: %s Destino: %s" % (
        origen, destino
    ))
    for weight in [None, "distancia", "tiempo"]:
        print("* Ordenando por: %s" % weight)
        paths = list(nx.all_shortest_paths(DiGraph,
                                          source=origen,
                                          target=destino,
                                          weight=weight))
        for path in paths:
            print("   Camino óptimo: %s" % path)
            show_path(path)
In [20]:
get_all_shortest_paths(DG, origen="CCC", destino="ABC")

*** All shortest paths - Origen: CCC Destino: ABC
* Ordenando por: None
   Camino óptimo: ['CCC', 'CGN', 'ABC']
    Cuba -> Alemania
    - Distancia: 12399.77 Tiempo: 531 minutos
    Alemania -> España
    - Distancia: 8010.64 Tiempo: 541 minutos

     Total Distancia: 20410.41 Total Tiempo: 1072 minutos 

   Camino óptimo: ['CCC', 'BYJ', 'ABC']
    Cuba -> Portugal
    - Distancia: 12311.81 Tiempo: 583 minutos
    Portugal -> España
    - Distancia: 7609.21 Tiempo: 465 minutos

     Total Distancia: 19921.02 Total Tiempo: 1048 minutos 

   Camino óptimo: ['CCC', 'SAL', 'ABC']
    Cuba -> El Salvador
    - Distancia: 6543.65 Tiempo: 407 minutos
    El Salvador -> España
    - Distancia: 2354.46 Tiempo: 586 minutos

     Total Distancia: 8898.11 Total Tiempo: 993 minutos 

   Camino óptimo: ['CCC', 'AEP', 'ABC']
    Cuba -> Argentina
    - Distancia: 5777.54 Tiempo: 361 minutos
    Argentina -> España
    - Distancia: 12671.71 Tiempo: 105 minutos

     Total Distancia: 18449.25 Total Tiempo: 466 minutos 

   Camino óptimo: ['CCC', 'SDQ', 'ABC']
    Cuba -> República Dominicana
    - Distancia: 3451.71 Tiempo: 81 minutos
    República Dominicana -> España
    - Distancia: 8945.34 Tiempo: 372 minutos

     Total Distancia: 12397.05 Total Tiempo: 453 minutos 

   Camino óptimo: ['CCC', 'BUD', 'ABC']
    Cuba -> Hungría
    - Distancia: 4521.79 Tiempo: 58 minutos
    Hungría -> España
    - Distancia: 7881.63 Tiempo: 145 minutos

     Total Distancia: 12403.42 Total Tiempo: 203 minutos 

* Ordenando por: distancia
   Camino óptimo: ['CCC', 'LIM', 'SAL', 'ABC']
    Cuba -> Perú
    - Distancia: 4651.85 Tiempo: 358 minutos
    Perú -> El Salvador
    - Distancia: 1784.99 Tiempo: 151 minutos
    El Salvador -> España
    - Distancia: 2354.46 Tiempo: 586 minutos

     Total Distancia: 8791.3 Total Tiempo: 1095 minutos 

* Ordenando por: tiempo
   Camino óptimo: ['CCC', 'BUD', 'ABC']
    Cuba -> Hungría
    - Distancia: 4521.79 Tiempo: 58 minutos
    Hungría -> España
    - Distancia: 7881.63 Tiempo: 145 minutos

     Total Distancia: 12403.42 Total Tiempo: 203 minutos
In [21]:
def plot_shortest_path(path):
    print(path)
    positions = nx.circular_layout(DG)
    
    nx.draw(DG, pos=positions,
                node_color='lightblue',
                edge_color='gray',
                font_size=24,
                width=1, with_labels=True, node_size=3500, alpha=0.8
           )
    
    short_path=nx.DiGraph()
    for i in range(len(path)-1):
        short_path.add_edge(path[i], path[i+1])
    
    nx.draw(short_path, pos=positions,
                node_color='dodgerblue',
                edge_color='dodgerblue',
                font_size=24,
                width=3, with_labels=True, node_size=3000
           )
    plt.show()
In [22]:
def get_shortest_path(DiGraph, origen, destino):
    print("*** Origen: %s Destino: %s" % (origen, destino))
    
    for weight in [None, "distancia", "tiempo"]:
        print(" Ordenado por: %s" % weight)
        path = list(nx.astar_path(DiGraph,
                                  (origen),
                                  (destino),
                                  weight=weight
                                 ))
        print("   Camino óptimo: %s " % path)
        show_path(path)
        plot_shortest_path(path)
In [23]:
get_shortest_path(DG, origen="CCC", destino="ABC")

*** Origen: CCC Destino: ABC
 Ordenado por: None
   Camino óptimo: ['CCC', 'CGN', 'ABC'] 
    Cuba -> Alemania
    - Distancia: 12399.77 Tiempo: 531 minutos
    Alemania -> España
    - Distancia: 8010.64 Tiempo: 541 minutos

     Total Distancia: 20410.41 Total Tiempo: 1072 minutos 

['CCC', 'CGN', 'ABC']

 Ordenado por: distancia
   Camino óptimo: ['CCC', 'LIM', 'SAL', 'ABC'] 
    Cuba -> Perú
    - Distancia: 4651.85 Tiempo: 358 minutos
    Perú -> El Salvador
    - Distancia: 1784.99 Tiempo: 151 minutos
    El Salvador -> España
    - Distancia: 2354.46 Tiempo: 586 minutos

     Total Distancia: 8791.3 Total Tiempo: 1095 minutos 

['CCC', 'LIM', 'SAL', 'ABC']

 Ordenado por: tiempo
   Camino óptimo: ['CCC', 'BUD', 'ABC'] 
    Cuba -> Hungría
    - Distancia: 4521.79 Tiempo: 58 minutos
    Hungría -> España
    - Distancia: 7881.63 Tiempo: 145 minutos

     Total Distancia: 12403.42 Total Tiempo: 203 minutos 

['CCC', 'BUD', 'ABC']
In [24]:
path = ['CCC', 'ABC']
plot_shortest_path(path)

['CCC', 'ABC']
In [25]:
# https://en.wikipedia.org/wiki/Dijkstra's_algorithm
print("Dijkstra's algorithm")
HTML('<img src="https://upload.wikimedia.org/wikipedia/commons/2/23/Dijkstras_progress_animation.gif">')

Dijkstra's algorithm
Out[25]:
In [ ]: