Biblioteca teachmedijkstra en Python

El algoritmo de Dijkstra es muy similar al algoritmo de Prim para árboles de expansión mínimos. Al igual que el MST de Prim, generamos un SPT (árbol de ruta más corta) con una fuente determinada como raíz. Mantenemos dos conjuntos, un conjunto contiene vértices incluidos en el árbol de ruta más corta, otro conjunto incluye vértices que aún no están incluidos en el árbol de ruta más corta. En cada paso del algoritmo, encontramos un vértice que está en el otro conjunto (conjunto de aún no incluido) y tiene una distancia mínima de la fuente.

teachmedijkstra: la biblioteca de utilidades que ayuda en la representación explicó el algoritmo de Dijkstra en formato látex para fines didácticos. Las filas de la array representan el vértice del gráfico y la columna representa cada paso de tiempo de unidad de explicación, obtiene el árbol de ruta más corto construido para el algoritmo de distancia más corta.

Instalación

Este módulo no viene integrado con Python. Para instalarlo, escriba el siguiente comando en la terminal.

pip install teachmedijkstra

Después de la instalación de la biblioteca, los pasos a seguir son:

• Inicializar el gráfico no dirigido/dirigido
• Adición de vértices y aristas al gráfico
• Usando Dijaskstra(), para ingresar el gráfico creado con un punto de partida.
• run(), ejecuta el algoritmo.
• Al final, el archivo latex producido se puede guardar con el nombre requerido.
   

Función utilizada:

• teachmedijkstra.UndirectedGraph() : Inicializa el gráfico con Graph no dirigido.
• graph.addVertex(nombre, coordenada) : Agrega el nombre del vértice junto con la coordenada gráfica a la que debe pertenecer.
• graph.addEdge(strt, end, weight) : Agrega borde de 1 Node a otro con peso particular.
• teachmedijkstra.Dijkstra(graph_obj, strt_point) : Inicializa la variable con instancia de gráfico con punto de inicio.
• dijkstra.run() : Ejecuta el algoritmo dijkstra.
• dijkstra.saveToLaTeXFile (nombre_de_archivo) : Guarda el gráfico construido en nombre_de_archivo en formato látex.

Ejemplo 1:

import teachmedijkstra
  
# getting graph
graph = teachmedijkstra.UndirectedGraph()
  
# initializing vertices
graph.addVertex("i", (0, 1))
graph.addVertex("j", (2, 1))
graph.addVertex("k", (2, 2))
graph.addVertex("l", (0, 2))
  
# initializing edges
graph.addEdge("i", "j", 7)
graph.addEdge("i", "l", 8)
graph.addEdge("j", "k", 6)
graph.addEdge("l", "j", 1)
graph.addEdge("k", "i", 5)
  
  
# creating graph from i.
dijkstra = teachmedijkstra.Dijkstra(graph, "i")
dijkstra.run()
  
# saving file
dijkstra.saveToLaTeXFile("undirectedDij.tex")

Archivo de látex producido:

Salida (Después de convertir Latex):

Ejemplo 2: gráfico dirigido 

En este ejemplo, crearemos un gráfico dirigido con este módulo.

import teachmedijkstra
  
# initializing Directed graph
graph = teachmedijkstra.DirectedGraph()
  
# initializing vertices
graph.addVertex("a", (0, 2))
graph.addVertex("b", (1, 2))
graph.addVertex("c", (2, 2))
graph.addVertex("d", (0, 1))
graph.addVertex("e", (1, 1))
graph.addVertex("f", (2, 1))
graph.addVertex("g", (0, 0))
graph.addVertex("h", (1, 0))
graph.addVertex("i", (2, 0))
  
# adding edges
graph.addEdge("a", "b", 9)
graph.addEdge("b", "c", 3)
graph.addEdge("c", "f", 4)
graph.addEdge("e", "f", 3)
graph.addEdge("e", "d", 6)
graph.addEdge("d", "g", 1)
graph.addEdge("g", "h", 3)
graph.addEdge("h", "i", 8)
graph.addEdge("a", "d", 1)
graph.addEdge("e", "b", 3)
graph.addEdge("e", "h", 9)
graph.addEdge("f", "i", 6)
graph.addEdge("a", "e", 4)
graph.addEdge("c", "e", 5)
graph.addEdge("g", "e", 1)
graph.addEdge("i", "e", 4)
graph.addEdge("c", "i", 6)
graph.addEdge("a", "g", 1)
  
  
# calling Dijkstra fnc to perform algo.
dijkstra = teachmedijkstra.Dijkstra(graph, "a")
dijkstra.run()
  
  
# saving file
dijkstra.saveToLaTeXFile("directedDij.tex")

Salida de látex: 

Producción :