{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Algoritmos de búsqueda en grafos\n",
"\n",
"Hemos definido el problema de búsqueda de caminos en un laberinto como encontrar un camino entre dos nodos cualesquiera del grafo, en caso de existir ese camino.\n",
"\n",
"Este no es un problema nuevo para la computación, de hecho el algoritmo que le da solución y que lleva el nombre de su inventor, fue descubierto en 1956."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Dijkstra\n",
"\n",
"El algoritmo de dijkstra es un algoritmo que determijna camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo con pesos.\n",
"\n",
"La idea es partir del nodo de origen y explorar recusivamente los caminos mínimos al resto de nodos, guardando y actualizando la información de forma continua en memoria.\n",
"\n",
"```bash\n",
"ALGORITMO Dijkstra(Grafo G, Nodo origen)\n",
" INICIALIZAR distancia[nodos de G] a infinito\n",
" INICIALIZAR visto[nodos de G] a falso\n",
" DISTANCIA[origen] = 0\n",
"\n",
" MIENTRAS existan nodos no vistos HACER\n",
" nodo_actual = nodo no visto con menor valor en DISTANCIA\n",
" visto[nodo_actual] = verdadero\n",
"\n",
" PARA CADA vecino DE nodo_actual HACER\n",
" SI visto[vecino] es falso ENTONCES\n",
" distancia_tentativa = DISTANCIA[nodo_actual] + peso(nodo_actual, vecino)\n",
" SI distancia_tentativa < DISTANCIA[vecino] ENTONCES\n",
" DISTANCIA[vecino] = distancia_tentativa\n",
" FIN SI\n",
" FIN SI\n",
" FIN PARA\n",
" FIN MIENTRAS\n",
"FIN ALGORITMO\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from heapq import heappush, heappop # colas de prioridad\n",
"import networkx as nx\n",
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"from maze import Maze\n",
"m = Maze(10) ## RANDOM SEED NOT SET ON MAZE GENERATION ### "
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"\n",
"def dijkstra(grafo, start):\n",
" distancias = {}\n",
" caminos = {}\n",
" padres = {}\n",
" vistos = set()\n",
" queue = []\n",
" for n in grafo.nodes:\n",
" distancias[n] = float('inf')\n",
" padres[n] = None\n",
" caminos[n] = []\n",
" distancias[start] = 0\n",
" caminos[start] = [start]\n",
" heappush(queue, (distancias[start], start))\n",
"\n",
" while queue:\n",
" dist_actual, nodo_actual = heappop(queue)\n",
" vistos.add(nodo_actual)\n",
" if dist_actual > distancias[nodo_actual]:\n",
" continue\n",
"\n",
" for ady in list(grafo.neighbors(nodo_actual)):\n",
" if ady not in vistos:\n",
" nueva_dist = distancias[nodo_actual] + grafo[nodo_actual][ady].get('weight', 1)\n",
" if nueva_dist < distancias[ady]:\n",
" distancias[ady] = nueva_dist\n",
" padres[ady] = nodo_actual\n",
" caminos[ady] = caminos[nodo_actual] + [ady]\n",
" heappush(queue, (distancias[ady], ady))\n",
" return distancias, caminos"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(0, 0),\n",
" (0, 1),\n",
" (0, 2),\n",
" (1, 2),\n",
" (2, 2),\n",
" (3, 2),\n",
" (3, 3),\n",
" (3, 4),\n",
" (3, 5),\n",
" (4, 5),\n",
" (4, 6),\n",
" (5, 6),\n",
" (6, 6),\n",
" (7, 6),\n",
" (7, 7),\n",
" (7, 8),\n",
" (8, 8),\n",
" (9, 8),\n",
" (9, 9)]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# DIJKSTRA\n",
"distancias, caminos = dijkstra(m.grid,m.start)\n",
"caminos[m.end]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Visualización de resultados - Animación con pyvis"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"from pyvis.network import Network\n",
"\n",
"def dijkstra_animado_con_pyvis(G):\n",
" start, end = G.start, G.end\n",
" visitados = set()\n",
" distancias = {nodo: float('inf') for nodo in G.grid.nodes()}\n",
" distancias[start] = 0\n",
" cola = [(0, start)]\n",
"\n",
" while cola:\n",
" _, nodo_actual = heappop(cola)\n",
" if nodo_actual in visitados:\n",
" continue\n",
" visitados.add(nodo_actual)\n",
"\n",
" visualizar_grafo_con_pyvis(G.grid, visitados, start, end, f\"resources/frames/dijkstra_{len(visitados)}.html\")\n",
"\n",
" if nodo_actual == end:\n",
" break\n",
"\n",
" for vecino in G.grid.neighbors(nodo_actual):\n",
" nueva_dist = distancias[nodo_actual] + 1 # Asumiendo un peso de 1 para cada arista\n",
" if nueva_dist < distancias[vecino]:\n",
" distancias[vecino] = nueva_dist\n",
" heappush(cola, (nueva_dist, vecino))\n",
"\n",
"def visualizar_grafo_con_pyvis(G, visitados, start, end, filename):\n",
" nt = Network(notebook=True, width=\"100%\", height=\"700px\",cdn_resources=\"local\")\n",
" for node in G.nodes:\n",
" x, y = node\n",
" nt.add_node(str(node), title=str(node), x=x*100, y=-y*100, color=\"lightgray\" if node not in visitados else \"skyblue\", fixed=True)\n",
"\n",
" for edge in G.edges:\n",
" nt.add_edge(str(edge[0]), str(edge[1]))\n",
"\n",
" nt.get_node(str(start))[\"color\"] = \"green\"\n",
" nt.get_node(str(end))[\"color\"] = \"red\"\n",
" nt.toggle_physics(False)\n",
" nt.show(filename)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAZcAAAGVCAYAAAAyrrwGAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAurUlEQVR4nO3df3Ac9X3/8dfuHmvjfM+5HzUJR86HAccKIo1JcVrAtWmnNAQshybTaSc/BaSddMLQgkUCJXYJbaEtFkmYZiZpZrCblEKYNiS1GayBmeI0QGlHgU6aRo6gsXwd5Ue5H3CUiU63+/n+IaScsCXr9j7SvXb9esxkgqVb3dOfO/mtvdtdOcYYAxEREYvcXgeIiEjyaLiIiIh1Gi4iImKdhouIiFin4SIiItZpuIiIiHUaLiIiYp2Gi4iIWKfhIiIi1mm4iIiIdRouIiJinYaLiIhYp+EiIiLWabiIiIh1Gi4iImKdhouIiFin4SIiItZpuIiIiHUaLiIiYp2Gi4iIWKfhIiIi1mm4iIiIdRouIiJinYaLiIhYp+EiIiLWabiIiIh1Gi4iImKdhouIiFin4SIiItZpuIiIiHUaLiIiYp2Gi4iIWJfqdcBSHHvpGPY/tx/j1XE0phpIr0pjY24jBjcPYv0b1/c6T0REXscxxpheRyzk8NHDGH56GAd/cBCuM7OTFZgAnuMBAEITYsdbd2DokiFsK21bsS5jDIIgQBiGcF0XnufBcZwVu3/mHqYW9cQL09owtcQV5XAxxmD46WHc/NjNSDkptExrwdvOfn7v5Xtx08U3LesTIAgC1Go1VKtVNJvNuY/7vo9cLodsNgvP85bt/pl7mFrUEy9Ma8PUEneUw2X4qWEMPTbU8XZ7L9+LXZfsWoYioNFooFwuIwzDBW/jui6KxSLS6fSyNLD2MLWoJ16Y1oapJQnohsvho4dx2d9eFn37wcPWXyJrNBqYmJhY8u1LpdKyPvmYepha1BMvTGvD1JIUdEeLDT89jJQT7TiDlJPC8NPDVnuCIEC5XO5om3K5jCAIrHYw9jC1qCdemNaGqSVJqIbLsZeO4eAPDi76HstiWqaFA0cOoPxSZ0+UxdRqtUV3k08kDEPU63VrDaw9TC3qiRemtWFqSRKq4bL/uf1zR4VF5Tou9j23z0qPMQbVajXStpVKBbZfcWTqYWpRT7wwrQ1TS9JQnecyXh238nX+7fl/w3fS37HytXzfj7Rds9nEs88+a6WhHVMPUwuQrJ4gCJBKUX17WhMEwbwjsTrB9jxO8uPULapVaUw1EJjuXscMwgCPPP4IHvnYI133FAoFjIyMRN5+YGAAk5OTXXcw9jC1JLGn05dp4qTbvxvT8zjJj1O3qI4W+/DDH8YD332gqwHjOR6uOOsK3HHhHVaaov5UAyDyT2eLYephagGS1dPX15fYn4hbrRbGxsYib8/0PE7y49QtqlXZmNto5eu867x34Z3vfGfXX8cYg/Hx8UhPZt/30d/fb/WkTqYeppYk9iT5RD3P8+D7PsVjpcdp+VC9oT+4eRCh6W43MzQhrtl8jZUex3GQy+UibZvP561fLYCph6lFPfHCtDZMLUlDNVzWv3E9drx1R1fnuQxsGkDxjUVrTdlsFq7b2TK5rotMJmOtgbWHqUU98cK0NkwtSUI1XABg6JKhyOe5BCbArovtXv7F8zwUi50Nq2KxuGy7y0w9TC3qiRemtWFqSRK64bKttA17L98badu7L797Wa6OnE6nUSqVTvrTjeu6K3JZCKYephb1xAvT2jC1JAXV0WKzjDG45+l7MPTYEN1Vkev1OiqVynFXTM3n88hkMit+pV2WHqYW9cQL09owtcSeIXb46GGz84GdxrndMd5nPON9xjO4HXP/7dzumJ0P7DSHjx5e0a4wDM3o6KgpFApmdHTUhGG4ovfP3MPUwtozPT1tpqamzPT0dM97mDA9VkwtcUV1KPLrbSttw7bSNpRfKmPfc/vwfPV5vDz1MtauWovzcufhms3XWH3zfqlm945mT+Tq9REjTD1MLe33z9Sj8yJOjOmxYmqJq1g8y4tvLGLP9j29zhARkSWie0NfRETiT8NFRESs03ARERHrNFxERMQ6DRcREbFOw0VERKzTcBEREes0XERExDoNFxERsU7DRURErNNwERER6zRcRETEOg0XERGxTsNFRESs03ARERHrNFxERMQ6DRcREbEuFr+Jko0xBgBQKBTm/tzLX4PK1MPUwtjDxBiDIAgQhiFc14XneXqsCFtm75/psVoKx8yuopxUEASo1WqoVqtoNptzH/d9H7lcDtlsFp7nnZI9TC2MPUzY1oaph6mFsacTGi5L1Gg0UC6XEYbhgrdxXRfFYhHpdPqU6mFqYexhwrY2TD1MLYw9ndJwWYJGo4GJiYkl375UKi3rg83Uw9TC2MOEbW2YephaGHui0Bv6JxEEAcrlckfblMtlBEGQ+B6mFsYeJmxrw9TD1MLYE5WGy0nUarVFd0tPJAxD1Ov1xPcwtTD2MGFbG6YephbGnqg0XBZhjEG1Wo20baVSge1XHJl6mFoYe5iwrQ1TD1MLY0839J7LIlqtFsbGxiJv3350hy2+70fe1nYPUwvQXU9fXx9SqWQema/n8eKYWoDkPI85Kkh1umv6egMDA5icnLRUM3PM/cjICEUPU4uNnm4fa2Z6HsejxUYP0/NYey6L0E98i2NqAZLzE59teh4vjqkFSM7zmKOClOd58H0/0hPI93309/dbPYvWGIPx8XGKHqYWGz2sJ6LZoOdxPFps9DA9j/WG/iIcx0Eul4u0bT6ft355BqYephbGHiZsa8PUw9TC2NMNDZeTyGazcN3Olsl1XWQymcT3MLUw9jBhWxumHqYWxp6oNFxOwvM8FIvFjrYpFovLtnvK1MPUwtjDhG1tmHqYWhh7otIb+kvEdp0fph6mFsYeJmxrw9TD1MLY0ykNlw4EQYB6vY5KpXLcFUrz+TwymcyKXzGVpYephbGHCdvaMPUwtTD2dMRIx8IwNKOjo6ZQKJjR0VEThmHPe6anp83U1JSZnp7uaY/WJj4YHyuWHqYWxp6l0KHIEcwekTF78lSvj9BwHIfm2HatTXwwPlYARw9TS/v9s/Qshd7QFxER6zRcRETEOg0XERGxTsNFRESs03ARERHrNFxERMQ6DRcREbFOw0VERKzTcBEREes0XERExDoNFxERsU7DRURErNNwERER6zRcRETEOg0XERGxTsNFRESs03ARERHrNFxERMS62Pz+V2MMgiBAGIZwXRee5/XsV30aYwAAhUJh7s9x+LWjK0Frszg9j+PRw9TC2LMUjpmtJhUEAWq1GqrVKprN5tzHfd9HLpdDNpuF53mnXAsbrc3imNaHqYWth6mFsacT1MOl0WigXC4jDMMFb+O6LorFItLp9CnTwkZrszim9WFqYethamHs6RTtcGk0GpiYmFjy7Uul0rItMFMLG63N4pjWh6mFrYephbEnCso39IMgQLlc7mibcrmMIAgS3cJGa7M4pvVhamHrYWph7ImKcrjUarVFdwVPJAxD1Ov1RLew0dosjml9mFrYephaGHuiohsuxhhUq9VI21YqFdh8lY+phY3WZnFM68PUwtbD1MLY0w2691xarRbGxsYib99+RIUNvu9H3ravrw+pVGyO9u5It49TktcGSNbz2HYLwNXD1AIk598cjoo2ne4Ovt7AwAAmJyettBQKBYyMjETevtu/C7Nu/25JXhsgWc9jmy1sPUwtNnqYvq+053ISSfkpwjbtuSwuSc9jtp/OtTYLY/q+4qho43kefN+P9KD5vo/+/n5rZ64aYzA+Ph65hfXkJhu6fZySvDZAsp7HNlvYephabPQwfV/RvaHvOA5yuVykbfP5vNUHmqmFjdZmcUzrw9TC1sPUwtjTDbrhAgDZbBau21ma67rIZDKJbmGjtVkc0/owtbD1MLUw9kRFOVw8z0OxWOxom2KxuCy7hEwtbLQ2i2NaH6YWth6mFsaeqOje0G/HdG0dphY2WpvFMa0PUwtbD1MLY0+nqIcLMHMphHq9jkqlctxVQfP5PDKZzIpeMZWlhY3WZnFM68PUwtbD1MLY0xETE2EYmtHRUVMoFMzo6KgJw1AthLQ2i2NaH6YWth6mFsaepaB8z+VEZo+CmD1hqZdHRTC1sNHaLI5pfZha2u+foYeppf3+WXqWIjbDRURE4kPDRURErNNwERER6zRcRETEOg0XERGxTsNFRESs03ARERHrNFxERMQ6DRcREbFOw0VERKzTcBEREes0XERExDoNFxERsU7DRURErNNwERER6zRcRETEOg0XERGxLjbDxRgDACgUCvP+fKq3zN5/q9VCs9lEq9XS2rRhWpvZHoBjfZha2u+foYeppf3+WXqWwjHklUEQoFaroVqtotlszn3c933kcjlks1l4nnfKtbD1MLWoJz4tbD1MLYw9naAeLo1GA+VyGWEYLngb13VRLBaRTqdPmRa2HqYW9cSnha2HqYWxp1O0w6XRaGBiYmLJty+VSsu2wEwtbD1MLeqJTwtbD1MLY08UlO+5BEGAcrnc0TblchlBECS6ha2HqUU98Wlh62FqYeyJinK41Gq1RXcFTyQMQ9Tr9US3sPUwtagnPi1sPUwtjD1R0Q0XYwyq1WqkbSuVitWjKJha2HqYWtQTnxa2HqYWxp5u0L3n0mq1MDY2Fnn79iMqbPB9P/K2tlsArh6mFkA9i2FqAbh6mFqA7nr6+vqQSqUs1kTHUdGm093B1xsYGMDk5KSVlkKhgJGREYoWth6mFvXEp4Wth6nFRk+3/37apD2Xk0jSTzVam4UlvYepBeDqYWoBtOeybDzPg+/7kR403/fR398Px3GstBhjMD4+TtHC1sPUop74tLD1MLXY6GE6oZLuDX3HcZDL5SJtm8/nrT7QTC1sPUwt6olPC1sPUwtjTzfohgsAZLNZuG5naa7rIpPJJLqFrYepRT3xaWHrYWph7ImKcrh4nodisdjRNsVicVl2CZla2HqYWtQTnxa2HqYWxp6o6N7Qb8d0bR2mFrYephb1xKeFrYephbGnU9TDBZi5FEK9XkelUjnuqqD5fB6ZTGZFr5jK0sLWw9Sinvi0sPUwtTD2dMTERBiGZnp62kxNTZnp6WkThqFaCHvCMDSjo6OmUCiY0dFRirVh69Fjxd/D1MLYsxR0hyIvxHEcmuO3mVoArp7Zo1VmTyzr9dErjD16rE6MqYeppf3+WXqWgvINfRERiTcNFxERsU7DRURErNNwERER6zRcRETEOg0XERGxTsNFRESs03ARERHrNFxERMQ6DRcREbFOw0VERKzTcBEREes0XERExDoNFxERsU7DRURErNNwERER6zRcRETEOg0XERGxTsNFrDLGAAAKhcK8P/cKWw8TtrVh6mFqab9/lp6lcEwcKoVeEASo1WqoVqtoNptzH/d9H7lcDtlsFp7nnbI9TNjWhqmHqYWxpxMaLtK1RqOBcrmMMAwXvI3ruigWi0in06dcDxO2tWHqYWph7OmUhot0pdFoYGJiYsm3L5VKy/qNwNbDhG1tmHqYWhh7otB7LhJZEAQol8sdbVMulxEEwSnRw4RtbZh6mFoYe6LScJHIarXaorvsJxKGIer1+inRw4RtbZh6mFoYe6LScJFIjDGoVquRtq1UKtaPdmHrYcK2Nkw9TC2MPd3Qey4SSavVwtjYWOTt2498scX3/cjb9vX1IZVKWazhkbTHynYPUwuQnOcxR4XETqe77a83MDCAyclJSzUzx/+PjIxE3r7bvw+zpD1WNnuYWmz0MD2PtecikSTtp2Gmn/hsS9pjpT2XhTE9jzkqJHY8z4Pv+5G+uXzfR39/PxzHsdZjjMH4+HjkHtYT0WxI2mNls4epxUYP0/NYb+hLJI7jIJfLRdo2n89b/YZk7GHCtjZMPUwtjD3d0HCRyLLZLFy3s6eQ67rIZDKnRA8TtrVh6mFqYeyJSsNFIvM8D8VisaNtisXisu26s/UwYVsbph6mFsaeqPSGvnSN7RpIbD1M2NaGqYephbGnUxouYkUQBKjX66hUKsddvTWfzyOTyaz41WSZepiwrQ1TD1MLY08nNFzEKmMMnn32WQwMDODAgQO48MILe/omozEGQRAgDEO4rgvP86je9OwltrVheu4wtTD2LIUORRarZp/wsyeW9fobwHEcmuP+2bCtDdNzh6ml/f5ZepZCb+iLiIh1Gi4iImKdhouIiFin4SIiItZpuIiIiHUaLiIiYp2Gi4iIWKfhIiIi1mm4iIiIdRouIiJinYaLiIhYp+EiIiLWabiIiIh1Gi4iImKdhouIiFin4SIiItZpuIiIiHU8v4buJJh+JStTC1vP7G/NLhQKc3+Ow2/NWylMjxUbpucOUwtjz1I4ZraaVBAEqNVqqFaraDabcx/3fR+5XA7ZbBae551yLWw9TC2MtD4LY1obphbGnk5QD5dGo4FyuYwwDBe8jeu6KBaLSKfTp0wLWw9TCyOtz8KY1oaphbGnU7TDpdFoYGJiYsm3L5VKy7bATC1sPUwtjLQ+C2NaG6YWxp4oKN/QD4IA5XK5o23K5TKCIEh0C1sPUwsjrc/CmNaGqYWxJyrK4VKr1RbdFTyRMAxRr9cT3cLWw9TCSOuzMKa1YWph7ImKbrgYY1CtViNtW6lUYPNVPqYWth6mFkZan4UxrQ1TC2NPN+jec2m1WhgbG4u8ffsRFTb4vh95W9stAFdPNy19fX1IpWJzJHzHun0eJ3l99D2+uKR8X3FUtOl0d/D1BgYGMDk5aaWlUChgZGSEooWtp9uWbh9ndt3+/ZK8PvoeX74epueN9lxOIkk/1TCtDdNPWMtBey4L0/f44pLyfcVR0cbzPPi+H+lB830f/f391s5cNcZgfHycooWtp9sW1hO/bOn2eZzk9dH3+PL1MD1v6N7QdxwHuVwu0rb5fN7qA83UwtbD1MJI67MwprVhamHs6QbdcAGAbDYL1+0szXVdZDKZRLew9TC1MNL6LIxpbZhaGHuiohwunuehWCx2tE2xWFyWXUKmFrYephZGWp+FMa0NUwtjT1R0b+i3Y7q2DlMLWw9TCyOtz8KY1oaphbGnU9TDBZi5FEK9XkelUjnuqqD5fB6ZTGZFr5jK0sLWw9TCSOuzMKa1YWph7OmIiYkwDM3o6KgpFApmdHTUhGGoFsKeMAzN9PS0mZqaMtPT0z1fGzZMjxUbprVhex6z9SwF3aHIC5k9CmL2hKVeHhXB1NJ+/ww9juPQHGfPiOmxYsO0NmzPY7aepaB8Q19EROJNw0VERKzTcBEREes0XERExDoNFxERsU7DRURErNNwERER6zRcRETEOg0XERGxTsNFRESs03ARERHrNFxERMQ6DRcREbFOw0VERKzTcBEREes0XERExDoNFxERsU7DRURErIvNcDHGAAAKhcK8P5/qLe33z9LDxBiDVquFZrOJVqvV87XRY7UwrU2yOIb8EQyCALVaDdVqFc1mc+7jvu8jl8shm83C87xTroWxhwnb2rD1MNHaJBP1cGk0GiiXywjDcMHbuK6LYrGIdDp9yrQw9jBhWxu2HiZam+SiHS6NRgMTExNLvn2pVFq2Jx9TC2MPE7a1YethorVJNsr3XIIgQLlc7mibcrmMIAgS3cLYw4Rtbdh6mGhtko9yuNRqtUV3k08kDEPU6/VEtzD2MGFbG7YeJlqb5KMbLsYYVKvVSNtWKhWrR5gwtTD2MGFbG7YeJlqbU0Oq1wGvFwTBvCNGOtFsNvHss89a7fF9n6YF6K4nCAKkUnQPuRVszxtAj9VCun2skrw2SUL3CHW6q/x6AwMDmJyctNJSKBQwMjJC0WKjp9u1Zcb0vAH0WC2m279bktcmSeiGi+t290rdgQMHLJV0j6kF6H5tmSXpeQPosVrO7WVl0A0Xz/Pg+36k3Wbf99Hf3w/Hcay0GGMwPj5O0WKjJ8knojE9bwA9Vovp9rFK8tokCd2PAI7jIJfLRdo2n89b/QeCqYWxhwnb2rD1MNHanBrohgsAZLPZjnd9XddFJpNJdAtjDxO2tWHrYaK1ST7K4eJ5HorFYkfbFIvFZdldZmph7GHCtjZsPUy0NslHe/kXgOu6Q0wtjD1M2NaGrYeJ1ia5qIcLMHNMfL1eR6VSOe6Kqfl8HplMZkWviszSwtjDhG1t2HqYaG2SifJlsXae5yGfz2Pjxo1oNpt497vfjWaziY0bNyKfz6/ok46phbGHCdvasPUw0dokE/1wmTV7hMjsiW69PGKEqaX9/ll6mLCtDVsPE61NssRmuIiISHxouIiIiHUaLiIiYp2Gi4iIWKfhIiIi1mm4iIiIdRouIiJinYaLiIhYp+EiIiLWabiIiIh1Gi4iImKdhouIiFin4SIiItZpuIiIiHUaLiIiYp2Gi4iIWKfhIiIi1qV6HbBUxhgAQKFQmPtzr35THVMLW48xBkEQIAxDuK4Lz/O0NqQ9eqwWb2FbG6aepXDM7CNKKggC1Go1VKtVNJvNuY/7vo9cLodsNrtiv2ObqYWth6lFPfFpYethamHs6QT1cGk0GiiXywjDcMHbuK6LYrGIdDp9yrSw9TC1qCc+LWw9TC2MPZ2iHS6NRgMTExNLvn2pVFq2BWZqYethalFPfFrYephaGHuioHxDPwgClMvljrYpl8sIgiDRLWw9TC3qiU8LWw9TC2NPVJTDpVarLboreCJhGKJerye6ha2HqUU98Wlh62FqYeyJim64GGNQrVYjbVupVGDzVT6mFrYephb1xKeFrYephbGnG3TvubRaLYyNjUXevv2ICht834+8re0WgKuHqQVQz2KYWgCuHqYWoLuevr4+pFIcZ5hwVLTpdHfw9QYGBjA5OWmlpVAoYGRkhKKFrYepRT3xaWHrYWqx0dPtv582ac/lJJL0U43WZmFJ72FqAbh6mFoA7bksG8/z4Pt+pAfN93309/dbO3PVGIPx8XGKFrYephb1xKeFrYepxUYP0wmVdG/oO46DXC4Xadt8Pm/1gWZqYethalFPfFrYephaGHu6QTdcACCbzcJ1O0tzXReZTCbRLWw9TC3qiU8LWw9TC2NPVJTDxfM8FIvFjrYpFovLskvI1MLWw9Sinvi0sPUwtTD2REX3hn47pmvrMLWw9TC1qCc+LWw9TC2MPZ2iHi7AzKUQ6vU6KpXKcVcFzefzyGQyK3rFVJYWth6mFvXEp4Wth6mFsacjJibCMDSjo6OmUCiY0dFRE4ahWgh7mFrUE58Wtp4wDM309LSZmpoy09PTWpsI6A5FXsjsURCzJyz18qgIppb2+2foYWppv3/1cLe03z9Dj+M4NOeLAFxrs1SUb+iLiEi8abiIiIh1Gi4iImKdhouIiFin4SIiItZpuIiIiHUaLiIiYp2Gi4iIWKfhIiIi1mm4iIiIdRouIiJinYaLiIhYp+EiIiLWabiIiIh1Gi4iImKdhouIiFin4SIiItZpuIiIiHWxGS7GGABAoVCY9+dTvaX9/hl6mFra71893C3t98/SwySOa+MY8sogCFCr1VCtVtFsNuc+7vs+crkcstksPM875VrYepha1BOfFsYeJnFeG+rh0mg0UC6XEYbhgrdxXRfFYhHpdPqUaWHrYWpRT3xaGHuYxH1taIdLo9HAxMTEkm9fKpWWbYGZWth6mFrUE58Wxh4mSVgbyvdcgiBAuVzuaJtyuYwgCBLdwtbD1KKe+LQw9jBJytpQDpdarbboruCJhGGIer2e6Ba2HqYW9cSnhbGHSVLWhm64GGNQrVYjbVupVKweRcHUwtbD1KKe+LQw9jBJ0trQvefSarUwNjYWefv2Iyps8H0/8ra2WwCuHqYWQD2LYWoBuuvp6+tDKpWyWMOj23//mNaGo6JNp7uDrzcwMIDJyUkrLYVCASMjIxQtbD1MLeqJT4uNnm7/jWDW7d+NaW2053ISSfqJT2uzsKT3MLUA2nNZiPZclpHnefB9P9IT2vd99Pf3w3EcKy3GGIyPj1O0sPUwtagnPi02elhPGrSh23//mNaG7g19x3GQy+UibZvP561+EzC1sPUwtagnPi2MPUyStDZ0wwUAstksXLezNNd1kclkEt3C1sPUop74tDD2MEnK2lAOF8/zUCwWO9qmWCwuyy4hUwtbD1OLeuLTwtjDJClrQ/eGfjuma+swtbD1MLWoJz4tjD1M4r421MMFmLkUQr1eR6VSOe6qoPl8HplMZkWvJsvSwtbD1KKe+LQw9jCJ9dqYmAjD0IyOjppCoWBGR0dNGIY9bZmenjZTU1Nmenq6py1sPUyPk3ri08LYwySOa0N3KPJCZo+CmD2Zq5dHRTiOQ3MsOcDVw/Q4td+/erhb2u+fpYdJHNeG8g19ERGJNw0XERGxTsNFRESs03ARERHrrL4LHAQBpqenbX7JeYwxKJVKMMbgZz/72bLdT1L4vt/xmb4iIjZYGS7GGPz4xz9e9t+Elkql8MUvfhGpVAo//OEPl/W+ksB1XWzYsKGrK9CKiERhZbjMDpYzzjgDa9asWbbD5F599VVMT0+jWCxizZo1y3IfSRGGISYnJ/GjH/0I69evj8WhiyKSHF0Pl9kzSM844wzk83kbTYveFwCsWrUKq1evXtb7SoJ169ZhcnISrVYLp512Wq9zROQU0vUL8rPvsWhPgs/sy2GzQ1lEZKVYe0O/m5ddjr10DPuf24/x6jgaUw2kV6WxMbcRg5sHsf6N620lnnL0UpiI9EpPrxly+OhhDD89jIM/OAjXmdmJCkwAz5m5ENvtT9yOHW/dgaFLhrCttK2XqSIi0oGeHKdqjMHep/bisr+9DI+OPwoDg8AECMzMyzez/21g8Oj4o9i+fzuGnxqG4b6Ac2S33347Nm/e3OsMERFrerLncs/T9+Dmx24GALRMa9Hbzn5+6LEhNJtNXP7/LrfWMTg4iHq9jm984xvWvqaIiPRgz+Xw0cMYemwo0rZ/fPiP8Z3KdywXJcNynrwqItKpFR8uw08PI+VE22HyHA/3//B+y0Uzzj77bHzuc5+b97HNmzfj9ttvn/vz2NgYtm7ditWrV+P888/H448/Dsdx5u35fOpTn8Jb3/pWrFmzBueccw5279593D/8f/EXf4E3velNSKfTuO6664672kAYhrjjjjvwlre8BatWrcLmzZtx6NChuc8fPXoUjuPga1/7GrZv347Vq1fj/vuXZ11ERKJY0ZfFjr10DAd/cBAG0d47CUyAf/nJv+B/Xv4fbHrDJst1J7nvIMDVV1+N9evX45lnnkGj0cCuXbuOu106ncb+/ftRKBTw3e9+F7/3e7+HdDqNT37ykwCAhx56CLfffju+8IUvYOvWrfjqV7+Ke++9F+ecc87c1/j85z+P4eFhfOlLX8KFF16I++67Dzt37sT3vvc9bNy4ce52t9xyC4aHh3HhhRfqvB8RobKiey77n9s/d1RYVA4cfPU/v2qpaOkee+wxvPDCC/jKV76Cd7zjHdi6dSv+/M///LjbffrTn8Yll1yCs88+GwMDAxgaGsJDDz009/nPfe5zuO6663Dddddh06ZN+LM/+zOcf/75877G3r178alPfQq/+7u/i02bNuEv//IvsXnz5uP2rP7oj/4I73vf+7BhwwaceeaZy/L3FhGJYkX3XMar411/DQcO/rv+3xZqOnPkyBEUi0W8+c1vnvvYu971ruNu97WvfQ333nsvXnjhBbzyyitotVpYu3bt3Oe///3v4+Mf//i8bS6++GL88z//MwDg5ZdfxuTkJC699NJ5t7n00kvxH//xH/M+dtFFF3X99xIRcseOAfv3o/TMM3gYQGn3buCXfxkYHATW854HuKJ7Lo2pxtzhxlEFCNBoNqwfluy67nFfs9M3yZ9++ml88IMfxJVXXomDBw/i2WefxW233YZms2kzdc4b3vCGZfm63Zhdw0KhMO/PvaKeeLS03z9LT88dPgzs3AmcfTbMHXcgd+gQdgLIHToEc8cdwNlnz3z+W9/qdekJrehwSa9Kz50gGZXneFi7ai2mpqYwPT1t7Qm4bt06/OhHP5r788svvzzvysubNm1CuVzGT37yk7mP/fu///u8r/HUU0+hVCrhtttuw0UXXYSNGzdiYmJi3m3e9ra34Zlnnpn3sX/913+d+++1a9eiUCjgySefnHebJ5988riXz5gEQYAXX3wR4+Pj8H0fIyMj8H0f4+PjePHFF1f8EjTqiUcLY0/PGQPs3QtcdhnMo48CxsAJAjhhCBeAE4ZwggAwZubz27cDw8Mz2xFZ0ZfFNuY2nvxGS3BO5hwYY9BqtdBqteD7Pjyvu6H167/+69i/fz8GBgaQyWSwZ8+eeV/z8ssvx7nnnouPfvSj+Ku/+is0Gg18+tOfBvDzy6xs3LgRx44dw4MPPogtW7bgkUcewcMPPzzvfv7wD/8Qg4ODuOiii3DppZfi/vvvx/e+9715b+jffPPN+JM/+ROce+652Lx5M/bt24fnnnuO9oiwRqOBcrmMMAyP+1yz2cSPf/xj/PSnP0WxWEQ6nVZPD3uYWhh7KNxzD3DzzHmATmvx8wDnPj/02ukdJzjIqFdWdM9lcPMgQnP8k6gToQnxkbd/ZN7Hms1mpJ9uwjBEKjUzX2+99VZs374dO3bswFVXXYWrr74a55577txtPc/DN77xDbzyyivYsmULPvaxj+G2224DgLkjtXbu3Ikbb7wR119/PTZv3oynnnoKu3fvnnefv/M7v4Pdu3fjk5/8JH7pl34JExMT+IM/+IN5t7nhhhtw0003YdeuXXj729+OQ4cO4Z/+6Z/mHSnGotFoYGJi4oT/OLQLwxATExNoNBrq6VEPUwtjD4XDh38+KDo1NET1Epljunxd6Wc/+xl++MMfYsOGDUs6HHbnAzvx6PijJz0z/0Q8x8N7zn0PHnrfQyf8/OrVqzu6WOMVV1yB8847D3/913/dcQsw81LV1q1b8fzzz88bRCw6fWw6FQQBjhw5ctJ/HNq5rotNmzZ1vaepnvi2MPbQ2LkT5tFHT7rHciImlYJz5ZXAN7+5DGGdW/GTKIcuGYo0WICZvZYbttyw4OeXuvdSq9Vw8OBBPPHEE/iN3/iNJd//ww8/jMceewxHjx7F448/jt///d/HpZdeSjlYVkKtVuvoHwdg5qfQ5fqNpeqJRwtjD4Vjx4CDByMNFuC1l8gOHADKZcth0az4cNlW2oa9l++NtO2dl92JrcWtC36+1Wot6Q3+a6+9Fh//+Mexa9cuvPe9713y/TcaDXziE59AX18fBgcHsWXLFnyT5KeElWaMQbVajbRtpVKxfiSQeuLRwthDY/9+GLe7f5KN6wL79lkK6s6KvywGzDy57nn6Hgw9NoSUk1p0T8ZzPAQmwF2X3YUbttxw0pe9On1pLMmW82WxVquFsbGxyNsvx+HZs78cLYqk9zC1AN319PX1zb1Xmigf/jDMAw/MHAkWkfE8OB/4APCVr1gMi6Ynj5DjONh1yS5sOWsLhp8exoEjB074+1xCE+I9574HN2y5YdE9lnbGGA2XFdDpSxqvNzAwgMnJSUs1M+dGjIyMqIe8xUZPt889Wo0G0O1h10EAvPyynZ4u9XT8byttw7bSNpRfKmPfc/vwfPV5vDz1Mt6QegPOyZyDj7z9I3jL2rd09DU1WFaG2+Xu+4EDByyV2KGehTG1AN0/92il04DndTdgPA9ouyJIL1HsWxbfWMSe7XsAzOx5TE1NRXpdVYNl5XieB9/3I71k4vs++vv7rT5exhiMj4+rh7zFRk9ijxazdarBeefZ+TpdovsRwHGcyE+eVCqlAbNCHMdBLpeLtG0+n7f+OKknHi2MPTQGB+F0+ZKfE4bANddYCuoOx3A5dgy44w7gwx8Grr4aqWuvRerOO+F0eEhdYn+iIZXNZjt+icJ1XWQyGfWscA9TC2MPhfXrgR07YCIerGBSKWBgACgWLYdF09vh0nZhNtxxB/DAA8A3vwnngQeQuusurOrrg//bvw33298+6ZfyfT+5P9GQ8jwPxQ6fyMVicdl+CFBPPFoYe2gMDUU/zyUITt3Lv8xpuzAbXrswG4Lg529kBcHMhdqMgXvoEFb95m8i9fnPL3hhtkS/DksunU6jVCqd9KdQ13VRKpWW/fpQ6olHC2MPhW3bZv5tjOLuu2e2J9Gb4dJ2YTac7MJsrw2c0269Fal77/35xx0Hp512GlavXh15sAwODsJxnON+vwoAfOITn4DjOBgcHFzS13riiSfgOE6yzyBeQDqdxqZNm3DmmWced/6C7/s488wzsWnTphX7x0E98Whh7KFw001zA+ZkL5HNfX7v3pntiKz80WJdXJjttFtvhfcrvwJn+3YAdo4OKxaLePDBB/HZz34Wp59+OoCZkw///u//HuuJfxEPG8/zkM/nkcvlEAQBwjCE67rwPK8nL1eqJx4tjD095zgzL29t2QJneBg4cODnZ+4Hwczhxnjt0vtXXjlzW6I9llkrv+cyPAxEPbs2lYL72c/CcRxrT7p3vvOdKBaL+PrXvz73sa9//etYv349LrzwwrmPhWGIu+66Cxs2bMDpp5+Od7zjHfiHf/gHAMDRo0fxa7/2awBm3qhs3+M5dOgQtm7dikwmg3w+jx07duCFF16w0s7IcRykUin4vk9x9J564tHC2NNz27bNXIRyYgLOnj1wPvABOO9978z/79kDTEzMfJ5wsAArvefy2oXZIv9Sm/YLs1k8IuLaa6/Fvn378MEPfhAAcN999+Gaa67BE088MXebu+66C3/3d3+HL37xi9i4cSO+9a1v4UMf+hDWrVuHrVu34h//8R/x/ve/H0eOHMHatWvn9oL+7//+DzfddBN+8Rd/Ea+88gr27NmD3/qt38Jzzz2X3JPBRMSeYhHYs6fXFR1b2eGyfz/gut2dgTp7YTaLi/2hD30It95669xvjXzyySfx4IMPzg2Xqakp3HnnnXj88cdx8cUXAwDOOeccfPvb38aXvvQlbN++fe64/TPOOGPe4ZLvf//7593Xfffdh3Xr1uG//uu/cMEFF1j7O4iIMFnZ4TI+bufrPP+8na/zmnXr1uGqq67C/v37YYzBVVddhV/4hV9ou7vn8eqrr+Lyyy+ft12z2Zz30tmJjI+PY8+ePXjmmWfw4osvzl0X6dixYxouIpJYKztciC/Mdu211+L6668HAHzhC1+Y97lXXnkFAPDII4/grLPOmve5VatWLfp1BwYGUCqV8OUvfxmFQgFhGOKCCy5YlivNioiwWNnhQnxhtiuuuALNZhOO4+Dd7373vM+df/75WLVqFY4dO4btrx2p9nqzh1G2/8KySqWCI0eO4Mtf/jJ+9Vd/FQDw7SWcECoiEncrO1yIL8zmeR6+//3vz/13u3Q6jaGhIdx4440IwxBbt27FSy+9hCeffBJr167FRz/6UZRKJTiOg4MHD+LKK6/E6aefjmw2i3w+j7/5m7/BmWeeiWPHjuGWW26x3i4iwmZlD1caHAS6/V0My3hhtrVr12LtAntFf/qnf4rdu3fjrrvuwtve9jZcccUVeOSRR7BhwwYAwFlnnYXPfOYzuOWWW/CmN70J119/PVzXxYMPPojR0VFccMEFuPHGG3H33XcvS7uICJOV/02UO3fOXPIlyvVzUingyitnju2Wk1rO30QpIrKYlT/RYmgo2mABZt6rIbowm4iInNjKD5cEXZhNREROrDeniLddmO2kl4IhvjCbiIicWG+Gy+yF2Q4fnnkPxXFmDjGePUpr9r8dZ+bzhw/P3P5Uv9aQiEhMWDsUOdJxAdu2zfyvXJ65pMvzz8+cILl27czhxtdcQ/Nb1eKoy2M1REQi63q4nHbaaQCAV199de5ijR2L6YXZ2M1eBUC/SE1EVlrXw8XzPGQyGfz0pz8FAKxZs0aXyiYQhiH+93//F2vWrEEq6q84EBGJyMq/Om9+85sBYG7ACAfXdbF+/XoNexFZcV2fRNkuCAJMT0/b+nLSJd/39TtjRKQnrA4XERERoFeHIouISKJpuIiIiHUaLiIiYp2Gi4iIWKfhIiIi1mm4iIiIdRouIiJinYaLiIhYp+EiIiLWabiIiIh1Gi4iImKdhouIiFin4SIiItZpuIiIiHX/H/+G6smdFBO4AAAAAElFTkSuQmCC",
"text/plain": [
"<Figure size 500x500 with 1 Axes>"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_1.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_2.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_3.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_4.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_5.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_6.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_7.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_8.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_9.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_10.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_11.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_12.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_13.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_14.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_15.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_16.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_17.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_18.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_19.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_20.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_21.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_22.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_23.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_24.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_25.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_26.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_27.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_28.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_29.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_30.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_31.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_32.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_33.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_34.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_35.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_36.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_37.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_38.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_39.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_40.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_41.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_42.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_43.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_44.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_45.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_46.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_47.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_48.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_49.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_50.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_51.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_52.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_53.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_54.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_55.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_56.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_57.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_58.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_59.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_60.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_61.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_62.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_63.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_64.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_65.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_66.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_67.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_68.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_69.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_70.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_71.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_72.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_73.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_74.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_75.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_76.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_77.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_78.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_79.html\n",
"Warning: When cdn_resources is 'local' jupyter notebook has issues displaying graphics on chrome/safari. Use cdn_resources='in_line' or cdn_resources='remote' if you have issues viewing graphics in a notebook.\n",
"resources/frames/dijkstra_80.html\n"
]
}
],
"source": [
"# Ejecutar la animación de Dijkstra\n",
"m = Maze(10) ## RANDOM SEED NOT SET ON MAZE GENERATION ### \n",
"m.display()\n",
"dijkstra_animado_con_pyvis(m)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"¿Cómo visualizar la animación? Después de ejecutar el comando anterior, se habran creado archivos html dentro de frames. Ahora tenemos ejecutar html_to_images.js para renderizar el javascript, realizar una captura de pantalla de cada html, y convertirlo todo después a vídeo.\n",
"\n",
"1. Ir a la carpeta resources\n",
"```bash\n",
"cd resources/\n",
"```\n",
"\n",
"2. Convertir los html a imagenes\n",
"```bash\n",
"node html_to_images.js\n",
"```\n",
"\n",
"3. Convertir las imagenes a un vídeo secuencial, donde cada frame dura 1s \n",
"```bash\n",
"ffmpeg -framerate 1 -pattern_type glob -i 'temp_images/capture_dijkstra_*.png' -c:v libx264 -r 30 -pix_fmt yuv420p out.mp4\n",
"``````"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<video src=\"resources/out.mp4\" controls >\n",
" Your browser does not support the <code>video</code> element.\n",
" </video>"
],
"text/plain": [
"<IPython.core.display.Video object>"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from IPython.display import Video\n",
"\n",
"## RANDOM SEED NOT SET ON MAZE GENERATION ### \n",
"Video(\"resources/out.mp4\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# A*"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Función heurística para el algoritmo A*\n",
"def manhattan(s,e):\n",
" dmin = min(abs(s[0]-e[0]), abs(s[1]-e[1])) \n",
" dmax = max(abs(s[0]-e[0]), abs(s[1]-e[1])) \n",
" return dmin + (dmax-dmin)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.8"
}
},
"nbformat": 4,
"nbformat_minor": 2
}