Algoritmo de Dijkstra con Networkx en Python. Ruta más corta METRO-CDMX

[@victorsanz2720]

Les dejo el link al repositorio con el código para que hagan sus propios análisis. github.com/VikSanz/videos-canal/blob/master/metrocdmx_networkx.ipynb

[@JAIRODELCARPIO]

Hola, una pregunta con ese algoritmo de grafos puedo utilizar para realizar calculos en una red electrica utilizando kirchoff

[@joselerm3143]

@@JAIRODELCARPIO supongo que te iría bien para saber la Resistencia según la longitud de los conductores no? Si es así está bien pensado, yo creo que sí que se podría llegar a implementar y sin necesidad de Python. Aunque justo me estoy iniciando en estos algoritmos y no sabría decirte como ahora. Si llego a saber como implementarlo lo comentaré.

[@victorsanz2720]

@@JAIRODELCARPIO yo pienso que el planteamiento debiera ser distinto, me parece un buen ejercicio de implementación en redes . Lamento no haber contestado antes, es que si no me arroban no me aparece en notificaciones.

[@jimmyllontop1267]

@@JAIRODELCARPIO no, kirchoff no interviene con longitudes

[@alandavid533]

Bro es el mismo código el de aqui y el de github?

[@gabrielgt1999]

Justamente el canal que estaba buscando, ciencias de la computación con Python en español. Muy bueno. Saludos desde Bogotá-Colombia.

Que bien video. Muchas Gracias.

[@la_materia]

Victor, que gran trabajo y aporte, síguenos aportándonos todo ese conocimiento con muchos temas interesantes como hasta ahora.

[@victorsanz2720]

