A_star.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 227,
   "metadata": {},
   "outputs": [],
   "source": [
    "from graphviz import Graph, Source\n",
    "class grapth:\n",
    "    def __init__(self):\n",
    "        self.nodes = set([])\n",
    "        self.edges = {\n",
    "            \n",
    "        }\n",
    "        self.edge_cost = {\n",
    "            \n",
    "        }\n",
    "        \n",
    "    def add_node(self, node):\n",
    "        self.nodes.update(node)\n",
    "    \n",
    "    def add_edge(self, source, target, cost):\n",
    "        if(source not in self.edges.keys()):\n",
    "            self.edges[source] = []\n",
    "        elif(target not in self.edges.keys()):\n",
    "            self.edges[target] = []\n",
    "        self.edges[source].append(target)\n",
    "        self.edge_cost[\"{}->{}\".format(source, target)] = cost\n",
    "        \n",
    "    def clear_edge(self):\n",
    "        self.edges = {\n",
    "            \n",
    "        }\n",
    "        self.edge_cost = {\n",
    "            \n",
    "        }\n",
    "        \n",
    "    def draw_grapth(self, path=set([])):\n",
    "        dot = Graph()\n",
    "        for node in self.nodes:\n",
    "            if(node in path):\n",
    "                dot.node(node, color=\"red\")\n",
    "            else:\n",
    "                dot.node(node)\n",
    "            \n",
    "        for source, target in self.edges.items():\n",
    "            for node in target:\n",
    "                dot.edge(source, node, weight=str(self.edge_cost[\"{}->{}\".format(source, node)]), label=str(self.edge_cost[\"{}->{}\".format(source, node)]))\n",
    "        return dot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "metadata": {},
   "outputs": [],
   "source": [
    "working_grapth = grapth()\n",
    "working_grapth.add_node(\"a\")\n",
    "working_grapth.add_node(\"b\")\n",
    "working_grapth.add_node(\"c\")\n",
    "working_grapth.add_node(\"d\")\n",
    "working_grapth.add_node(\"e\")\n",
    "working_grapth.add_node(\"f\")\n",
    "working_grapth.add_node(\"g\")\n",
    "working_grapth.add_node(\"h\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 247,
   "metadata": {},
   "outputs": [],
   "source": [
    "working_grapth.clear_edge()\n",
    "working_grapth.add_edge(\"a\", \"b\", 2)\n",
    "working_grapth.add_edge(\"b\", \"c\", 3)\n",
    "working_grapth.add_edge(\"c\", \"d\", 2)\n",
    "\n",
    "\n",
    "working_grapth.add_edge(\"f\", \"h\", 1)\n",
    "working_grapth.add_edge(\"h\", \"f\", 1)\n",
    "working_grapth.add_edge(\"a\", \"h\", 6)\n",
    "\n",
    "\n",
    "working_grapth.add_edge(\"a\", \"e\", 1)\n",
    "working_grapth.add_edge(\"e\", \"f\", 10)\n",
    "working_grapth.add_edge(\"f\", \"g\", 2)\n",
    "working_grapth.add_edge(\"g\", \"d\", 1.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 248,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"216pt\" height=\"392pt\"\n",
       " viewBox=\"0.00 0.00 216.00 392.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 388)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-388 212,-388 212,4 -4,4\"/>\n",
       "<!-- b -->\n",
       "<g id=\"node1\" class=\"node\"><title>b</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- c -->\n",
       "<g id=\"node3\" class=\"node\"><title>c</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">c</text>\n",
       "</g>\n",
       "<!-- b&#45;&#45;c -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>b&#45;&#45;c</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-260.799C27,-246.052 27,-224.915 27,-210.175\"/>\n",
       "<text text-anchor=\"middle\" x=\"32\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- f -->\n",
       "<g id=\"node2\" class=\"node\"><title>f</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"148\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">f</text>\n",
       "</g>\n",
       "<!-- h -->\n",
       "<g id=\"node4\" class=\"node\"><title>h</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"82\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"82\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">h</text>\n",
       "</g>\n",
       "<!-- f&#45;&#45;h -->\n",
       "<g id=\"edge4\" class=\"edge\"><title>f&#45;&#45;h</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M133.278,-176.522C127.347,-170.406 120.599,-163.071 115,-156 106.478,-145.236 97.9705,-132.279 91.7285,-122.252\"/>\n",
       "<text text-anchor=\"middle\" x=\"120\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- g -->\n",
       "<g id=\"node7\" class=\"node\"><title>g</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"181\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"181\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">g</text>\n",
       "</g>\n",
       "<!-- f&#45;&#45;g -->\n",
       "<g id=\"edge5\" class=\"edge\"><title>f&#45;&#45;g</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M154.52,-174.207C160.305,-159.305 168.713,-137.649 174.494,-122.758\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- d -->\n",
       "<g id=\"node6\" class=\"node\"><title>d</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">d</text>\n",
       "</g>\n",
       "<!-- c&#45;&#45;d -->\n",
       "<g id=\"edge6\" class=\"edge\"><title>c&#45;&#45;d</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-173.879C27,-140.91 27,-68.9659 27,-36.0516\"/>\n",
       "<text text-anchor=\"middle\" x=\"32\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- h&#45;&#45;f -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>h&#45;&#45;f</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M100.883,-117.908C109.406,-124.005 119.088,-132.032 126,-141 133.642,-150.915 139.253,-163.899 142.895,-174.15\"/>\n",
       "<text text-anchor=\"middle\" x=\"139\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- e -->\n",
       "<g id=\"node5\" class=\"node\"><title>e</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"148\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">e</text>\n",
       "</g>\n",
       "<!-- e&#45;&#45;f -->\n",
       "<g id=\"edge3\" class=\"edge\"><title>e&#45;&#45;f</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148,-260.799C148,-246.052 148,-224.915 148,-210.175\"/>\n",
       "<text text-anchor=\"middle\" x=\"157.5\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- g&#45;&#45;d -->\n",
       "<g id=\"edge7\" class=\"edge\"><title>g&#45;&#45;d</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M160.867,-92.8877C131.353,-76.5975 76.6545,-46.4067 47.1378,-30.115\"/>\n",
       "<text text-anchor=\"middle\" x=\"124.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">1.5</text>\n",
       "</g>\n",
       "<!-- a -->\n",
       "<g id=\"node8\" class=\"node\"><title>a</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"82\" cy=\"-366\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"82\" y=\"-362.3\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- a&#45;&#45;b -->\n",
       "<g id=\"edge8\" class=\"edge\"><title>a&#45;&#45;b</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.0924,-349.423C66.9325,-343.397 62.1866,-336.418 58,-330 50.6338,-318.708 42.622,-305.768 36.5889,-295.881\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- a&#45;&#45;h -->\n",
       "<g id=\"edge9\" class=\"edge\"><title>a&#45;&#45;h</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M82,-347.604C82,-300.421 82,-170.414 82,-123.32\"/>\n",
       "<text text-anchor=\"middle\" x=\"87\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- a&#45;&#45;e -->\n",
       "<g id=\"edge10\" class=\"edge\"><title>a&#45;&#45;e</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M93.7995,-349.804C105.739,-334.428 124.098,-310.783 136.08,-295.351\"/>\n",
       "<text text-anchor=\"middle\" x=\"123\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7f146cc45c50>"
      ]
     },
     "execution_count": 248,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Source(working_grapth.draw_grapth())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 255,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"216pt\" height=\"392pt\"\n",
       " viewBox=\"0.00 0.00 216.00 392.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 388)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-388 212,-388 212,4 -4,4\"/>\n",
       "<!-- b -->\n",
       "<g id=\"node1\" class=\"node\"><title>b</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- c -->\n",
       "<g id=\"node3\" class=\"node\"><title>c</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">c</text>\n",
       "</g>\n",
       "<!-- b&#45;&#45;c -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>b&#45;&#45;c</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-260.799C27,-246.052 27,-224.915 27,-210.175\"/>\n",
       "<text text-anchor=\"middle\" x=\"32\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- f -->\n",
       "<g id=\"node2\" class=\"node\"><title>f</title>\n",
       "<ellipse fill=\"none\" stroke=\"red\" cx=\"148\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">f</text>\n",
       "</g>\n",
       "<!-- h -->\n",
       "<g id=\"node4\" class=\"node\"><title>h</title>\n",
       "<ellipse fill=\"none\" stroke=\"red\" cx=\"82\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"82\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">h</text>\n",
       "</g>\n",
       "<!-- f&#45;&#45;h -->\n",
       "<g id=\"edge4\" class=\"edge\"><title>f&#45;&#45;h</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M133.278,-176.522C127.347,-170.406 120.599,-163.071 115,-156 106.478,-145.236 97.9705,-132.279 91.7285,-122.252\"/>\n",
       "<text text-anchor=\"middle\" x=\"120\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- g -->\n",
       "<g id=\"node7\" class=\"node\"><title>g</title>\n",
       "<ellipse fill=\"none\" stroke=\"red\" cx=\"181\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"181\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">g</text>\n",
       "</g>\n",
       "<!-- f&#45;&#45;g -->\n",
       "<g id=\"edge5\" class=\"edge\"><title>f&#45;&#45;g</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M154.52,-174.207C160.305,-159.305 168.713,-137.649 174.494,-122.758\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- d -->\n",
       "<g id=\"node6\" class=\"node\"><title>d</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">d</text>\n",
       "</g>\n",
       "<!-- c&#45;&#45;d -->\n",
       "<g id=\"edge6\" class=\"edge\"><title>c&#45;&#45;d</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-173.879C27,-140.91 27,-68.9659 27,-36.0516\"/>\n",
       "<text text-anchor=\"middle\" x=\"32\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- h&#45;&#45;f -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>h&#45;&#45;f</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M100.883,-117.908C109.406,-124.005 119.088,-132.032 126,-141 133.642,-150.915 139.253,-163.899 142.895,-174.15\"/>\n",
       "<text text-anchor=\"middle\" x=\"139\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- e -->\n",
       "<g id=\"node5\" class=\"node\"><title>e</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"148\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">e</text>\n",
       "</g>\n",
       "<!-- e&#45;&#45;f -->\n",
       "<g id=\"edge3\" class=\"edge\"><title>e&#45;&#45;f</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148,-260.799C148,-246.052 148,-224.915 148,-210.175\"/>\n",
       "<text text-anchor=\"middle\" x=\"157.5\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- g&#45;&#45;d -->\n",
       "<g id=\"edge7\" class=\"edge\"><title>g&#45;&#45;d</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M160.867,-92.8877C131.353,-76.5975 76.6545,-46.4067 47.1378,-30.115\"/>\n",
       "<text text-anchor=\"middle\" x=\"124.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">1.5</text>\n",
       "</g>\n",
       "<!-- a -->\n",
       "<g id=\"node8\" class=\"node\"><title>a</title>\n",
       "<ellipse fill=\"none\" stroke=\"red\" cx=\"82\" cy=\"-366\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"82\" y=\"-362.3\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- a&#45;&#45;b -->\n",
       "<g id=\"edge8\" class=\"edge\"><title>a&#45;&#45;b</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.0924,-349.423C66.9325,-343.397 62.1866,-336.418 58,-330 50.6338,-318.708 42.622,-305.768 36.5889,-295.881\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- a&#45;&#45;h -->\n",
       "<g id=\"edge9\" class=\"edge\"><title>a&#45;&#45;h</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M82,-347.604C82,-300.421 82,-170.414 82,-123.32\"/>\n",
       "<text text-anchor=\"middle\" x=\"87\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- a&#45;&#45;e -->\n",
       "<g id=\"edge10\" class=\"edge\"><title>a&#45;&#45;e</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M93.7995,-349.804C105.739,-334.428 124.098,-310.783 136.08,-295.351\"/>\n",
       "<text text-anchor=\"middle\" x=\"123\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7f146cbe6048>"
      ]
     },
     "execution_count": 255,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import queue\n",
    "\n",
    "def a_star(grapth, start, goal):\n",
    "    visited_nodes = set()\n",
    "    node_queue = queue.PriorityQueue()\n",
    "    node_score = {\n",
    "        \n",
    "    }\n",
    "\n",
    "    node_queue.put((0, start))\n",
    "\n",
    "    path = {}\n",
    "    node_score[start] = 0\n",
    "    \n",
    "    \n",
    "    while not node_queue.empty():\n",
    "        current = node_queue.get()[1]\n",
    "        \n",
    "        visited_nodes.add(current)\n",
    "        \n",
    "        if(current == goal):\n",
    "            visited_nodes = set([current])\n",
    "            while current in path.keys():\n",
    "                current = path[current]\n",
    "                visited_nodes.update(current)\n",
    "            return visited_nodes\n",
    "        \n",
    "        edges = grapth.edges[current]\n",
    "        for edge_node in edges:\n",
    "            if(edge_node in visited_nodes):     \n",
    "                continue\n",
    "\n",
    "            cost = node_score[current] + grapth.edge_cost[\"{}->{}\".format(current, edge_node)]\n",
    "            if(edge_node not in node_score.keys() or cost <= node_score[edge_node]):\n",
    "                node_score[edge_node] = cost\n",
    "                node_queue.put((cost, edge_node))\n",
    "                path[edge_node] = current                \n",
    "    raise Exception(\"Path not found\")\n",
    "\n",
    "z = a_star(working_grapth, \"a\", \"g\")\n",
    "Source(working_grapth.draw_grapth(z))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}