week-7-class.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 7 - Class\n",
    "\n",
    "This notebook starts with some useful code for visualising graphs and running Dijkstra's algorithm. The questions are in the section [Questions](#Questions) below.\n",
    "\n",
    "## Useful code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import networkx as nx\n",
    "import random\n",
    "from collections import defaultdict\n",
    "import math\n",
    "import matplotlib.pyplot as plt\n",
    "infinity = float('inf')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def visualise(G, W, layout=nx.spring_layout):\n",
    "    G_out = nx.DiGraph()\n",
    "    for u in G.keys():\n",
    "        G_out.add_node(str(u))\n",
    "        for v in G[u]:\n",
    "            G_out.add_edge(str(u), str(v), weight=str(W[u, v]))\n",
    "    pos = layout(G_out)\n",
    "    nx.draw_networkx(G_out, pos=pos)\n",
    "    nx.draw_networkx_edge_labels(G_out, pos=pos, edge_labels=W)\n",
    "\n",
    "def graph_from_edges(edges):\n",
    "    # assume edges = list of triples (u, v, w)\n",
    "    nodes = sorted(list(set([u for u, v, w in edges]+[v for u, v, w in edges])))\n",
    "    G = defaultdict(list)\n",
    "    W = {}\n",
    "    for u, v, w in edges:\n",
    "        G[u].append(v)\n",
    "        W[u, v] = w\n",
    "    return G, W"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dijkstra(G, W, start):\n",
    "    predecessor = {start: None}   # predecessor subgraph (start has no predecessor)\n",
    "    q = {start: 0}                # priority queue for next vertices, distance to start is 0\n",
    "    shortest = {}                 # shortest paths found (none at the start)\n",
    "    # Repeatedly evaluate this cell until it says Finished!\n",
    "    while q: # are there any vertices to add?\n",
    "        # Find the lowest priority (note: this is where the data structure is inefficient!)\n",
    "        d, vertex = min((d, vertex) for vertex, d in q.items())\n",
    "        del q[vertex]\n",
    "        # Add this to the set of vertices we've finished processing\n",
    "        shortest[vertex] = d\n",
    "        # Now update the list of candidate vertices by iterating through its neighbours\n",
    "        for next_vertex in G[vertex]:\n",
    "            if next_vertex in shortest: # don't add ones we've already finished with\n",
    "                continue\n",
    "            c = q.get(next_vertex, infinity) # get the current best found if there is one, or infinity if not\n",
    "            e = d+W[vertex, next_vertex] # distance to next_vertex if you take this route\n",
    "            if e<c: # if it's better, replace it in the queue and predecessor subgraph\n",
    "                q[next_vertex] = e\n",
    "                predecessor[next_vertex] = vertex\n",
    "    return shortest, predecessor\n",
    "\n",
    "def shortest_path_subgraph(G, W, target, predecessor):\n",
    "    SG = {}\n",
    "    SW = {}\n",
    "    while predecessor[target] is not None:\n",
    "        source = predecessor[target]\n",
    "        SG[source] = [target]\n",
    "        SW[source, target] = W[source, target]\n",
    "        target = source\n",
    "    return SG, SW"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Questions\n",
    "\n",
    "### Give an example to show that Dijkstra's algorithm fails on graphs if you allow negative weights. Why does it fail?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is the shortest (weighted) path from A to D in the graph below?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgMAAAGFCAYAAABg2vAPAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/av/WaAAAACXBIWXMAAA9hAAAPYQGoP6dpAABPlUlEQVR4nO3de0DN9/8H8OfndFK6KEUMtRAhEWZzmUuuc9uwi9lsmEuEkOuw+TJsrilddM/9rmGMRO6XuYTKpVAy90vrXpzL7w9fftt3Ijn1Ppfn45/vV+ecz3k2Ou9nn9fnIqnVajWIiIjIYMlEByAiIiKxWAaIiIgMHMsAERGRgWMZICIiMnAsA0RERAaOZYCIiMjAsQwQEREZOHlxnqRSqXD79m1YWlpCkqTSzkREREQaoFarkZ2djWrVqkEmK/r3/2KVgdu3b8Pe3l5j4YiIiKjs3Lx5EzVq1Cjy8WKVAUtLyxcbq1ChgmaSERERUanKysqCvb39i3W8KMUqA89HAxUqVGAZICIi0jGvG/HzAEIiIiIDxzJARERk4FgGiIiIDBzLABERkYFjGSAiIjJwLANEREQGjmWAiIjIwLEMEBERGTiWASIiIgPHMkBERGTgWAaIiIgMHMsAERGRgWMZICIiMnAsA0RERAaOZYCIiMjAsQwQEREZOLnoAEQkTm6hAmmPcvFEoUI5uQyOtuYwN+HHApGh4U89kYFJuZeNNSfTEXflPtIf50H9t8ckAA42ZnB3tsPXHzigThVLUTGJqAxJarVa/bonZWVlwcrKCpmZmahQoUJZ5CIiDbv5OA/TohNw+OpDGMkkKFVF/+g/f7yNUyXM6+MKexuzMkxKRJpS3PWbxwwQGYD1p9LRyecgjl1/BACvLAJ/f/zY9Ufo5HMQ60+ll3pGIhKHYwIiPecfl4JFMckleq1SpYZSpcbUrQl4mFOI0e51NJyOiLQB9wwQ6bH1p9JLXAT+16KYZGzgHgIivcQyQKSnbj7Ow8ztSRrd5o/bk3DzcZ5Gt0lE4nFMQKSnpkUnQPGSYwNyLsTi0a6l//8FI2PITM1hbGuP8jWbwKJRFxiZW790mwqVGtOiE7BqyAelE5qIhGAZINJDKfeycfjqw1c+x7b7OBjb1oBapYAyNxOFf15E5oktyDoZjUq9p6C8o9u/XqNUqXH46kNcvZ8NJzuedkikLzgmINJDa06mw0gmvfI5xpXfhUn1ejC1bwjzeq1h02kYqn23DFI5UzzYOhfK3IyXvs5IJmH1CR47QKRPWAaI9FDclfuvPX3wZeRWdqjYYQjUT/KRHb/7pc9RqtSIS77/thGJSIuwDBDpmZxCBdLf4iC/8rXeAyQZCm8mFvmc9Ed5yC1UlPg9iEi7sAwQ6Zkbj3Lx5vsE/p+snClkZhWgzHlc5HPUANIe5b7FuxCRNmEZINIzTxSqt99IMdqERt6HiLQCywCRniknf7sfa9WTAqjys2BkYVOq70NE2oM/zUR6xtHWHK8+j+DV8q+dAtQqmDi4Fvkc6b/vQ0T6gWWASM+Ym8jhUMK7DCoy7yMjLgKSiTksm3Qr8nkOtmYwN+FlSoj0BX+aifSQu7MdVp288crTC58+uAGolFCrlFDlZaLgZhJyEmIhSTLY9Z0OIzOrl77OSCbBva5daUUnIgFYBoj00NcfOCDqeNorn/PiksRGcshMLGBsWwNWLT6FReOuRRYB4Nl1Bga0cNBcWCISjmWASA/VqWKJNk6VcOz6o3/tHbBo1AkWjTqVaLtGMgmtatnyUsREeobHDBDpqXl9XCF/zSWJ35RcJmFen6IPLCQi3cQyQKSn7G3MMOtjF41uc/bHLrAv4cGJRKS9WAaI9NiXzR0wsUtdjWxrUhdn9GvOYwWI9BGPGSDSc6Pd66CShQlmbk+CQqV+oxsYGckkyGUSZn/swiJApMe4Z4BIj2VnZ+Obb77Bd+3qYevQpmhVyxYAXnt74+ePN3ewwq3Qkdi5bAays7NLPS8RiSGp1erX/pqQlZUFKysrZGZmokKFCmWRi4jeglKpRGRkJKZMmYLHj5/dcCgnJwfm5uZIuZeNNSfTEZd8H+mP8v5xGwIJzy4o5F7XDgNaOKCqmQRLy2dnDtja2mL+/PkYNGgQjIyMyv6bIqI3Vtz1m2WASM/ExcVhzJgxSEpKevE1a2trZGRk/Ou5uYUKpD3KxROFCuXkMjjamv/ryoLW1tbIzMx88eeGDRvCz88P7u7upfdNEJFGFHf95piASI/4+PigQ4cOuHTp0j++Xrt27Zc+39xEDpdqVmjiUBEu1axeeonhWrVq/ePPFy9eRIcOHeDj46O54EQkFMsAkR5p0aIFKleuDEn6/2MCZDIZ6tSpU+Jt1q1bFzLZ/39USJKEypUro0WLFm+VlYi0B8sAkR5p2bIlLl++jJo1awJ4tnDLZLIXfy6JmjVrQiaTvSgYNWvWxOXLl9GyZUuNZCYi8VgGiPTMmTNncPXqVXh4eMDGxgYKheKty4BCoYCNjQ08PDxw9epVnDlzRoOJiUg0HkBIpEeysrLQsGFD1KlTB3v37kVGRgaCgoIwcuRI2Nralmibjx49QmBgIDw9PVGxYkV07twZKSkpSExM5OcBkZbj2QREBmjYsGFYv349EhIS4OjoWCrvkZaWBldXV/Tv3x8hISGl8h5EpBk8m4DIwOzevRthYWFYvHhxqRUBAHB0dMTixYsRGhqKPXv2lNr7EFHZ4Z4BIj3w119/oWHDhmjQoAH27Nnzj7MJSoNarUbXrl1x8eJFJCYmwtraulTfj4hKhnsGiAyIt7c3srOzER4eXupFAHh2lkJ4eDiys7Ph7e1d6u9HRKWLZYBIx+3cuRORkZFYsmQJ7O3ty+x97e3tsWTJEkRGRmLXrl1l9r5EpHkcExDpsIyMDLi4uKBx48bYtWtXmewV+Du1Wo3u3bvjwoULSExMRMWKFcv0/Yno1TgmIDIAY8eORV5eHkJDQ8u8CADPxgWhoaHIzc3FuHHjyvz9iUgzWAaIdNT27duxatUq+Pr6okaNGsJy1KhRA76+vli5ciV27NghLAcRlRzHBEQ66NGjR2jYsCGaNWuGHTt2CNkr8HdqtRq9evXCmTNnkJSUBBsbG6F5iOgZjgmI9JiXlxcKCgoQEhIivAgAz8YFISEhKCgogJeXl+g4RPSGWAaIdMzWrVuxdu1aLFu2DNWqVRMd54Vq1aph2bJlWLNmDaKjo0XHIaI3wDEBkQ55+PAhXFxc0LJlS0RHR2vFXoG/U6vV6NOnD44fP46kpCRUqlRJdCQig8YxAZEeGj16NBQKBZYvX651RQB4Ni5Yvnw5FAoFRo8eLToOERUTywCRjti0aRM2bNgAf39/VK1aVXScIlWtWhX+/v7YsGEDNm/eLDoOERUDxwREOuD+/ftwcXFB27ZtsXnzZq3cK/B3arUan332GQ4dOoSkpCTY2dmJjkRkkDgmINITarUanp6eAICgoCCtLwLAs3FBUFAQAMDT0xPF+J2DiARiGSDSchs3bsSWLVsQGBioU79h29nZITAwEFu2bMHGjRtFxyGiV+CYgEiL3b17Fy4uLujYsaPOLqhffPEF9u/fj6SkJFSpUkV0HCKDwjEBkY5Tq9UYMWIEjIyMEBAQIDpOiQUEBEAmk2HkyJEcFxBpKZYBIi21du1abNu2DUFBQahcubLoOCVWuXJlBAUFITo6GuvWrRMdh4hegmMCIi10584duLi44KOPPsLatWtFx9GIr776Crt370ZSUhLeeecd0XGIDALHBEQ6Sq1Ww8PDA+XKlcOyZctEx9GYZcuWoVy5cvDw8OC4gEjLsAwQaZlVq1Zhx44dCA4Ohq2treg4GmNra4vg4GDs2LEDq1evFh2HiP6GYwIiLXLr1i24uLigV69eWLVqleg4peKbb77Bb7/9hsTERFSvXl10HCK9xjEBkY5Rq9UYPnw4zMzM4OvrKzpOqfH19UX58uUxfPhwjguItATLAJGWiIqKwq5duxASEgIbGxvRcUqNjY0NQkJCsGvXLkRFRYmOQ0TgmIBIK9y8eRMNGzZEnz59DGaBHDRoEKKjo5GUlIQaNWqIjkOklzgmINIRarUaQ4cOhYWFBZYuXSo6TplZunQpLCwsMHToUI4LiARjGSASLCwsDDExMQgLC4O1tbXoOGXG2toaYWFh2LNnD8LDw0XHITJoLANEAt24cQMTJkzAkCFD0K1bN9Fxyly3bt0wZMgQeHt748aNG6LjEBksHjNAJIharUbnzp2RnJyMhIQEWFlZiY4kRGZmJho2bIh69eohJiZGJ27RTKQreMwAkZYLDg7Gvn37EBYWZrBFAACsrKwQHh6O2NhYhISEiI5DZJBYBogESE1NxcSJEzF8+HB06dJFdBzhunTpguHDh2PChAlITU0VHYfI4HBMQFTGVCoVOnXqhOvXryMhIQGWlpaiI2mF7OxsuLq6olatWoiNjYVMxt9ViN4WxwREWiooKAhxcXEIDw9nEfgbS0tLhIeHIy4uDkFBQaLjEBkUlgGiMnTt2jVMnjwZI0eORMeOHUXH0TodO3bEyJEjMXnyZFy/fl10HCKDwTEBURlRqVRwd3dHeno6EhISYGFhITqSVsrJyYGrqyscHBwQFxfHcQHRW+CYgEjL+Pv749ChQ4iMjGQReAULCwtERkbi0KFD8Pf3Fx2HyCCwDBCVgZSUFEydOhVjxoxB+/btRcfReu3bt8eYMWMwdepUpKSkiI5DpPc4JiAqZUqlEu3atcPdu3dx/vx5mJubi46kE3Jzc9G4cWNUrVoVBw8ehJGRkehIRDqHYwIiLeHr64tjx44hMjKSReANmJubIzIyEseOHYOfn5/oOER6jWWAqBRduXIF06dPx9ixY9GmTRvRcXROmzZtMHbsWEybNg1XrlwRHYdIb3FMQFRKlEolPvzwQzx69Ajnzp2DmZmZ6Eg6KS8vD25ubrC1tcWRI0c4LiB6AxwTEAm2ZMkSnDx5ElFRUSwCb8HMzAyRkZE4efIklixZIjoOkV5iGSAqBRcvXsQPP/wAb29vtGrVSnQcnde6dWt4e3vjhx9+wKVLl0THIdI7HBMQaZhCoUCrVq2QlZWF+Ph4lC9fXnQkvZCfn48mTZrAysoKR48ehVwuFx2JSOtxTEAkyKJFi3DmzBlERUWxCGhQ+fLlERUVhdOnT2PRokWi4xDpFZYBIg1KTEzEzJkzMWnSJLRo0UJ0HL3TokULTJo0CTNnzkRiYqLoOER6g2MCIg15+vQpWrZsifz8fJw5cwampqaiI+mlgoICNGvWDOXLl8fx48dhbGwsOhKR1uKYgKiMrVy5EufOnUNUVBSLQCkyNTVFVFQUzp07hwULFoiOQ6QXWAaINECtVmPQoEHYu3cvmjdvLjqO3mvevDmmTJmCWbNm4cKFC6LjEOk8jgmINEitVkOSJNExDEJhYSHee+89yOVy/PHHHxwXEL0ExwREpUClUr3ycRaBsmNiYoKoqCgkJCRg3rx5ouMQ6TSWAaI3IJPxR0abNGvWDNOmTcOcOXNw7tw50XGIdBY/2YiKYc+ePWjVqhUKCgpefK0YEzYqAzNmzECDBg0wcOBAPHnyRHQcIp3EMkBUDIMGDUKXLl3+cZYARwLaoVy5clixYgUuXryIOXPmiI5DpJN4ACHRawwcOBBJSUk4ffo0VCoVjh49inXr1qFq1aqoU6cOunfvDisrK9ExDd7s2bMxe/ZsnDx5Es2aNRMdh0grFHf9ZhkgeoUjR46gbdu2SEtLg4ODA8aOHYvY2FjI5XIoFAqYmZnB3d0ds2bN4qWHBXv69Ck++OADPH36FKdPn4aJiYnoSETC8WwCIg2IiYmBtbU1/P39ER4ejh07dsDPzw/nz59HUlISevfujcDAQBw5ckR0VINnbGyMqKgoXLlyBbNnzxYdh0insAwQvcLUqVOxePFiHD9+HJ6envjuu+/QsWPHF6cYTp8+Hfb29khISBCclACgUaNGmDlzJn755RecOnVKdBwincF7gBK9gpmZGQYPHoz33nsPmzZtQpcuXQA8O8VQoVBApVKhVq1ayM/PF5yUnpsyZQqio6MxcOBAnD17lpeGJioG7hkgKgZXV1dMnz4dbm5uL74ml8tx4sQJnDhxAn379hUXjv5BLpdjxYoVuHbtGmbOnCk6DpFOYBkgKiYTExOUK1cOwLNrDOzduxejRo3CsGHDUL9+fcHp6O9cXFwwa9YsLFq0CCdOnBAdh0jr8WwCohLIz8+Hl5cXMjMzsXHjRtFx6CUUCgVat26NzMxMxMfH82wPMkg8tZBIQ4q6+ZBarUZBQQEXGS126dIlNGnSBKNHj8aiRYtExyEqczy1kEgDjh07hjlz5rz0BkWSJLEIaLn69etjzpw5WLJkCY4ePSo6DpHW4p4BoiLk5eWhcePGqFy5Mg4fPgwjIyPRkagElEol2rRpg4cPH+LcuXMwMzMTHYmozHDPANFbmj59Ov78809ERUWxCOgwIyMjREZG4ubNm5g+fbroOERaiWWA6CUOHToEX19fzJs3D3Xr1hUdh96Ss7Mz5s2bB19fXxw6dEh0HCKtwzEB0f/Izc1Fo0aNUK1aNRw4cIB7BfSEUqlE+/btcfv2bVy4cAHm5uaiIxGVOo4JiEpo6tSpuHPnDiIjI1kE9MjzccGdO3fw/fffi45DpFVYBoj+Ji4uDv7+/pg/fz6cnJxExyENc3Jywi+//IJly5bhwIEDouMQaQ2OCYj+KycnB66urnj33Xexf/9+yGTsyvpIpVLB3d0d6enpSEhIgIWFhehIRKWGYwKiNzR58mQ8ePAAERERLAJ6TCaTITIyEg8ePMDkyZNFxyHSCvzEIwIQGxuLoKAgLFiwALVq1RIdh0pZrVq1MH/+fAQFBWHfvn2i4xAJxzEBGbysrCy4urrCyckJe/fu5V4BA6FSqdCpUydcu3YNCQkJ/GwjvcQxAVExTZo0CY8fP0Z4eDiLgAGRyWSIiIjA48ePMWnSJNFxiITiJx8ZtJiYGISEhGDRokVwdHQUHYfKmKOjIxYtWoSQkBDExMSIjkMkDMcEZLAyMzPRsGFD1KtXDzExMS+9MyHpP7VajS5duuDy5ctITEyElZWV6EhEGsMxAdFreHt7IzMzE+Hh4SwCBkySJISHhyMzMxMTJkwQHYdICJYBMki7du1CREQEfHx84ODgIDoOCebg4IAlS5YgPDwcv//+u+g4RGWOYwIyOBkZGWjYsCEaNWqEXbt2ca8AAXg2LujWrRsSEhKQmJiIihUrio5E9NY4JiAqwvjx45Gbm4vQ0FAWAXpBkiSEhYUhNzcX48ePFx2HqEyxDJBB2bFjB1asWIGlS5eiRo0aouOQlqlRowZ8fHywYsUK7NixQ3QcojLDMQEZjMePH8PFxQXNmjXDjh07uFeAXkqtVqNnz56Ij49HYmIibGxsREciKjGOCYj+h5eXFwoKChASEsIiQEWSJAkhISHIz8/H2LFjRcchKhMsA2QQfv31V6xZswZ+fn6oVq2a6Dik5apXrw4/Pz+sXr0av/76q+g4RKWOYwLSew8fPoSLiwtatGiBX3/9lXsFqFjUajV69+6NkydPIikpCba2tqIjEb0xjgmI/mvMmDFQKBQIDg5mEaBikyQJy5cvx5MnTzBmzBjRcYhKFcsA6bUtW7Zg/fr18Pf3R9WqVUXHIR3zzjvvwN/fH+vWrcOWLVtExyEqNRwTkN568OABXFxc8OGHH2LLli3cK0Alolar8emnn+LIkSNISkpC5cqVRUciKjaOCcjgjRo1CiqVCkFBQSwCVGKSJCEoKAgqlQqjRo0SHYeoVLAMkF7auHEjNm3ahMDAQFSpUkV0HNJxVapUQUBAADZt2oSNGzeKjkOkcRwTkN65d+8eXFxc0KFDB35wk8ao1Wp88cUXiIuLQ1JSEksm6QSOCcggqdVqjBw5EjKZDAEBAaLjkB6RJAmBgYGQyWQYOXIkivF7FJHOYBkgvbJ+/XpER0cjKCiIB3qRxlWuXBlBQUGIjo7G+vXrRcch0hiOCUhv3LlzBy4uLujatSvWrVsnOg7psf79+yMmJgZJSUk8ZZW0GscEZFDUajU8PDxQrlw5+Pv7i45Dem7ZsmWQy+UYMWIExwWkF1gGSC+sXr0aO3bsQHBwMC8bS6WuUqVKWL58ObZt24Y1a9aIjkP01jgmIJ13+/ZtuLi4oEePHli9erXoOGRABgwYgJ07dyIpKYk3wCKtxDEBGQS1Wo3hw4fD1NQUfn5+ouOQgfHz84OpqSmGDx/OcQHpNJYB0mkrVqzAzp07ERISAhsbG9FxyMDY2NggJCQEO3fuxMqVK0XHISoxjglIZ/35559wcXFBnz59EBUVJToOGbCBAwdi27ZtSExMRI0aNUTHIXqBYwLSa2q1GkOHDoWFhQWWLl0qOg4ZuKVLl8Lc3BzDhg3juIB0EssA6aSIiAjs2bMHYWFhsLa2Fh2HDFzFihURGhqK3bt3IyIiQnQcojfGMkA6Jz09HePHj8d3332Hbt26iY5DBADo3r07Bg8ejPHjxyM9PV10HKI3wjJAOkWtVmPIkCGwsrLCkiVLRMch+oclS5bAysoKQ4cO5biAdArLAOmUkJAQxMbGIjw8HFZWVqLjEP2DtbU1wsLCsHfvXoSGhoqOQ1RsLAOkM9LS0jBx4kQMGzYMXbp0ER2H6KW6du2KYcOGYcKECUhLSxMdh6hYeGoh6QSVSoXOnTvj6tWrSEhI4L9D0mpZWVlwdXWFk5MT9u7dC5mMv3eRGDy1kPTK8uXLsX//foSHh7MIkNarUKECwsPDsX//fgQHB4uOQ/RaLAOk9a5fv45JkyZh5MiR6NSpk+g4RMXSqVMnjBgxApMmTcL169dFxyF6JY4JSKupVCq4u7sjPT0dCQkJsLCwEB2JqNiys7PRqFEjvPvuu9i/fz/HBVTmOCYgvRAQEIBDhw4hMjKSRYB0jqWlJSIiInDw4EEEBASIjkNUJJYB0lpXr17FlClTMHr0aLRv3150HKIScXd3x6hRozBlyhRcvXpVdByil+KYgLSSUqlEu3btcOfOHVy4cAHm5uaiIxGVWE5ODho3boxq1arh4MGDHBdQmeGYgHSan58fjh07hqioKBYB0nkWFhaIjIzEkSNH4OfnJzoO0b+wDJDWuXLlCqZNmwYvLy+0adNGdBwijWjbti3Gjh2L77//HsnJyaLjEP0DxwSkVZRKJdq0aYMHDx7g/PnzMDMzEx2JSGPy8vLQuHFjVK5cGYcPH4aRkZHoSKTnOCYgneTj44MTJ04gKiqKRYD0jpmZGaKionDixAksXbpUdByiF1gGSGtcunQJM2bMgLe3N1q3bi06DlGpaN26NcaPH4/p06fj8uXLouMQAeCYgMpIbqECaY9y8UShQjm5DI625jA3kb94XKFQoHXr1sjMzER8fDzKly8vMC1R6crPz4ebmxusra1x9OhRyOXy17+IqASKu37zXyCVmpR72VhzMh1xV+4j/XEe/t46JQAONmZwd7bD1x84YGtUIE6fPo2jR4+yCJDeK1++PFasWIHWrVtj8eLFmDJliuhIZOC4Z4A07ubjPEyLTsDhqw9hJJOgVBX9T+z54wVp5/CpwxMEzJ9VhkmJxJo8eTJ8fX1x9uxZuLi4iI5Deqi46zfLAGnU+lPpmLk9CQqV+pUl4F/UKpgYyzHrYxd82dyh9AISaZGCggI0adIEFhYWOH78OMcFpHE8m4DKnH9cCqZuTUChQvVmRQAAJBkKFSpM3ZoA/7iU0glIpGVMTU2xYsUKnD17FgsWLBAdhwwYywBpxPpT6VgUo5kLqSyKScaGU+ka2RaRtnv//fcxe/ZsODs7i45CBoxjAnprNx/noZPPQRQqVEU+58n9VGSd2oaC9AQocx5DkhnB2KY6zOq3gUXjrjAqb/mP55vIZYgd3w72NrzWAOk/tVoNpVLJMQFpHM8moDIzLToBileMBbLP7cbjmCAY21SH1Qd9YWxrD7VKiSd3U5AT/zsKb12G3acz/vEahUqNadEJWDXkg9KOTyScJEnFKgLp6enIzMyEq6trGaQiQ8IyQG8l5V42Dl99WOTjhbcu4fGeQJjWbAK7vjMgyY1fPFa+ZhNUeL8P8q+f/dfrlCo1Dl99iKv3s+FkZ/mvx4kMTW5uLlavXo29e/fi559/RosWLURHIj3CYwboraw5mQ4jmVTk45nHNgKSBNuPRv+jCDwnGRnDrM7Lf/s3kklYfYLHDhCpVCqYm5vjm2++gaurKz799FPRkUjPsAzQW4m7cr/IMwfUKiUK0i+gXFUnyCtUfuNtK1VqxCXff9uIRDpNqVRCJnv2UV1YWIj9+/fjr7/+wpEjRwQnI33CMkAlllOoQPrjvCIfV+VnQf20EHKrKiV+j/RHecgtVJT49US6TKFQvLiz4bx58+Ds7Izq1atj9+7daNKkieB0pE94zACV2I1HuXjDqwm8MTWAtEe5cKlmVcrvRKQdzp8/j8LCQrz//vuQy+W4du0a+vXrh+TkZMybNw/ffvst3nnnHdExSc9wzwCV2JNXnEoIALLyFSAZm0CRea9U34dIn+zbtw9dunRBXl4eFi5cCGdnZ1SoUAE7d+7EuHHjWASoVHDPAJVYOfmru6QkM4Lpu42Rf/0MFFkPIa9QqVTeh0ifeHt7Y8WKFbCysoKFhQV++uknfPvtt6hevbroaKTH+ClLJeZoa46izyN4xqrl54BajUe7l0GtfPqvx9VKBfJSThb5eum/70NkSLZs2QK1Wg0vLy9MmjSJRYBKHcsAlZi5iRwOr7lCoEn1+rDp6omCtHO4EzUO2Wd3oiA9Aflp55B5cgtuh41EzoW9Rb7ewdYM5ibcgUWGxcnJCd9//z2Cg4Px119/iY5DBoCfsvRW3J3tsOrkjVfemMjS7SOYvFMXWae2IfPEZihzMyDJ5DC2qQ7zBu1h2aznS19nJJPgXteutKITabWffvoJaWlpOHfuHDp16iQ6Duk53puA3krKvWx0Xnqo1LbfTXUKNW3N8Pyf6fP//fzzz1G7du1Se18ibVBQUABTU1PRMUiH8d4EVCbqVLFEG6dKOHb90ZvftvgVjGQScq/HY/n6WZAkCTKZDJIkvbihi5GRESZNmqSx9yPSRi8rAiqV6sVFiIg0hf+i6K3N6+MK+SsuSVwScpmExf2a/aMAKBQKKJVKmJqaYtCgQRp9PyJdoFKpkJ2djeRkzdwunOg5lgF6a/Y2Zpj1sYtGtzn7Yxd83fsjzJo161+POTo64uHDom+ORKSvJEnCgAED0LNnT+TlFX31T6I3xTJAGvFlcwdM7FJXI9ua1MUZ/Zo7AACmTZuGDh06vLgkq1wuR1ZWFlxcXNC/f39cvHhRI+9JpAskScKiRYtw8+ZNzJgx4/UvIComlgHSmMbyu3j0+zLIJfUr72T4MkYyCSZyGeb3dcUod6f//7qREdatWwdbW1sAgJeXF65fv46goCAcO3YMDRs2xJdffomkpCSNfi9E2srZ2Rlz587F0qVLcfjwYdFxSE+wDJBG5ObmYvDgwWhskYPY8e3Qqtazxft1peD5461q2SJ2fLsXewT+zs7ODlu2bMGHH36IyZMnw8TEBB4eHkhJScHy5ctx4sQJuLq64osvvkBCQoLmvzkiLTN27Fi0atUKgwcPRm5urug4pAd4aiFphJeXF8LCwnDu3DnUrftsXJByLxtrTqYjLvk+0h/l/eOmRhKeXVDIva4dBrRwgJOdZYnf+8mTJ1i5ciXmzp2LtLQ0fPrpp/jxxx/RqFGjt/umiLRYcnIy3NzcMGzYMPj6+oqOQ1qquOs3ywC9tQMHDsDd3R1Lly7F2LFjX/qc3EIF0h7l4olChXJyGRxtzTV+ZcGnT59i1apVmDNnDlJTU9G3b1/8+OOPaNy4sUbfh0hb+Pr6Yty4cThw4ADatWsnOg5pIZYBKhM5OTlwdXWFvb09Dhw4oBXnPz99+hSrV6/G3Llzce3aNfTu3Rs//vgj7/9OekelUqF9+/b4888/ceHCBVhYWIiORFqmuOu3+E9u0mmTJ0/G/fv3ERkZqRVFAACMjY0xePBgXL58GVFRUUhMTETTpk3xySef4OzZs6LjEWmMTCZDZGQk7t27hylTpoiOQzpMOz69SSft27cPQUFBmD9/vlZeGlgul2PgwIG4dOkSVq5ciUuXLqFZs2b4+OOPcebMGdHxiDSidu3amD9/PgIDA7F//37RcUhHcUxAJZKVlQVXV1fUqlUL+/bt05q9Aq+iUCiwfv16/PTTT0hOTkaPHj0wc+ZMNG/eXHQ0oreiUqnQsWNHpKamIiEhAZaWJT8gl/QLxwRUqiZNmoRHjx4hIiJCJ4oA8GxPwYABA3Dx4kWsWbMG165dw/vvv4/u3bvj5MmTouMRlZhMJkNERAQePnzIe3ZQiejGpzhplZiYGISEhGDRokWoWbOm6DhvzMjICF999RUSExOxbt06pKWloUWLFujWrRtOnDghOh5RidSsWROLFi1CcHAwYmJiRMchHcMxAb2RzMxMuLq6om7duti7dy8kSbM3KBJBqVRi8+bNmD17Ni5evIguXbpg5syZaNWqlehoRG9ErVajc+fOSE5ORkJCAqysrERHIsE4JqBSMWHCBGRkZCA8PFwvigDwbE9Bv379kJCQgI0bN+L27dto3bo1OnfujCNHjoiOR1RskiQhPDwcGRkZmDhxoug4pENYBqjYfv/9d4SHh2PJkiV49913RcfROJlMhs8//xznz5/H5s2bce/ePbRp0wadOnXiNeBJZ7z77rtYsmQJwsLCsHv3btFxSEdwTEDF8tdff8HFxQUNGzbE7t279WavwKuoVCr8+uuvmD17Ns6fPw93d3fMnDmTV3ojradWq/HRRx8hKSkJiYmJsLa2Fh2JBOGYgDRq/PjxyMnJQVhYmEEUAeDZnoK+ffvi7NmziI6ORkZGBtq3b4/27dvjwIEDouMRFUmSJISFhSE7Oxvjx48XHYd0AMsAvdZvv/2GqKgo+Pj4wN7eXnScMieTydC7d2+cPXsW27ZtQ1ZWFtzd3dGuXTvs378fxdi5RlTm7O3t4ePjg6ioKOzcuVN0HNJyLAP0So8fP8bw4cPRrVs3DB48WHQcoSRJenH1wu3btyM3NxcdO3ZE27ZtERsby1JAWmfw4MHo1q0bhg0bhoyMDNFxSIuxDNArjR07Fnl5eQgNDTWY8cDrSJKEXr164dSpU/jtt99QUFCAzp0748MPP8TevXtZCkhrSJKE0NBQ5OXlFXlHUSKAZYBeYdu2bVi9ejX8/PxQvXp10XG0jiRJ6NGjB/744w/s3LkTCoUCXbp0QevWrbFnzx6WAtIK1atXh6+vL1atWoVt27aJjkNaimWAXurRo0fw8PBAz5498c0334iOo9UkSUL37t1x4sQJ/P777y+O5G7ZsuWLPxOJ9O2336Jnz57w8PDAo0ePRMchLcQyQC81ZswYPHnyBMHBwRwPFJMkSfjoo49w7Ngx7NmzBzKZDN27d0eLFi2wa9culgISRpIkBAcH48mTJ/Dy8hIdh7QQywD9y5YtW7Bu3TosW7YM1apVEx1H50iShC5duuDo0aOIiYmBsbExevTogffffx+//fYbSwEJUa1aNSxbtgxr167F1q1bRcchLcMyQP/w4MEDjBw5Er1798ZXX30lOo5OkyQJnTt3xuHDhxEbG4vy5cujV69eaN68ObZv385SQGXuq6++Qu/evTFixAg8ePBAdBzSIiwD9A+jR4+GSqXC8uXLOR7QEEmS0LFjRxw8eBD79++Hubk5PvnkEzRr1gzbtm1jKaAyI0kSgoKCoFQqMXr0aNFxSIuwDNALGzduxMaNG+Hv748qVaqIjqN3JEmCu7s7Dh48iLi4OFhZWaF3795o2rQpoqOjoVKpREckA1C1alUEBARg48aN2LRpk+g4pCVYBggAcO/ePXh6euLTTz9Fv379RMfRe+3bt0dcXBwOHjwIGxsb9O3bF02aNMGWLVtYCqjU9evXD59++ik8PT1x//590XFIC7AMENRqNTw9PSFJEgIDAzkeKENt27bFvn37cOjQIVSuXBmfffYZ3NzcsHnzZpYCKjXPf9YBwNPTk6MqYhkgYMOGDdi6dSsCAwNhZ2cnOo5BatOmDWJjY3HkyBFUrVoVn3/+ORo3boyNGzeyFFCpsLOzQ2BgILZs2YINGzaIjkOCsQwYuLt372LUqFHo168fPv/8c9FxDF7r1q0RExODY8eOoXr16ujXrx9cXV2xfv16KJVK0fFIz3z++ef44osvMGrUKNy9e1d0HBKIZcCAqdVqjBgxAnK5HP7+/qLj0N+0bNkSu3fvxvHjx+Hg4ID+/fvD1dUV69atYykgjQoICIBcLseIESM4LjBgLAMGbM2aNdi2bRuWL1+OSpUqiY5DL9GiRQv8/vvvOHHiBGrWrImvvvoKDRs2xJo1a1gKSCMqVaqE5cuXY9u2bVi7dq3oOCQIy4CBun37Nry8vPDVV1+hT58+ouPQa3zwwQfYuXMn/vjjDzg5OWHAgAFo0KABVq1aBYVCIToe6bg+ffqgf//+GDNmDG7fvi06DgnAMmCA1Go1PDw8YGJiAj8/P9Fx6A00b94cO3bswKlTp+Ds7Ixvv/0WDRo0wMqVK1kK6K0sW7YM5cqVg4eHB8cFBohlwACtXLkSv/32G4KDg2Frays6DpXAe++9h+3bt+PMmTNo0KABBg4ciPr16yMqKoqlgErE1tYWwcHB+O2337Bq1SrRcaiMsQwYmD///BNjx47FN998g48//lh0HHpLTZs2xa+//oqzZ8+iYcOGGDx4MJydnREREYGnT5+Kjkc65pNPPsE333wDLy8v3Lp1S3QcKkMsAwZErVZj2LBhMDMzg6+vr+g4pEFNmjRBdHQ0zp07Bzc3NwwZMgTOzs4IDw9nKaA34uvrCzMzMwwbNozjAgPCMmBAIiMjsXv3boSGhqJixYqi41ApaNy4MbZs2YLz58+jWbNmGDp0KOrWrYvQ0FA8efJEdDzSARUrVkRoaCh+//13REZGio5DZYRlwECkp6dj/PjxGDx4MHr06CE6DpWyRo0aYdOmTbhw4QKaN28ODw8P1K1bF8HBwSwF9Fo9evTAoEGDMH78eNy8eVN0HCoDLAMGQK1WY+jQobC0tMSSJUtEx6Ey5Orqio0bNyIhIQEtWrTAyJEj4eTkhOXLl6OwsFB0PNJiPj4+sLS0xNChQzkuMAAsAwYgNDQUe/fuRVhYGKytrUXHIQFcXFywfv16JCYm4sMPP4SnpyecnJwQGBjIUkAvZW1tjbCwMMTExCAsLEx0HCplLAN67saNG5gwYQKGDh2Kjz76SHQcEqxBgwZYu3YtkpKS0LZtW4wZMwa1a9eGv78/CgoKRMcjLfPRRx9hyJAh8Pb2xo0bN0THoVIkqYux/ycrKwtWVlbIzMxEhQoVyiIXaYBKpULnzp2RkpKCxMRE/t3Rv1y5cgVz5szB2rVrUbVqVUydOhXDhg2Dqamp6GikJTIzM+Hq6oq6deti7969vMW5jinu+s09A3osODgY+/fvR3h4OIsAvZSzszNWrVqFS5cuoVOnThg3bhxq1aoFX19f5Ofni45HWsDKygrh4eHYt28fgoODRcehUsIyoKdSU1MxadIkeHh4oHPnzqLjkJarW7cuVqxYgcuXL6NLly6YMGECatWqBR8fH+Tl5YmOR4J17twZHh4emDhxIlJTU0XHoVLAMYEeUqlU6NixI1JTU5GQkABLS0vRkUjHXLt2DXPnzsXKlStRqVIlTJ48GSNGjICZmZnoaCRIdnY2XF1dUbNmTezbtw8yGX+X1AUcExiwwMBAHDhwABERESwCVCK1a9dGREQEkpOT0bNnT0yZMgU1a9bEokWLkJubKzoeCWBpaYnw8HAcOHAAgYGBouOQhrEM6JmrV69iypQpGDVqFDp06CA6Dum4WrVqISwsDMnJyfj444/x/fffo2bNmliwYAFycnJEx6My1rFjR3h6emLKlCm4du2a6DikQRwT6BGVSoV27drh1q1buHDhAiwsLERHIj2TlpaGn3/+GZGRkbCyssLEiRMxatQo/lszIDk5OWjUqBFq1KiBAwcOcFyg5TgmMEB+fn44cuQIIiMj+eFMpcLR0RHBwcFISUnBZ599hh9++AGOjo74+eefkZ2dLToelQELCwtERkbi8OHDWLZsmeg4pCHcM6AnkpOT4ebmhmHDhvGOhFRm0tPT8csvvyA8PBwWFhbw9vbGmDFj+DlhALy8vBAWFoZz586hbt26ouNQEYq7frMM6AGlUom2bdvi/v37OHfuHMzNzUVHIgNz8+ZNzJ8/H6GhoTA3N39RCqysrERHo1KSm5uLxo0bo0qVKjh06BCMjIxER6KX4JjAgCxduhTHjx9HZGQkiwAJYW9vD39/f1y7dg1ff/015syZA0dHR8yePRuZmZmi41EpMDc3R2RkJI4fP869kXqAewZ03OXLl+Hm5gZPT0/ekZC0xu3btzF//nwEBwfD1NQU48aNw7hx43ijLD3k7e2NoKAgxMfHo169eqLj0P/gmMAAKJVKtG7dGhkZGYiPj+cFYUjr3LlzBwsWLMDy5cthYmKCsWPHYty4cahYsaLoaKQheXl5cHNzg42NDY4ePcpxgZbhmMAALF68GKdOnUJUVBSLAGmld955Bz4+PkhNTcV3332HhQsXwtHRET/88AMeP34sOh5pgJmZGaKiovDHH39g8eLFouNQCbEM6KiLFy/ihx9+wIQJE9CyZUvRcYheqWrVqliyZAlSU1MxbNgwLF68GI6OjpgxYwYePXokOh69pVatWmHChAn48ccfcfHiRdFxqAQ4JtBBCoUCLVu2RE5ODuLj43m7WdI59+/fx6JFixAQEACZTIYxY8bA29sblSpVEh2NSig/Px9NmzaFpaUljh07BrlcLjoSgWMCvbZw4UKcPXsWUVFRLAKkk+zs7LBgwQKkpaXB09MTfn5+cHR0xNSpU/HgwQPR8agEypcvj6ioKJw5cwYLFy4UHYfeEMuAjsnLy8P69esxefJkfPDBB6LjEL2VypUrY/78+UhLS8OYMWMQEBCAmjVrYsqUKSwFOuiDDz7ApEmTMHPmTCQkJIiOQ2+AYwIdo1AooFarIUkSd8OR3nn48CF8fHzg5+cHlUoFT09PTJo0CXZ2dqKjUTEVFBSgWbNmMDU1xYkTJ2BsbCw6kkHjmEBPyeVyGBsbswiQXqpUqRLmzp2LtLQ0jB8/HsHBwXB0dMTEiROhUChEx6NiMDU1RVRUFM6fP4/58+eLjkPFxDJARFrH1tYWc+bMQVpaGiZOnIiMjIw3LsAJCQnIyMgopYT0Ks2bN8fUqVMxe/ZsnD9/XnQcKgaOCYhI6ymVSkiSVOTtcpVKJWQyGSRJAgA8fvwYP/30E37//Xe0bNkSc+fORbVq1coyssErLCzEe++9B7lcjpMnT6JcuXKiIxkkjgl0lEqlEh2BSOsYGRm9tAg8/3kxMjKCJEkvRglmZmb47rvv4O/vj+zsbDRt2hQrVqwo08yGzsTEBCtWrEBCQgLmzZsnOg69BsuAlgkPD0dKSoroGEQ6IS0tDe3atcOUKVOgUChejBJMTU3h6uqKTp06YfPmzfDw8MDatWvx119/iQ1sYJo2bYrp06dj7ty5iI+PFx2HXoFlQIuMGTMGHh4eGDZsGGJjY5Gfny86EpFWq1WrFsaPH49Dhw7B0tISJ06cAPBsTPD3UxO7du2KvXv3Ijc3V1RUgzV9+nS4uLhg4MCBePLkieg4VASWAS1x6dIl7Nu3D35+fpAkCb169cIvv/yC9PR00dGItFrv3r1x7Ngx7NmzB/b29gCAa9euoVGjRujTpw8iIiIwZMgQtG7dGhYWFoLTGp5y5cohKioKly5dwk8//SQ6DhWBZUBL3L17Fx988AG6deuGuLg4LFy4ED///DP69++Pffv2oaCgAABw/PhxBAQE8NgCor+RJAlt27ZF9erVATw7mn3Hjh148OABli5digkTJmDTpk2wsrISnNQwubm54YcffsDPP/+M06dPi45DL8EyoCXatGmD8ePHo3bt2gCA0aNHIy0tDTKZDL169cKCBQtw5swZfPHFF3j8+HGRR1UTGZrnJ0Q9ePAA2dnZL77+3nvvYdmyZcjNzUWTJk1QtWpVUREJwPfff49GjRph0KBBKCwsFB2H/gdXFC0hl8vRqFEjAM+OkFYqlahWrRoOHz6Mn3/+GfPnz8eHH34ICwsL/PDDD4LTEmmP56cT+vv7IzQ09B+PNWnSBE+ePMH9+/dFRKO/MTY2xooVK5CcnIxZs2aJjkP/g2VAC8lkMhgZGb04TWrs2LHw8/NDYWEhtm7dKjgdkfZRqVSwtLTEkiVL8OWXXyI+Ph5nz57F8OHDYWlpCaVSKToiAXB1dcXMmTMxf/58/PHHH6Lj0N/wokM64M6dO3BxccGgQYOwZMkS0XGItFZaWhomTZqE06dPo2rVqkhOToavry/69OkDc3PzF89TqVS4desWZs2ahalTp8LJyUlgasOiUCjQokUL5Obm8hbsZYAXHdIjSqUSHh4eLAJEr+Ho6IhNmzbhxIkTCA4ORnJyMgYMGPCPIgA8Gy1cuXIFO3fuRL169TBo0CBe36OMyOVyrFixAtevX8ePP/4oOg79F/cMaImCggIYGxvDyMjopY+rVCoeNEikYfn5+QgNDcUvv/yCe/fu4euvv8aMGTNQt25d0dH03vz58zFt2jQcOXIELVu2FB1Hb3HPgA7Jz8/H+++/jw0bNqCobsYiQKR55cuXh5eXF65fv46lS5di3759qF+/PgYMGIDLly+LjqfXJkyYgObNm2PQoEG8wJoW4AqjBWbMmIHk5GQ0bdr0xZHRRFR2TE1NMWbMGFy7dg1+fn44cOAAGjRogK+//hqXLl0SHU8vyeVyREVF4caNG5gxY4boOAaPZUCwI0eOwMfHB3PnzkW9evVExyEyaKamphg1ahSuXbuGgIAAHDp0CC4uLujfvz8uXrwoOp7eqVevHubMmQMfHx8cOXJEdByDxmMGBMrNzYWbmxvs7Oxw6NChIo8XICIxCgsLERkZiXnz5uHPP//E559/jh9++AENGzYUHU1vKJVKtGnTBg8ePMD58+dhZmYmOpJe4TEDOmDatGm4desWIiMjWQSItJCJiQlGjBiBq1evYvny5Thx4gRcXV3xxRdfICEhQXQ8vWBkZISoqCj8+eefmDZtmug4BotlQJCDBw/Cz88P8+bN45HLRFquXLlyGD58OFJSUhASEoJTp06hUaNG+Oyzz3DhwgXR8XRe3bp1MW/ePPj6+uLgwYOi4xgkjgkEyMnJQePGjVG9enUcOHCAZwoQ6ZinT59i5cqVmDt3LlJTU9GnTx/8+OOPcHNzEx1NZymVSrRv3x63b9/G+fPneYdJDeGYQItNnToVd+/eRUREBIsAkQ4yNjbGkCFDcOXKFUREROD8+fNo0qQJ+vTpg/j4eNHxdJKRkREiIyNx584dTJ06VXQcg8OVqIzt378fAQEBmD9/Pi+BSqTjjI2NMXjwYFy+fBmRkZFISEhA06ZN8cknn+DMmTOi4+kcJycnzJ8/HwEBAYiLixMdx6BwTFCGsrOz4erqipo1a2Lfvn3cK0CkZxQKBdauXYs5c+YgJSUFPXv2xMyZM/Hee++JjqYzVCoVOnTogBs3buDChQuwtLQUHUmncUyghSZPnoyHDx8iPDycRYBID8nlcnz77be4ePEiVq1aheTkZDRv3hw9e/bEqVOnRMfTCTKZDBEREXjw4AEmT54sOo7B4IpURvbu3Yvly5dj4cKFqFWrlug4RFSK5HI5BgwYgIsXL2L16tW4evUq3n//fXTv3h0nT54UHU/r1apVCwsWLMDy5cuxd+9e0XEMAscEZSArKwsNGzZE3bp1ERMTw70CRAZGqVRi48aN+Omnn3Dp0iV07doVM2fO5A16XkGlUqFz585ISUlBYmIi154S4phAi0yYMAEZGRkcDxAZKCMjI/Tv3x8JCQlYv349bt68iVatWqFr1644duyY6HhaSSaTITw8HBkZGZg4caLoOHqPK1Mp27NnD8LCwrB48WK8++67ouMQkUBGRkbo168fEhISsGHDBty6dQutW7dG586deW3+l3B0dMSiRYsQGhqKPXv2iI6j1zgmKEV//fUXGjZsiAYNGmDPnj28IyER/YNKpcLWrVsxe/ZsJCQkoEOHDpg5cybatm0rOprWUKvV6NKlCy5duoTExERYW1uLjqRTOCbQAt7e3sjOzkZ4eDiLABH9i0wmw2effYZz585hy5YtePjwIdq1a4cOHTrwsrz/JUkSwsPDkZWVBW9vb9Fx9BbLQCnZuXMnIiMj4ePjA3t7e9FxiEiLyWQy9O3bF/Hx8di6dSsyMjLQvn17tG/fHnFxcSjGDly95uDgAB8fH0RGRmLXrl2i4+gljglKQUZGBlxcXODm5oadO3dyrwARvRG1Wo3t27dj1qxZiI+PR5s2bfCf//wH7u7uBvt5olar0b17d1y4cAGJiYmoWLGi6Eg6gWMCgcaNG4e8vDyEhIQY7A8uEZWcJEkvLmm8fft25ObmomPHjmjbti1iY2MNck+BJEkIDQ1Fbm4uxo0bJzqO3mEZ0LDt27dj5cqV8PX1RY0aNUTHISIdJkkSevXqhdOnT2PHjh0oKChA586d8eGHHyImJsbgSkGNGjWwdOlSrFy5Etu3bxcdR6+wDGjQo0eP4OHhgZ49e+Lbb78VHYeI9IQkSejZsyf++OMP7Ny5EwqFAl27dkWrVq2wZ88egyoFAwcORI8ePeDh4YHHjx+LjqM3WAY0yMvLC4WFhQgODuZ4gIg0TpIkdO/eHSdOnMDvv/8OtVqNjz76CC1btnzxZ30nSRJCQkJQUFAALy8v0XH0BsuAhkRHR2Pt2rXw8/NDtWrVRMchIj0mSRI++ugjHD9+HLt374ZMJkP37t3RokUL7Ny5U+9LQbVq1eDn54c1a9YgOjpadBy9wDKgAQ8fPsSIESPwySef4OuvvxYdh4gMhCRJ6Nq1K44ePYqYmBgYGxujZ8+eeP/99/Hbb7/pdSkYMGAAPv74Y4wYMQIPHz4UHUfnsQxowOjRo6FQKLB8+XKOB4iozEmShM6dO+Pw4cOIjY2FqakpevXqhebNm2P79u16WQokSUJwcDAUCgVGjx4tOo7OYxl4S5s2bcKGDRsQEBCAqlWrio5DRAZMkiR07NgRhw4dwr59+2Bubo5PPvkEzZo1w6+//qp3paBq1arw9/fHhg0bsHnzZtFxdBrLwFu4f/8+PD090bdvX/Tr1090HCIiAM9KwfNLGsfFxaFChQro06cPmjRpgujoaKhUKtERNebLL79Enz59MHLkSNy/f190HJ3FMlBCarUanp6eAICgoCCOB4hIK7Vv3x4HDhzAgQMHYGNjg759+6JJkybYsmWLXpQCSZIQFBT04jNZ3/Z+lBWWgRLauHEjtmzZgsDAQNjZ2YmOQ0T0Su3atcP+/ftx6NAhVK5cGZ999hnc3NywadMmnS8FVapUQWBgILZs2YKNGzeKjqOTWAZK4O7du/D09MQXX3yBzz//XHQcIqJia9OmDWJjY3H48GFUqVIFX3zxBRo1aoSNGzfqdCl4/nk8atQo3Lt3T3QcncMy8IbUajVGjhwJuVyOgIAA0XGIiErkww8/xN69e3H06FFUr14d/fr1g6urK9avXw+lUik6XokEBARAJpNh5MiRHBe8IZaBN7Ru3Tr8+uuvCAoKQqVKlUTHISJ6K88vaXzs2DE4ODigf//+cHV1xdq1a3WuFFSuXBlBQUGIjo7GunXrRMfRKSwDb+DOnTsYPXo0+vfvj759+4qOQ0SkMc8vaXzixAk4Ojri66+/houLC9asWaNTpeDTTz/Fl19+idGjR+POnTui4+gMloFiUqvV8PDwQLly5bBs2TLRcYiISsUHH3yAXbt24eTJk3BycsKAAQPQoEEDrFq1CgqFQnS8YvH390e5cuXg4eHBcUExsQwU06pVq7Bjxw4EBwfD1tZWdBwiolL1/JLGp06dgrOzM7799ls0aNAAK1as0PpSYGtri+XLl2PHjh1YvXq16Dg6gWWgGG7dugUvLy8MGDAAn3zyieg4RERl5r333sP27dtx+vRp1K9fH4MGDUK9evUQFRWl1aWgd+/e+Prrr+Hl5YVbt26JjqP1WAZeQ61WY/jw4TAzM4Ovr6/oOEREQjRr1gzbtm3D2bNn4erqisGDB8PZ2RkRERF4+vSp6Hgv5efnB1NTUwwfPpzjgtdgGXiNqKgo7Nq1CyEhIbCxsREdh4hIqOeXNI6Pj4ebmxuGDBkCZ2dnhIWFaV0psLGxQUhICHbt2oWoqCjRcbQay8Ar3Lx5E+PGjcOgQYPQs2dP0XGIiLSGm5sbtmzZgvPnz6Np06YYNmwY6tSpg9DQUDx58kR0vBd69eqFgQMHYty4cfjzzz9Fx9FaLANFUKvVGDZsGCwtLeHj4yM6DhGRVmrUqBE2b96MCxcu4P3334eHhwfq1KmD4OBgrSkFS5cuhYWFBYYOHcpxQRFYBooQHh6OPXv2IDQ0FNbW1qLjEBFpNVdXV2zcuBEJCQlo2bIlRo4cCScnJwQFBaGwsFBoNmtra4SGhmLPnj0IDw8XmkVbsQy8xI0bN+Dt7Y0hQ4agW7duouMQEekMFxcXrF+/HomJiWjdujVGjRoFJycnBAYGCi0F3bt3x3fffQdvb2/cuHFDWA5txTLwP9RqNYYMGQJra2ssXrxYdBwiIp3UoEEDrFu3DklJSWjbti3GjBmD2rVrw9/fHwUFBUIyLVmyBFZWVhwXvATLwP8IDg7Gvn37EB4eDisrK9FxiIh0Wv369bFmzRpcvHgR7u7uGDt2LGrXrg0/Pz/k5+eXaRYrKyuEhYUhNjYWISEhZfre2o5l4G9SU1MxceJEDB8+HJ07dxYdh4hIbzg7O2PVqlW4dOkSOnbsiPHjx6N27drw9fUt01LQtWtXDBs2DBMmTEBqamqZva+2k9TF2FeSlZUFKysrZGZmokKFCmWRq8ypVCp06tQJ169fR0JCAiwtLUVHIiLSWykpKZg7dy5Wr16NypUrY/LkyfDw8ICZmVmpv3dWVhZcXV1Ru3ZtxMbGQibT39+Li7t+6+9/gTcUFBSEuLg4hIeHswgQEZWyOnXqICoqCpcvX0a3bt0wadIk1KpVC4sXL0Zubm6pvneFChUQHh6OuLg4BAUFlep76QqWAQDXrl3D5MmT4enpiY4dO4qOQ0RkMJycnBAREYErV66gR48emDJlCmrVqoVFixaVaino1KkTRowYgcmTJ+P69eul9j66wuDHBCqVCu7u7rh58yYuXLgACwsL0ZGIiAxWamoq5s2bh6ioKFSsWBETJ06Ep6dnqXw2Z2dno1GjRnBwcEBcXJxejgs4JniFe/fuvfj//v7+OHToECIiIlgEiIgEq1mzJkJDQ5GSkoLevXtj+vTpqFmzJn755RdkZ2dr9L0sLS0RERGBQ4cOwd/fX6Pb1jUGVwb279+PqlWrYujQoYiPj8fUqVMxZswYtG/fXnQ0IiL6L0dHR4SEhODq1av49NNP8eOPP6JmzZr4+eefNVoK3N3dMXr0aEydOhUpKSka266uMbgxwdKlS+Ht7Q2ZTAaZTIZKlSohJSUF5ubmoqMREVER0tPT8csvvyAsLAyWlpbw9vbGmDFjNLIm5ebmolGjRnjnnXdw8OBBGBkZaSCxduCYoAipqamQy+VQKpV4+vQp7ty5A29vb43vfiIiIs1xcHBAYGAgrl27hi+//BKzZ8+Go6MjfvrpJ2RmZr7Vts3NzREZGYmjR4/Cz89PQ4l1i0GWgf+953ZISAhmzJghKBERERWXvb09AgICcO3aNXz99deYO3cuHB0dMXv2bPz1118l3m7btm0xduxYTJs2DVeuXNFcYB1hcGUgOTn5xf9/viuoT58+mDhxoqhIRET0hmrUqIFly5bh2rVr+OabbzBv3jw4OjriP//5T4lLwbx581CjRg0MGjQISqVSs4G1nF6VgdxCBZJuZyI+PQNJtzORW6j4x+Nqtfof55O6uLjg4MGD2Lp1K+zt7cs6LhERvaXq1avDz88P169fx6BBgzB//nw4Ojpi5syZyMjIeKNtmZmZISoqCidPnsSSJUte+pzXrTO6SucPIEy5l401J9MRd+U+0h/n4e/fjATAwcYM7s52+PoDB1S3NIK5uTnKly+PwMBAfPvtt3p5XikRkaG6c+cOFi5ciOXLl8PY2BheXl4YP348bGxsir2NCRMmICAgAPHx8ahfv/4brTN1qmjXFWyLu37rbBm4+TgP06ITcPjqQxjJJChVRX8bzx9v41QJzaVr+KZPN1SsWLEM0xIRUVm6e/cuFi5ciKCgIMjlcowZMwbe3t6wtbV97Wvz8/Ph5uaGKrUa4N3Ppr7xOjOvjyvsbUr/HgvFoddlYP2pdMzcngSFSv3Kv5z/ZSSTIJdJmPWxC75s7lCKCYmISBvcu3cPixYtQmBgIGQy2YtSUKlSpVe+bsmvJxB48gHUMiOdXmf09tRC/7gUTN2agEKF6o3+ggBAqVKjUKHC1K0J8I8z3ItLEBEZiipVqmDhwoVITU2Fp6cn/Pz84OjoiKlTp+LBgwcvfY1/XAr8Tj6CAjKDWWd0qgysP5WORTHJr39iMSyKScaGU+ka2RYREWk3Ozs7zJ8/H6mpqRg9ejT8/f1Rs2ZNTJ48Gffv33/xPENdZ3RmTHDzcR46+RxEoUJV5HOyTm9HRmwIjCs5oNrQwNdu00QuQ+z4dloz2yEiorLx8OFDLFmyBMuWLYNKpYKnpye+Gu6FL1cmvnSdybkQi0e7lv7ja7LyFWBcyQEVPugLM6f3X/o+otcZvRsTTItOgOI1u2tyLuwFADx9mI7C26+/aIRCpca06ASN5CMiIt1RqVIlzJs3D2lpaRg/fjyCg4Pxlc+O164ztt3Hoeo3i1D1m4Ww/Wg0JJkMDzbPRl7KyZc+X1fWGZ0oAyn3snH46sNXzm4K76Tg6f1UlK/dHACQcz7mtdtVqtQ4fPUhrt7npYjJ8Bw6dAi9evVCtWrVIEkSfv31V9GRiMqcra0t5syZg/1nLiHf6t3XHiNgXPldmFSvB5Pq9WHm3AqVP5sJGBkj99Khlz5fV9YZnSgDa06mw0gmvfI5OReeLf7W7QfCpHp95F46BNXTgtdu20gmYfUJ3ZjpEGlSbm4uGjdubPC3biXDsH37dvz+++8oajL+26W/XrvOvIwkLwfJSA5JVvTNjXRhndGJMhB35f4r25rqaSFyLx5CuXfqoFxlR5g36gz1k3zkXT762m0rVWrEJd9/7fOI9E23bt0wZ84c9O3bV3QUolLn6emJ7t27o1mzZti1a9e/SsHr1pkX1CqoVUqolQoosh4iIzYE6qeFMG/QrsiX6MI6Ixcd4HVyChVIf5z3yufkXTkKdWEuLBp1AQCY12+DjH2hyDkfAwvXjq99j/RHecgtVMDcROv/cxARUQk8X/wvXLiAHj16oEmTJpgzZw66deuG3CfK164zz91dOeGfXzAyhk3nEShfq9krX6ft64x2pvqbG49y8bqulnM+BpLcBOb12wIAZOXKw8y5NXITYvH08S0Y21R/5evVANw//gLlcrW7uRG9qVatWmHBggUa2dbkyZNx7NgxjWyLqKw9v6bA8xsQxcfHo0ePHrCzs8O+M1deu848Z9vTG8a2z+5lo8rPQl7ycTyOCYJarUSFZr2KfJ0aQNqjXLhUs3qbb6PUaH0ZePKKUwkB4GnGbRTeTIKZcysAaqgKcgAA5vWelYGcC3tRsf2g175PjXdrwuqpdv4lEZVUtWrVNLqtOnXqaGx7RGXp7Nmz/7h9vSRJUKvVsLe3x5M3uLCQsa09TN75/5+D8rWaQZF5H3/FRcHCxR0yU4siX/u69UwkrS8D5eSvPqzh2emEauRdOYq8K/8+RiA3cT+s237zyoM7AOCn//yotY2NSBuMGzdOdASiEouJiUF+fj7kcjmUSiW+/PJL/Pjjj6hXrx6Sbme+1bbL2TmiIPUsnj6+BZNqzkU/7zXrmUhaXwYcbc0hAS/dhaNWKZGbsA9y63dg223Mvx7Pv3YKWX9EI//6mSIvCAE8u+uUo625xjITEZF2MTExgSRJ+Pzzz1+UgOdetc4Ux5N7qQAAmVnRv1Bq+zqj9WXA3EQOBxsz3HjJwR35189AmfMY1u0HwfTdRv963Ljyu8g68xtyzse8sgw42Jpp7UEdRKUlJycHV69effHn1NRUnDt3DjY2NnBwEH+DFSJN2rx5M8zNzeHs/O/f3F+1zvyvpw9uAKpnxx0o87ORl3wMBWnxKF+3JYytqxb5Om1fZ7Q32d+4O9th1ckb/zrtI+d8DGAkh0Wjzi99nZGZFczqtkTelaNQ5mbAyPzfty02kklwr2tXKrmJtNnp06fh7u7+4s/e3t4AgIEDByIqKkpQKqLS0bRp01c+XtQ687/+fkliycQccqsqqNhhKCyb9ijyNbqwzujEvQlS7mWj89KXX91JE2LHt4WTnWWpbZ+IiLSbvq4zenVvgjpVLNHGqVKJrg71KkYyCW2cKrEIEBEZOENfZ3SiDADAvD6ukGv4L0kukzCvj6tGt0lERLrJkNcZnSkD9jZmmPWxi0a3OftjF96+mIiIABj2OqMzZQAAvmzugIld6mpkW5O6OKNfcx4xTURE/89Q1xmdOJvg70a710ElCxPM3J4EhUpdvBtL/JeRTIJcJmH2xy468xdERERlyxDXGZ04m+Blbj7Ow7ToBBy++hBGMumVf1nPH2/jVAnz+rjqxC4bIiISSx/WmeKu3zpbBp5LuZeNNSfTEZd8H+mP8v5xBSkJzy704F7XDgNaOGj90ZxERKR9dHmdMZgy8He5hQqkPcrFE4UK5eQyONqaa/UVn4iISLfo2jpT3PVbe7+DEjA3kfNmQ0REVGr0dZ3RqbMJiIiISPNYBoiIiAwcywAREZGBYxkgIiIycCwDREREBo5lgIiIyMCxDBARERk4lgEiIiIDxzJARERk4FgGiIiIDBzLABERkYFjGSAiIjJwLANEREQGjmWAiIjIwLEMEBERGTiWASIiIgMnL86T1Go1ACArK6tUwxAREZHmPF+3n6/jRSlWGcjOzgYA2Nvbv2UsIiIiKmvZ2dmwsrIq8nFJ/bq6AEClUuH27duwtLSEJEkaDUhERESlQ61WIzs7G9WqVYNMVvSRAcUqA0RERKS/eAAhERGRgWMZICIiMnAsA0RERAaOZYCIiMjAsQwQEREZOJYBIiIiA8cyQEREZOD+DzCclTsTkSogAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "edges_problematic = [\n",
    "    ('A', 'B', 1),\n",
    "    ('B', 'C', -3),\n",
    "    ('C', 'A', 1),\n",
    "    ('B', 'D', 1),\n",
    "    ('C', 'D', 5),\n",
    "]\n",
    "visualise(*graph_from_edges(edges_problematic), layout=nx.planar_layout)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Design an algorithm (using the hints below) that can find the shortest paths from a single source to all destinations even if negative weights are allowed, and will raise an error if this cannot be done. Verify that this works on your example, and the example given above.\n",
    "\n",
    "You should use the following data structures. The map ``shortest[v]`` stores the current best distance from the start to the vertex ``v``. The map ``predecessor[v]`` gives the previous vertex on the path from the start vertex to ``v`` for the shortest path found so far (assuming such a path has been found).\n",
    "\n",
    "The relaxation operation on an edge $(u, v)$ with weight $w$ should check if the shortest path found so far from the start to $u$ and then from $u$ to $v$ is better than the shortest path found so far from the start to $v$, and if so, update the data structures. This operation is also used in Dijkstra's algorithm.\n",
    "\n",
    "What happens if you relax every edge in the graph?\n",
    "\n",
    "How many times should you do this? Think about the largest number of possible vertices in a shortest weighted path in the graph.\n",
    "\n",
    "How can you detect if there is a problem?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is the complexity of this algorithm?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.11.0 ('dmclass')",
   "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.0"
  },
  "vscode": {
   "interpreter": {
    "hash": "6a49734ee071ffa0c8c241132785defaa79e59e5d82f90ac60edfabf8372010d"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}