Agradezco mucho tu apoyo. Te invito a ver mis nuevos videos. (;

[@la_materia]

@@victorsanz2720 Estoy al tanto siguiendo tus vídeos. Gracias y sigue adelante.

[@junkyver]

Gracias por tu video, es muy conciso, limpio y practico

[@phsicodelia]

Genial tu video Victor, me encanto la manera en que solucionaste un problema real con matematicas, programacion y grafos.

[@isaachernandezjimenez7043]

Me gustó el contenido de tu video, me suscribo y te felicito por tu entusiasmo! Yo recién empiezo en este mundo pero espero pronto poder ser capaz de hacer pequeñas implementaciones.

[@armandoalamilla]

Vine buscando plata y encontré oro. Tu canal es increible.

[@victorsanz2720]

Gracias por tus palabras. Comentarios así me motivan a seguir subiendo mejor contenido cada vez. Qué temas te gustaría que abordara en un próximo video ?

[@armandoalamilla]

@@victorsanz2720 Me gustaría que hicieras videos sobre algoritmos de cifrado avanzados como SHA o RSA donde nosotros podamos usar python para desarrollarlos. Gracias.

[@ericameck310]

¡Excelente!

[@elkiparionarojas9206]

Gracias por la info... bueno veo que la libreria de networkx facilita bastante el proceso... porque a decir verdad una implementacion pura y dura de graphos es relativamente complejo

[@user-oj4lo6nd3r]

Desde hace 20 años que veo estudiantes haciendo lo mismo con C, C++ y ahora Phyton. Es teoría de grafos.

[@josemata8865]

Actualmente estudió TI en la universidad y un problema que r hallado es que los profesores de matemáticas te enseñan los conceptos pero no donde aplicarlos, sino que te enseñan solo para pasar un examen y en parte no es culpa de ellos. Simplemente no son afines a la parte de programación y eso no está mal, pero ver los conceptos de matemáticas aplicados a problemas resueltos y resolverlos con código, te motiva a aprender matemáticas ya que sabes en qué casos puedes usarlas. Gran video y sigue así❤️ PD: estaría genial que hicieras uno con árboles binarios y n-arios

[@victorsanz2720]

Gracias por tu comentario. Me pasó algo similar, yo estudié matemáticas como licenciatura. Y justo en mis videos trato de conectar la parte teórica con la implementación en Python para resolver problemas que me parecen interesantes. Pd. Sobre árboles binarios tengo pensado hacer un video con una aplicación bastante interesante muy pronto. 🤓

[@josemata8865]

@@victorsanz2720 La espero con ansias 😊

[@MrWikimat]

Muy bien.Muy buen aporte!!

[@metatema]

Genial, gracias Victor.

[@victorsanz2720]

Te gustaría ver más temas de aplicaciones de grafos?

[@metatema]

@@victorsanz2720 Por favor. Si es posible cosas de Hypergrafos, estaría genial. Saludos

[@victorsanz2720]

Sí, justo pensaba retomar eso ya que como lo mostré en el video nos permite modelar situaciones donde las relaciones no necesariamente se dan de dos en dos. Además, que muchos problemas de gráficas que sabemos como resolverlos de manera lineal como el de la conexidad por vértices; en el caso de hipergráficas es un problema de tipo NP.

[@metatema]

Estaría padre que tocaras el tema que está en graphneural.network sobre la librería spektral de Python o sobre la Teoría espectral de grafos. Saludos!

[@victormanuelrodriguezluna2042]

Exelente amigo

[@DankSeven78877]

Saludos a mi profe Magdiel

[@MrDankid]

Hola Victor, muchas gracias por el video, es muy claro y bien explicado, lo quiero aplicar a realizar rutas entre calles a ver que me sale. Saludos desde Colombia

[@benjaguzman4957]

Buena hno

[@Leqiiz1996]

PUEDES AYUDARME A COMO MOSTRAR LA TABLA DE ADYASENCIA O LA LISTA DE ADYASENCIA ASI EN GRAFICO? OSEA NO POR CONSOLA

[@mectoystv]

Buena explicacion, una consulta el algoritmo de dijkstra se 'puede aplicar a crear una ruta optima dentro de un almacen lleno de pasadizos? para preparar la mercaderia en menor tiempo

[@victorsanz2720]

Habría que revisar el modelo, porque hay algoritmos específicos para transporte e inventarios. Sin embargo, el algoritmo de Dijkstra es súper eficiente y simple.☝️

[@mectoystv]

Osea hay otro algoritmo que superan a dijkstra en exactitud?

[@victorsanz2720]

Dijkstra en general produce un árbol generador de peso mínimo en gráficas no dirigidas con pesos positivos. Hay muchos otros algoritmos que hacen lo mismo, arrojando cada uno de ellos un resultado distinto. El tema, es saber cómo es tu modelo y ver qué algoritmo es el que mejor le acomoda.

[@matiasbarrientos7401]

@@mectoystv También está el de Bellman-Ford, que admite negative weights y también visualiza negatives cycles

[@TheSoyunusuariomas]

Excelente vídeo, tal vez podría ser útil añadirle peso a los transbordes ya que cada transborde es diferente

[@victorsanz2720]

Sí, de hecho un modelo más realista tomaría en cuenta el tiempo promedio de recorrido entre dos estaciones y el tiempo del transborde, aunque aquí variaría bastante ya que tenemos unos que son cortos, Oceanía, y otros que son larguísimos como la Raza.

[@axellbernabel5403]

Cuando quieres recuperas los nodos pones G.nodes(), cuando quieres recuperas las aristas pones G.edges(), cuando quieres recuperas lo pesos que pones?

[@alejandrosantoyo8293]

Que buen ejemplo práctico. ¿Qué tan difícil sería agregar pesos para considerar no solo distancia si no también cantidad de gente en distintos horarios?

[@victorsanz2720]

Solo sería hacer el estudio y los cálculos para agregarlos como atributos a las aristas. Esta vez solo consideré la distancia en metros porque es la información que ofrece oficialmente el metro.

[@krlschavita4398]

Hola amigo, gracias por compartir tu conocimiento tengo una pregunta cómo podría utilizar nexworkx en un proyecto de generar rutas de coordenadas es decir tengo 1000 puntos de coordenadas que debo visitar en x cantidad de tiempo y saber cuál es el punto más cercano al otro, y después formar la info que se le entrega a neteorkx, espero me puedas ayudar bro

[@dilafrina2871]

Can you draw any edge with different colors in the same model,i am stuck in such type of problem

[@franzsantana7562]

Hola Victor, muchas gracias por el video, me gustó tu forma de explicar y aprendí bastante, pero tengo una duda tangencial al tema del video ¿Hay alguna función de networkx que entregue todas las rutas posibles entre dos nodos? Me ayudarías mucho si me aclaras eso, Saludos!

[@victorsanz2720]

Claro, la solución al problema que propones consume muchos recursos computacionales (por lo que puede tardar muchísimo en calcularse). Sin embargo, existe la siguiente función: networkx.org/documentation/networkx-1.9/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html

[@brendavidal2340]

Hola Victor, gracias por compartir tus conocimientos. Quisiera saber de qué pagina obtuviste los datos del metro, ya vi tu archivo csv en el repositorio pero me gustaría saber de dónde salió. Gracias, eres un crack!

[@victorsanz2720]

Hola Brenda, gracias por tu comentario. Los saqué de esta página: www.metro.cdmx.gob.mx/operacion/cifras-de-operacion

[@brendavidal2340]

@@victorsanz2720 gracias!!!!!

[@sergiomartinez5424]

en la página del metro de méxico no encuentro la tabla que tú usas para sacar el csv de ella, me puedes pasar el enlace de esa tabla o decir donde buscarla? y si quisiese usar el metro de madrid , por ejemplo, de donde podría sacar una tabla parecida? Gracias !

[@fernandodiazdeleon1542]

Hola es justo lo que estaba buscando y esta increible el canal. Solo me queda una duda, que pasa cuando tienes restricciones como tu punto inicial y vertice debe ser el mismo, debes visitar al menos 10 estaciones, etc? Hay forma de agregar o contemplar esas restricciones?

[@victorsanz2720]

Hola, gracias por ver mi video. Respecto a tu pregunta, te refieres a encontrar una ruta que vaya de ida y vuelta?

[@fernandodiazdeleon1542]

@@victorsanz2720 Asi es, digamos un centro de distribución, donde tenemos N clientes, pero solo podemos elegir 100 y entregar X cantidad de producto, minimizando la distancia recorrida

[@victorsanz2720]

@@fernandodiazdeleon1542 quizás esto pueda resolver tu duda: kzbin.info/www/bejne/g3_IdZ2qbdJ2eas Considera que los pesos de las aristas pueden ser distancias, tiempos, vistos, etc...

[@fernandodiazdeleon1542]

@@victorsanz2720 gracias, una cosa más al módulo de networkx hay forma de ponerle restricciones???

[@victorsanz2720]

Si te refieres a flujos en redes, sí tienen algunos algoritmos que pueden manejar eso.

[@darlystefannyquinonezmendo9023]

no me muestra la grafica en gelphi sabes porque??

[@bettowo]

Hola buenas amigo, tengo una duda, yo lo hice en el idle de python pero no me imprime ni la primera gráfica, que se hace en estos caso?

[@laurasofiagonzalez923]

Si a mi tampoco, debe ser donde quedo guardado el archivo, pero no se que en que carpeta de quedar guardada

[@Zero-es-natural]

Se podría mejorar si pusieras distintos vértices si la estación está en una linea o la otra y agregas una arista con el peso del tiempo de traslado. =P

[@victorsanz2720]

Es un modelo simple, sería bueno considerar el tiempo de traslado y el tiempo que toma cada transbordo. Porque en el caso de la Raza o de San Lázaro son transbordos largos. De hecho encontré un trabajo de un chavo de ESCOM que trabajó el mismo problema. Aunque creo que lo hizo en Java.😢

[@matiasbarrientos7401]

@@victorsanz2720 Justo estaba pensando en lo del tiempo de traslado! Podrías compartir el link de ese trabajo? Muy bueno el vídeo, sigue así!

[@sneik09saul]

Como puedo aplicar el mismo principio si en clase me dieron dos puntos en un mapa y debo saber cual es la ruta mas corta

[@victorsanz2720]

Saul Henandez se me ocurren dos formas de resolverlo, la primera discretizando el problema. Y la segunda, al vivir en una esfera la distancia más corta entre dos puntos no es una recta sino una curva. Busca sobre la fórmula del semiverseno y se puede implementar en Python fácilmente.

[@hackingdanons]

Me está costando mucho implementar la parte gráfica en Java script 😪

[@victorsanz2720]

Hola, qué estás usando para implementarlo? Alguna biblioteca en especial ? Yo tengo en mi GitHub una implementación gráfica paso a paso usando Tkinter y networkx.

[@MusimilianKazaiko]

Genial Bro . Te dejo mi megalike y suscrip con campanita activada. Ojalá puedas darte una vuelta por mi canal : música y matemáticas. Un abrazo y excelente año!

[@victorsanz2720]

Gracias, y claro le doy un vistazo.

[@patriciohot6986]

que interesante? hay alguna forma de adaptarlo a un entorno web para generar una ruta de entregas?

[@victorsanz2720]

Una de las grandes ventajas de Python es que nos permite hacer desarrollo web, así que sí es posible adaptarlo a un entorno web importando el módulo de networkx.

[@b.al.1689]

una pregunta, como importo los datos de origen, veo que es una tabla, en que programa puedo hacer la tabla ? aun no entiendo esa parte

[@victorsanz2720]

En qué estás trabajando? Estás usando una libreta de Jupyter?

[@b.al.1689]

Recién estoy aprendiendo y ya la instalé, desde la misma libreta los importo?

[@victorsanz2720]

Tiene que guardarlo en el mismo Binder y ya de ahí lo corres tal cual está en el video. En otro caso, pon la dirección del archivo en la función read_csv

[@daniels1460]

Bro, en qué ide lo hiciste tú? Y en cuáles funciona el código? :3

[@victorsanz2720]

Hey, en este caso ocupé Jupyter. Sin embargo, me late más usar VS Code para proyectos más grandes, también dale un vistazo a Atom.

[@alandavid533]

@@victorsanz2720 Muchas gracias!! una duda bro, dónde se puede descargar completo el proyecto? es q en github pusiste que el xlsx se alteró :c me interesa correrlo todo en VS code y así poder ver y aprender un poco más, mi profe no enseña nada :( descargando todo lo de github se podría o sino puedo dejarte mi correo ojalá que se pueda, me ayudarías muchisimo

[@greivox24]

Hola, como hago para comunicarme contigo para ver si me puedes ayudar con una duda?

[@victorsanz2720]

Si gusta escríbeme por aquí tu duda. Y ya si es muy larga, podemos checarlo por otro medio.

[@greivox24]

@@victorsanz2720 Hola, si es un poco larga, me podrías ayudar? :C de verdad necesito ayuda :c

[@c_ca9384]

Hola excelente video! me podrías explicar como descargaste los datos de la pagina por favor para que me quede una tabla como la tuya gracias :)

[@victorsanz2720]

Me parece que subí la tabla con los datos en el repositorio, está en formato csv. Si no l’os encuentras avísame y te los mando, son datos que descargue de la página oficial del STC Metro.

[@c_ca9384]

@@victorsanz2720 lo que estoy haciendo es copiarlos en una hoja de excel voy en en la mitad ya jajajaja debería funcionar igual? en caso de no, te pediré los datos!!

[@victorsanz2720]

Baja el archivo metro.csv del repositorio, con ese trabajé.

[@c_ca9384]

@@victorsanz2720 No pude correr el algoritmo al final me marco -- NetworkXError: Invalid edge_attr argument: Longitud de interestación -- todo eso en la 3 celda

[@victorsanz2720]

Si sigues teniendo dudas, estoy pensando hacer un pdf para seguirlo paso a paso. Desde el preprocesamiento de l’os datos hasta su implementación.

[@axellbernabel5403]

vine por el algoritmo de dijkstra y solo encontre el uso de una funcion .-.

[@jafetpuyen7062]

Calla Rosca :v

[@victorsanz2720]

En este video quise hacer algo nuevo: Proponer un modelo, desarrollado en Python y realizar una implementación rápida a un problema que me pareció interesante. Ya que videos que expliquen el algoritmo de Dijkstra hay cientos en la plataforma, por otro lado, la implementación varía dependiendo de como representes tu gráfica. Te dejo este enlace dónde explican bastante bien el algoritmo a profundidad. Espero te sirva. (: kzbin.info/www/bejne/fZLddGZ3abSEiqc

[@axellbernabel5403]

@@jafetpuyen7062 xd

[@CipriValdezate]

Seguro que tu video es genial, pero he tenido que dejarlo. No sé a qué viene ese horrible ruido de fondo que has puesto y que hay gente que se atreve a llamar "música".

[@victorsanz2720]

Gracias, agradezco tu feedback. Justo por eso la quité en los videos más recientes (;