Fundamentos y Práctica con Grafos: Algoritmo de Floyd-Warshall

En este taller de Grafos: Exploración y Aplicación, se aprenderá los fundamentos de los grafos y cómo aplicarlos en la computación a través de videos instructivos y la práctica con el software Grafos v.1.3.5, será familiarizado con conceptos básicos y se podrá aplicar en ejercicios prácticos. El taller se desarrolla en tres pasos: explicación en clase, visualización de un video introductorio sobre el algoritmo de Floyd-Warshall, y ejercicio práctico utilizando el software Grafos v.1.3.5 para crear un grafo siguiendo las instrucciones del video "¿Cómo usar el programa Grafos?".

ALGORITMO DE GRAFO

Algoritmo de floyd-Warshall: Este algoritmo consiste e encontrar la distancia más corta que hay de un vértice a otro de un grafo, el grafo puede ser dirigido o no dirigido.

En este ejemplo vemos un grafo dirigido, lo primero que debemos hacer es realizar la matriz de distancia y la matriz de recorridos. En la matriz de distancia elegiremos la primera fila y columna para ir haciendo la sumatoria y reemplazar resultados si son menores a los que ya están, seguido de esto se cambiará el dato en la matriz de recorridos por la letra de la primera fila y primera columna, en caso de que no sea menor no se cambiará ningún dato. Al finalizar la matriz de distancia nos representa la distancia mínima que existe de un vértice a cualquier otro y la matriz de recorridos, es el recorrido que tomará esa distancia.

¿Cómo usar el programa grafos? 

Lo primero es descargar el programa por internet, es totalmente gratis y es la versión 1,3.5. Para realizar un proyecto nos dirigimos a archivos y abrir un nuevo proyecto, allí saldrá una hoja en blanco, donde podemos crear cada nodo dándole doble clic dependiendo del problema que vayan a resolver. 

También vamos a Añadir lo que son las flechas entre cada nodo para eso vamos a seleccionar el nodo origen con un clic, se va a poner amarillo y vamos a seleccionar el nodo destino con un clic derecho, este automáticamente se va a colorar rojo y vamos a seleccionar Añadir arco, vamos a hacer esto con cada uno de los de los nodos:

Hacer clic derecho y Añadir arco. Hay que recordar que el nodo origen siempre se pondrá de color amarillo y el nodo destino de color rojo, ya que los tenemos todos conectados vamos a proceder a añadirle valores a cada uno de ellos, vamos a irnos a edición, vamos a seleccionar tabla, vamos a irnos a la opción de costos para Añadir el costo, se puede cambiar el nombre de los nodos dependiendo de cómo se nos haga más fácil o dependiendo del problema y vamos a poner los valores. Otra de las opciones que tiene el programa es que nos muestra la Gráfica de distintas formas dependiendo cómo se nos haga más fácil visualizarla, podemos verlo de forma aleatoria, manera de árbol, manera circular, en forma de flujo, forma de tablero. 

Todo esto dependiendo de cómo están estructurados nuestros nodos y dependiendo del problema.

EXPLICACIÓN DE LOS CONCEPTOS APRENDIDOS

Algoritmo de Floyd-Warshall: Este algoritmo nos permite encontrar la distancia mas corta que hay de un vértice a otro de un grafo dado, este grafo puede ser dirigido o no dirigido.

Matriz de distancias: Representa la distancia mínima que existe de un vértice a cualquier otro. Si no existe un camino directo entre los vértices, se agrega una distancia infinita para representarlo.

Matriz de recorrido: Indica la ruta a seguir desde el vértice (i) hasta el vértice (j) para que el recorrido sea eficiente. Cada elemento (i, j) en la matriz muestra el vértice directo anterior con la distancia más corta.

Software Grafos v.1.3.5: El software permite crear grafos agregando nodos, aristas dirigidas o no dirigidas, valores, etiqueta, formato, etc.

PASOS SEGUIDOS PARA EL EJERCICIO PRÁCTICO

PASO 1. Descargar el Software Grafos v.1.3.5.

PASO 2. Crear un archivo nuevo.

PASO 3. Agregar vértices haciendo doble clic al botón derecho del mouse.

PASO 4. Hacer clic derecho a un vértice que es donde iniciara la arista, posteriormente haga clic izquierdo a otro vértice y presione en añadir arco.

PASO 5. Presionar en “Edición” el cual aparecerán dos opciones, seleccione “tabla”.

PASO 6. Agregar costes a las aristas haciendo clic en “Coste (Arcos)” posteriormente aparecerá una tabla para agregar los datos de coste.

PASO 7. Regresar a la gráfica nuevamente, luego pase el cursor por encima de un grafo el cual dice “Análisis de camino”, posteriormente de clic a “Todos los caminos mínimos – Alg. FloydWarshall”.

Fig. 3 Grafo hecho con “Software Grafos v.1.3.5” (Autoría propia, 2024)