miyamoto-yuichiro/dijkstra.ipynb Secret

## dijkstra.ipynb
{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# 単始点最短路問題とダイクストラ（Dijkstra）法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "単始点最短路問題とダイクストラ法（Dijkstra）を紹介する．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "単始点最短路問題の入力と出力は\n",
    "\n",
    "- 入力: 連結単純有向グラフ$G$，枝長さ$l \\colon E(G) \\to \\mathbb{R}_{\\ge 0}$，始点$s \\in V(G)$\n",
    "- 出力: 始点$s$からの最短路長$d \\colon V(G) \\to \\mathbb{R}_{\\ge 0}$\n",
    "\n",
    "である．\n",
    "\n",
    "ここでは簡単のため，最短路長だけを出力し，最短路は出力しないものとする．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "例えば，以下の連結単純有向グラフ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAEACAYAAABVtcpZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAH01JREFUeJzt3Xt8VOW97/HPk0lCkiEzgAgiLWqNPbVabDHaHqGx1a09\n4KVKrC1VNF4KKHX3Ql+2qICilW0lcb8OtdV2F+g+tbZVWq0WrceeYgy7dgs9XLyTvQU56kZCgISZ\nSYaZec4fK0mTyUyuc1/f9+u1Xm1nrTU808ma3/Ndz1rPMtZaRETEnYqy3QAREckeFQERERdTERAR\ncTEVARERF1MREBFxMRUBEREXUxEQEXExFQERERdTERARcTEVARERF1MREBFxMRUBEREXUxEQEXEx\nFQERERdTERARcTEVARERF1MREBFxMRUBEREXUxEQEXExFQERERdTERARcTEVARERF1MREBFxMRUB\nEREXUxEQEXExFQERERdTERARcTEVARERF1MREBFxMRUBEREXUxEQEXExFQERERdTERARcTEVARER\nF1MREBFxMRUBEREXUxEQEXExFQERERdTERARcbHibDdAJJcZYyZ5PJ5rvV7v9OLi4nGRSORQIBDY\nEY1G11tr92e7fSKjZay12W6DSM4xxpzl9/uXhsPh2bW1tXbmzJnllZWVtLe309TUFNqwYYMpLS19\npq2tbZW19uVst1dkpFQEROKUlpYuqqioqF+xYkVZXV1d0fjx4/ttc/DgQdatWxdbuXJlRzAYXBIO\nhx/KQlNFRk1FQKSX0tLSRRMnTqxvbGysqKqqGnT75uZmampqgi0tLSoEkpc0MCzSxRhzVkVFRZ8C\nEA6HufHGGznxxBPx+/3MmDGDZ599tmefqqoqGhsbKyoqKuqNMdXZarvISKkIiHTx+/1LV6xYUdY7\nAUQiEaZNm8aLL77I4cOHufvuu7nyyit55513erapqqpi+fLlZT6fb2k22i0yGjodJIJzFVB5efme\nd999tyzRGEBvZ5xxBnfeeSeXX355z2utra1MnTq1o6OjY5quGpJ8oiQgAng8nmvnzp1rBysA+/bt\nY9euXZx22ml9Xp8wYQK1tbXW4/Fcm852iqSaioAI4PV6p8+aNat8oG0ikQhXX301dXV1fPSjH+23\nfubMmeVer3d62hopkgYqAiJAcXHxuMrKyqTrrbVcffXVjBkzhjVr1iTcprKykuLi4nHpaqNIOuiO\nYREgEokcam9vT7r+hhtuoKWlhY0bN+LxeBJu097eTiQSOZSuNoqkg5KACBAIBN5qbGyMJlq3aNEi\n3njjDX7/+99TWlqa9D02b94cCgQCO9LWSJE00NVB4nrGmDnAz8rKyo5777336D04/M4773DiiSdS\nVlbWkwCMMTz88MPMmzevZztdHST5SqeDxLWMMeOBB4BrAYqKili7di1Llizp2WbatGnEYrFB32vt\n2rWUlJQ0hkIhFQDJK0oC4krGmIuAnwDH937d5/OxdetWhjJlRLfm5mbOPPPMcFtbWwi4B3jAWpvw\n1JJIrtGYgLiKMWa8MWY98DRxBQCIBgKBZ2pqaoLNzc1Der/uuYNCodA3gBnARUCTMeZjqWy3SLqo\nCIhrdPX+X6Hr9E+cV4HPRCKROS0tLUuqq6uDDQ0NsYMHDyZ8r9bWVurr62PV1dU9k8dZa/8TOB/4\nBU4h+I4xJvGlRCI5QqeDpODFn/uPEwXuA1Zaazt77VPt8/mWhsPhOfHPE9i8eXP38wQ2dj1PYEuC\nf/MjwM+AMuA6a+0b6fl0IqOjIiAFLdm5/y6vAnWJfsR77X9s95PFYrHY/KKiov/V9WSxnw92FZAx\npgi4CbgL+Cc0ViA5SEVACtJIev9DeE9rrTUjaItSgeQsjQlIwRnKuX9r7e3DKQCjobECyWVKAlIw\n0tH7j3v/ESWBuPdQKpCcoiQgBSHXev/JKBVIrlESkLyW7t5/3L816iQQ935KBZJ1SgKSt/Kl95+M\nUoHkAiUByTvGGAP8FLghweqU9v7j/t2UJoG491YqkKxQEpC8Y52ey4EEq3K+95+MUoFki4qA5B1j\nzHTgAuBI10tR4F7gzIFu/Mp11tqYtfZB4Gw0B5FkiIqA5A1jTIkxZhnwJ+CHOD3n7eRp7z8ZpQLJ\nJI0JSF7o6v2vAz4AFlhr93a9XmStHXzC/9S0IW1jAgP8mxorkLRSEpCcFtf7fxCY010AwDmFkrXG\nZYBSgaSbkoDkrGS9/yy2J+NJIO7fVyqQlFMSkJwzWO/frZQKJB2UBCSn5Frvv7dsJ4HelAokVZQE\nJCeo9z88SgWSKkoCknW53PvvLZeSQG9dqWAtMAalAhkmJQFJhYnALcAVwAlD3Um9/9ToSgXnMfJU\ncBJwJbAYGJ+GJkoOUxKQ0SgCvgHcAxjgKFAKfAfnRz2pfOn995arSaC3EaSC24BlQBgoBiywBOeR\nnPpxcAEVARmpKuA3wEcBb9y6EPAPwL/F72SMKQG+B/wj8F1gnc2TP8J8KAIwrGcbXwA8AVTEvR4A\ndgDzgD1pbKrkABUBGa7u3v/3cXr9yU47/D+cAhHqfiEfe/+95UsR6DZIKvAB/4FzKi+RCNCJUkHB\n05iADMdJwBbgbqCc5AUA4BicKZ117j9LBhkrWAOMHWD3YpyEVw80AVPT2VbJHhUBGaqPAX8DptP/\n9E8i5cCN69atmw+8BJwDzLDWrs2X0z+FIG5m0ouBpqeffvp6nEH8svjt16xZw7333tv7JW/XvtuA\nE9PeYMk4FQEZqjqcUwh9ev/btm3je9/7Hj/+8Y8JhULx+5RfeOGF6ydNmvQT1PvPqu5UcMIJJzz+\nmc985l/oPw7AK6+8wn333cdzzz3HJZdcwrZt27pXFeN891/OXIslU1QEZKhqiPt7+cEPfsBVV13F\ntGnTePTRR1m1ahWdnX1nc54yZUp43759p6n3n33W2tju3bunT5gwIZxo/YIFC7jnnnvYtGkTs2fP\n5tvf/jbhcM+mpcDnMtVWyRwVARmqVqBnxs729nbef/99HnnkEW6++WYefvhhnnzySVpbW/vsVFRU\nVAbciHM6SLLrAuCKoqKiMfErdu7cyd69e3n99dcBuPnmm3nmmWcoLS3t3iRC4qe5SZ5TEZChugPn\nahEAxo4dy6233sonP/lJwuEwp556KieddBItLS2J9i0Hft31n5IdPuCXJDgNBPCJT3yCHTt2cODA\nAW699VY6Ozt7FwBw7gFZmYF2SoapCMhQbQMeBoIAxhimTJkCQGlpKUePHuXtt9/G6006ZnwMzlVF\nkh31JLga6ODBgz3/ffz48dx8881s374dcL7jLgGcK73eSnsrJeNUBGQ4lgL9uvrRaJTm5mY+9KEP\n8ZGPfIS9e/fy3HPPETcMUA7cDPgz1Fb5u0nA1SS4Guixxx7j/PPPZ9++fQD89a9/5dRTT6WoqOen\nwQJ7ce4LkQKkIiDD0QFcaa3tcxmQx+MhFotx3HHH8eCDD3LeeefxwQcf9O5JditGf3PZUEaSm70W\nLFjA7Nmz+fznP8+8efP4wx/+wAUXXEBJSQkA1toOnHmFIplrrmSUtVaLliEvwPSf/vSn+0KhUMT2\nsm7dOmuMsfPmzbOvv/66TWJftts/ys9us92GES7GWtue7Eux1trm5mb71FNP2ffff9/GYjFrrbXB\nYDDS0NDwDvCxHPgMWtK0aNoIGZLec/4cc8wxt+/fv/92Y8y07vWvvfYaf/7zn1m8eHGytwjinE76\nn+lvbXrk27QRcW7HmSwu4cBwAtZa+6bX6/1RKBRawcBzEEkeUxGQQSWZ8+fTwJ8Z/IqfMM5ppDrg\nd2lsZtrleREAuAp4CGcuoZJBtg3hfMc79byCwqbzs5LUIHP+/JVeVwslEQSew5lxNK8LQIF4BPhv\nOHMBBQbYrvtqoJ2QkucVSA5TEpCEhjjjZxnwBvBh+nYounv/NwKPpbmpGVMASaCbAebjFPb4VBAF\ndgGfIMFgsFJB4VESkD6GOeNnB85dqIe7lk769v4LpgAUGAv8K04qaMT5zjpwvsODwBdIcjWQUkHh\nURKQHqOY778SqAbOwDnVsCU9LcyuAkoC8c4BzgL+L7CVgU8V9VAqKAwqApLXT/vKpAIuAiM2jKeY\nSY5SEXC5fH/aVyapCCTXKxWU4qSCN7PcJBkijQm4lJ72JanUa6zgEZyxgiUaK8gPSgIupN7/yCgJ\nDI1SQX5REnAR9f4lE5QK8ouSgEuo9z96SgLDp1SQ+5QECpx6/5JNA6WCriuLJMuUBAqYev+ppSQw\nOvGpAPhm16pbrbXtWWuYy6kIFCBd958eKgKj1+u+gu/z9wcM7QGut9b+n6w1zMVUBAqMev/poyKQ\nGsaYSuB1YGrcqodQKsg4nZMrEDr3L3lkKolnn12EM3X1eRluj6upCBSArt7/SzhzwMyw1q7V6R/J\nVV1zDH0SeID+j708AfiTMebHXYlB0kxFII+p9y/5ylobtNZ+G6jBmbo6nlJBhqgI5Cn1/qUQWGub\nUCrIKhWBPKPevxQapYLsUhHII+r9SyFTKsgOFYE8oN6/uIVSQeapCOQ49f7FjZQKMkc3i6WZMWaS\nx+O51uv1Ti8uLh4XiUQOBQKBHdFodL21dv8A++mu3xyjm8WywxgzC2e6iVMSrB7wbuORHn9uoiKQ\nJsaYs/x+/9JwODy7trbWzpw5s7yyspL29naamppCGzZsMKWlpc+0tbWtsta+HLev7vrNQSoC2WOM\nqQDuwZlvKNF30Odu49Ecf65jrdWS4qWkpGSR3+8PNDQ0RFtbW20ira2ttr6+Pur3+wMlJSWLuopx\nCbAM2A9cT1eR1pLR5Wxr7T9aa5fFL3fccYdN8PrXrbWfyoF2u2IBZgFv4Zwiil92A+eN9Phz65L1\nBhTaUlJSsmjKlCmBXbt22aHYtWuXnTJlSqC4uPhuYCvwDPDhbH8Oly7zrbUBa23IWhuLX6LRqE3w\neqhrn8tzoP2uWIAKoAGIxRcCY4w97rjjjg73+HNzIch6AwppAc7y+/39CsAPf/hDW11dbceMGWOv\nu+46G2/Xrl3W5/NZYKV6/1lbzrHOj/lIBay1Z+TA53DNkigV+Hw+m6gAvPXWW7asrMzOnz+/37pd\nu3ZZv98fAKqz/ZmysejqoBTy+/1LV6xYUVZVVdXn9alTp7Js2TJuuOGGhPtVVVWxfPnymM/nO812\n/XVLxs3COR03Ugb47ylqiwyBjbuCqKKiguXLlxN//AF8/etf5+yzz074Pl3HX5nP51ua1gbnKBWB\nFDHGTAqHw7Pr6ur6/X962WWXcemllzJhwoSk+1933XVF4XB4jjHm2LQ2VJKZwOiKQGnXe0gG2b/f\nV3BpLBaz119/fb9tfvWrXzF+/HjOP//8pO9TV1fn2uNPRSBFPB7PtXPnzrXjx48f0f4TJkygtrbW\nejyea1PcNMkMXTWURR6P59Ta2tqO+OOvra2NFStW0NDQwEAh283Hn4pAini93umzZs0qH817zJw5\ns9zr9U5PVZskdb761a8mfL2pqSnpaT7JnGTH3/Lly/na177G8ccfP+h7uPX4K852AwpFcXHxuMrK\n0d28WFlZSXFx8bgUNUlSaNOmTezevRtj+nb4x44dy9NPP52lVkm3RMfftm3beP7559m2bduQ3sOt\nx5+KQIpEIpFD7e2jeypee3s7kUjkUIqaJCl04MABLrnkkn5FAGDy5MlZaJH0luj4e+GFF9izZw/T\npk3DWsuRI0eIRqO89tprbNmypd97uPX4UxFIkUAgsKOpqSm0aNGifpE0Go1y9OhRotEokUiEzs5O\niouL8Xg8fbbbvHlzKBAI7MhYo2XIJk+ezM6dO7PdDEkiEAi80tjYGFm0aFHPb9rChQuZN29ezzb3\n338/e/bs4aGHHkr4Hq49/rJ9jWqhLMCk8vLyUKI7FO+8805rjLFFRUU9y1133dVnmwMHDtiysrIQ\ncGy2P4tLl7usc/NXQmvXrk22qluntfY7OfA5XLcAZwA7y8rKbLI7hK11jsNE9wlY6+7jL+sNKKTF\n7/f/tqGhIWpHYPXq1TGfz/dUtj+Di5f51tojg39TSbVbay/Lgc/hmgXnkt7lwFGc+wTs6tWrh/Zt\nxamvr4/6fL4N2f5M2Vg0gVwKdU1atWnLli0ViW5YSaa5uZkzzzwz0tbWdghnwrjfpa+VkkQZ8BxQ\nDQz3Kq8g0AhcivODJGlmjDkDWI9zs1gPn8/H1q1bE94wlkxzczPV1dXBw4cPn2ut7T9YUOB0iWgK\nWWtfDgaDS2pqaoLNzc1D2qe5uZmamppgKBS6BbgMuM8Y86gxZmJaGyvxOoALgceBd4CD8UtraysJ\nXt8D/BIVgIzoesDScmALcQUA4MiRI1tqampCwz3+gsHgEjcWAECng9KxdM9iWF9fn3QWwwMHDtjV\nq1f3m8UQZ3KseuA9QJOS5dDiHC7Zb4dbF2A68DcSzyC6D5hr7eiOPzcuOh2UJsaYap/PtzQcDs+J\nn8988+bN3fOZb+yaz7xfD8QYMxPnmQJbgVustS0Z/xDSh54nkB29HrC0jMRTe/yKuGNktMefm6gI\npJkx5tgkTzb6uR3kyUZdD9K4G5gHLLYaK8gqFYHM63rA0nrgUwlWfwDcZK397QD7j/j4cwsVgTyg\nVJAbVAQyZyS9fxkZDQznAWvtZpxBsPeAHcaYy7PcJJG06er9/xXn+RrxBeADoNZaO08FIDWUBPKM\nUkH2KAmkl3r/2aEkkGeUCqQQqfefPUoCeUypILOUBFJPvf/sUxLIY0oFks/U+88NSgIFQqkg/ZQE\nUkO9/9yiJFAglAokj5wG3Il6/zlBSaAAKRWkh5JAahhjjsOZcO+UXi+r958lSgIFSKlAcpFxXAVs\nB34LvI56/1mnJFDglApSR0lg5Lp6/w8BVUCdtXaLMeZUYL/+JrNLSaDAKRVINsX1/l8FzuyesM1a\n+7oKQPYpCbiIUsHoKAkMT6Lef5abJAkoCbiIUoFkwkC9f8k9SgIupVQwfEoCg1PvP/8oCbiUUoGk\nknr/+UtJQJQKhkhJIDH1/vObkoCkMhV4Af1I5h+D82zr4e2k3n9BUBEQAKy1QWvtEuBLwH3GmEeN\nMROHsGsx8BPgv4A24A3ggvS1VFLsYuA/gXacTsA/M4Tfha7e/++ApcBF1trbrbWd6WyopIeKgPQx\nglTwIHAVMBnn7+mjwBPAvwK+NDZVRmcC8Djwa+BEnO9uCnAjcF+yndT7LzwaE5CkhjBWcAHOD36i\nUwkdwBGcAvFcOtuZKQU0JnApzsPbK4AxCdaHgH8A/q33izr3X5iUBCSpQVKBD/glyc8llwETcU4Z\nKBXkhu7e/6PAeBIXAIBynIRQDur9FzolARmSBKmgHmf8oDzR9tZajOnpNHcAB4EaoDn9rU2PPE8C\npwF/xinGyX78ewsCPzPG3It6/wVNSUCGpHcqmDNnzpuRSOTLJCkAAIcOHer9P8twxgw2pLWRMpCn\ncJJZnwKwfft2FixYwOrVq3nvvfd6r6qIRCILa2pqXkO9/4KmJCDD5QuHw3tKS0vHJVr52muv8fDD\nD9PS0sKBAwe49957mTFjRvfqoziXkR7NVGNTKY+TQCXQinMlV4+77rqLJ554ggULFrBx40ZOP/10\nVq1a1WfHzs7OfWPGjDkJZ5xACpCSgAzXmtLS0oSnE/bu3cvChQs5+eSTWbNmDXPnzmXBggXs2rWr\nexMLTMpYS6XbVBIU3nA4zOOPP85NN93EbbfdxuHDh+ns7HuV55gxYyoZ4GohyX9KAjIcSa8Gikaj\nLFy4kO3bt/Pd736XK664AnAKg9/vx+fzWeDfgc9ktMUplMdJwACvAB9PtPKll17ioosu4lOf+hR+\nv59bbrmFz33uc703SXi1kBQGJQEZqgGvBmpsbOQ3v/kNt9xyC3/5y1+4+OKLOXDgAMcffzw+nw+c\nweEbM9jelDHGWGOM7f7v2W7PCFjgOpKc0ikqKuJHP/oRzz//PLNmzeLJJ5+kra2t9yZ9rhaSwqIi\nIEP1TZzz+Qk98MAD3H///VxzzTWsWrWKiooKOjo68Hg8AAHgn3B6o5Id/45zlU8wfsXZZ5/Nl7/8\nZQDmzZvH1q1bCYX61YvxwNfS3UjJPBUBGaqkl4MCVFdX8+lPfxqA3bt3Y4xhz5494PRC9wL3ZqKR\nMqDbgAEnB3z22Wc55phjuot3b17gynQ1TLKnePBNRAD4G3B6spUf/vCH+cpXvsLs2bPp6OjA6/Vy\nzjnn0NnZGXvhhRe+duGFF0Yy2FZJrONPf/rTwlmzZj09ZsyYnl/5o0eP8vbbb7N48WJKSkpoaGhg\n4sR+00bFAF0iWoA0MCxDdSXOzWJJZ5t86623eOSRR/jCF77AySefzKRJk4K/+MUvtl1zzTUfARZb\na3+bsdamUPw4QD4ODhvnzr2vAg1PPfXU7osuuuh0Y0zPd7l7924aGxu55pprkr1FAOdvYGP6WyuZ\npCIgw/Ft4B6cm78G+yG0wJvAJ4wxnyaPn1eQ70UgwZw/r+B8N9OGsHsMZ1D/m8BP09ZIyRqNCchw\nNADnAP9BggHGOB044wiRuDmIdhpj5qa1lQIMOOdP93cz2A1gAeB14CxUAAqWkoCMRCmwAvgWiVNB\nEOcGo5XxO+bjU8zyMQkMccbPBmAh/U/xxYBOnNT3A0DjOQVMSUBGIgzczt9TQSBu3U6SXA2kVJBe\nw5zx8zac76/33cTdvf9qnO9QBaDAKQnIaJUCN+GkgveBTTj3BBwebMd8SQX5kgRGON//ROB7wLnA\nMcD9OKd+9OPvEioCklVdV6jcjXPlSk5eQZTrRaD3lT/AvwAr9ahHGSoVAckJuZwKcrkI6GlfMloa\nE5CcoLGC4dHTviRVlAQk5+RaKsi1JKDev6SSkoDkHKWCxNT7l3RQEpCclgupIBeSgHr/ki5KApLT\n3J4K1PuXdFMSkLwRnwpwbkybDzxkrY2m8d/NShJQ718yQUlA8kZ8KgAeA34INBljPpbNtqWSev+S\nSUoCkpeMMd8A/rnXS53AMqAh1akgk0lAvX/JNCUByTtdd8heG/fyGJzJzvIyFaj3L9miJCB5qVeP\n+YsJVqc0FaQ7Caj3L9mkJCB5yVr7X8DlwNXAwbjVeZEK1PuXXKAkIHkv3akgHUlAvX/JFUoCkvfy\nKRWo9y+5RklACko6UkGqkoB6/5KLlASkoORiKlDvX3KZkoAUrFSlgtEkAfX+JdcpCUjBymYqUO9f\n8oWSgLjCSFOBMWaSMWZfWVkZHo+HaDRKOBy+NRqNrrfW7h/k31LvX3KeioC4Rq9n8a4BxifY5CXg\nOmvtG8aYs/x+/9JwODz7sssuK6upqaGyspL29naamppCGzZsMKWlpc+0tbWtsta+HPf+etav5A0V\nAXGdwVKBx+P5w9ixY//HihUryurq6orGj+9fLw4ePMi6detiK1eu7AgGg0uOHj36BOr9Sx5SERBX\nSpYKjDFMnjyZF198kaqqqkHfp7m5mc9+9rPhDz74oDMWi61BvX/JMxoYFleyjkeAjwNPdr9eWVnZ\nrwDMnz+fKVOm4Pf7Ofnkk/n+97/fs66qqooXX3yxdOzYsSXA71QAJO9Ya7VocfUCGOCqioqK8OrV\nq228V1991YZCIWuttW+++aadPHmyffbZZ/tsU19fH/X5fBuy/Vm0aBnuoiQgrmettcD/jsViseuv\nv77f+o9//OOUlZV1b0tJSQnHHntsn23q6uqKwuHwHGPMsf3eQCSHqQiIAB6P59ra2tpYokFggMWL\nF+P1ejn99NO5/fbbmTFjRp/1EyZMoLa21no8nvjnHIjkNBUBEcDr9U6fNWtWebL1Dz74IEeOHOH5\n55/njjvu4OWXX+63zcyZM8u9Xu/0tDZUJMVUBESA4uLicZWVlQNuY4zh3HPP5Utf+hKPPvpov/WV\nlZUUFxePS1cbRdJBRUAEiEQih9rb24e6LRUVFf1eb29vJxKJHEp120TSSUVABAgEAjuamppC8a/v\n37+fX//61wQCAWKxGH/84x957LHH+OIX+99ntnnz5lAgENiRkQaLpIhuFhPBmSOovLx8z7vvvlvW\ne3C4paWFK664gh07dmCt5ZRTTmHZsmVccsklffZvbW1l6tSpHR0dHdNskjmFRHJRcbYbIJILrLUf\njBs37pn169d/8Vvf+lZPQp44cSKbNm0adP/169fHSktLN4ZCIRUAyStKAiJduiaN27Rly5aKoUwZ\n0a25uZnq6urg4cOHz7WaM0jyjMYERLpYa18OBoNLampqgs3NzUPap7m5mZqammAwGFyiAiD5SEVA\npJdwOPxQS0vLkurq6mBDQ0Ps4MH4Z9E4Wltbqa+vj1VXVwdbWlqWhMPhhzLcVJGU0OkgkQSMMdU+\nn29pOByeU1tba2fOnFne/TyBzZs3dz9PYGPX8wSUACRvqQiIDMAYc6zH47nW6/VOLy4uHheJRA4F\nAoEd0Wj057oKSAqBioCIiItpTEBExMVUBEREXExFQETExVQERERcTEVARMTFVARERFxMRUBExMVU\nBEREXExFQETExVQERERcTEVARMTFVARERFxMRUBExMVUBEREXExFQETExVQERERcTEVARMTFVARE\nRFxMRUBExMVUBEREXExFQETExVQERERcTEVARMTFVARERFxMRUBExMVUBEREXExFQETExVQERERc\nTEVARMTFVARERFxMRUBExMVUBEREXExFQETExVQERERcTEVARMTFVARERFxMRUBExMVUBEREXExF\nQETExVQERERcTEVARMTFVARERFxMRUBExMVUBEREXExFQETExVQERERcTEVARMTF/j9p5W6meaNR\nlQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10477aa20>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# このコードは描画用である．\n",
    "\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "N4 = nx.DiGraph()\n",
    "N4.add_node(1, position=(0, 0))\n",
    "N4.add_node(2, position=(1, 1))\n",
    "N4.add_node(3, position=(1, -1))\n",
    "N4.add_node(4, position=(2, 0))\n",
    "N4.add_edge(1, 2, length=2)\n",
    "N4.add_edge(1, 3, length=6)\n",
    "N4.add_edge(2, 3, length=1)\n",
    "N4.add_edge(2, 4, length=5)\n",
    "N4.add_edge(3, 4, length=3)\n",
    "posN4 = nx.get_node_attributes(N4, 'position')\n",
    "\n",
    "%matplotlib inline\n",
    "fig, ax = plt.subplots()\n",
    "ax.set_axis_off()\n",
    "nx.draw_networkx(N4, pos=posN4, with_labels=True, node_color='w')\n",
    "edge_label = nx.draw_networkx_edge_labels(N4, pos=posN4, edge_labels=nx.get_edge_attributes(N4, 'length'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "が入力として与えられ，始点は頂点①であるとする．\n",
    "\n",
    "このとき出力は\n",
    "\n",
    "- d(①) = 0,\n",
    "- d(②) = 2,\n",
    "- d(③) = 3,\n",
    "- d(④) = 6,\n",
    "\n",
    "である．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "最短路を図示すると以下の赤い有向グラフ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAEACAYAAABVtcpZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAH7hJREFUeJzt3Xt8VPWd//HXN5OMSYZMABFELGqNVreKt2j7M5S2Wlvx\n0q3ES2mr4KWIuLau9GeLrYBKoa0k7i6Lq3ULtNZ6K22tFlofbquYaKtQBSsqiRVkxYpJgITJZZjk\nu3+cBCaZGXKb25nzfj4e51GZc87kO03OvL+f8/2ec4y1FhER8aa8TDdAREQyRyEgIuJhCgEREQ9T\nCIiIeJhCQETEwxQCIiIephAQEfEwhYCIiIcpBEREPEwhICLiYQoBEREPUwiIiHiYQkBExMMUAiIi\nHqYQEBHxMIWAiIiHKQRERDxMISAi4mEKARERD1MIiIh4mEJARMTDFAIiIh6mEBAR8TCFgIiIhykE\nREQ8TCEgIuJhCgEREQ9TCIiIeJhCQETEwxQCIiIephAQEfEwhYCIiIcpBEREPEwhICLiYQoBEREP\nUwiIiHiYQkBExMMUAiIiHqYQEBHxsPxMN0Akmxljxvp8vhmBQGBSfn7+yEgksjsUCm3q7OxcZa39\nMNPtExkuY63NdBtEso4x5szS0tJ54XB4amVlpa2oqCgqKSmhpaWFmpqattWrVxu/37+2ubl5ibX2\n5Uy3V2SoFAIiffj9/tnFxcVVCxYsKJw5c2beqFGjYrbZtWsXK1eu7LrzzjvbW1tb54bD4fsy0FSR\nYVMIiETx+/2zx4wZU7Vu3brisrKyfrevr69nypQprQ0NDQoCcSUNDIt0M8acWVxc3DsAwmG47jo4\n+mgoLYXTT4ff/37/PmVlZaxbt664uLi4yhhTnpmWiwydQkCkW2lp6bwFCxYU9qoAIhGYOBGefx72\n7IG77oLLL4d3392/SVlZGfPnzy8MBoPzMtBskWHR6SARnFlARUVF2957773CeGMAvZxyCixcCJdc\nsv+lpqYmJkyY0N7e3j5Rs4bETVQJiAA+n2/GtGnTbL8B8MEHUFcHH/94r5dHjx5NZWWl9fl8M1LY\nTJGkUwiIAIFAYNLkyZOLDrpRJAJf+xrMnAnHHx+zuqKioigQCExKURNFUkIhIALk5+ePLCkpSbyB\ntU4AHHIILFsWd5OSkhLy8/NHpqiJIimhK4ZFgEgksrulpSXxBtdeCw0NsGYN+HxxN2lpaSESiexO\nURNFUkKVgAhQsHfv9hefey7+LInZs+HNN+G3vwW/P+F71NbWtoVCoU2paqNIKmh2kHjevcbM/xQs\nmFJYmPf3HTvoNTj87rvONQKFhQcqAGPg/vth+vT9m2l2kLiVTgeJZy0y5uiz4Jk5cCzAhXl5/HTF\nCm6eO/fARhMnQldXv++1YsUKCgoK1rW1tSkAxFVUCYgn3WvMwkvg9vFRp0RfBr4YDPL8hg0M5JYR\nPerr6znjjDPCzc3NbcAi4B5rbWfyWy2SfBoTEE9ZZMzRTxtTPwcWjO/z938a8Lm9e+unTJnSWl9f\nP6D367l3UFtb2zeB04ELgRpjzAlJb7xICigExDPuNWbhtfD257tP/0TbAh3/AVc92Nl5XENDw9zy\n8vLW6urqrl27dsV9r6amJqqqqrrKy8v33zzOWvt34Fzg5zhB8C1jTPypRCJZQqeDJOf1nPuP9+Uf\nAZ6A2tdh6nxr988RNcaUB4PBeeFw+IK+zxOora3teZ7Amu7nCazv+77GmI8CPwEKgauttW+m8jOK\nDJVCQHJavHP/PbZAx1Pw9VusfTDR/saYw3qeLHZhV9eVv8vLe7D7yWI/7W8WkDEmD7gBuAP4ARor\nkCykEJCcNJTef7+MsVhrBtsWVQWSzRQCknOG2/tPaIgh4OyqqkCyk0JAckZKev/RhhECB95CVYFk\nF4WA5ISU9f6jJSEEnLdRVSDZQyEgrpby3n+0JIXAgbdTVSCZpxAQ10pL7z9akkPAeUtVBZJZCgFx\nnYXGmE/CG+fDx/quS3rvP1oKQuDAW6sqkMzQFcPiOguttW0Qc9/+nqt+K62dnPQASDFdbSyZohAQ\n16kypvJjMGlv978jwGqofQQOS+rpnzSz1nZZa5cDZ6F7EEma6HSQuMYdxhSdAE+eC+f8Fla1wLrP\nw3+thVlp+fJP4emg2B+lsQJJD4WAuEKVMZXnw8+aofU5uPA71r4EcIcxvgXp+nJMYwgc+JEaK5DU\nUghIVuvb+38Xrl2YqT/aDISA82NVFUjqKAQkayXq/WdMhkLgwI9XVSDJp4FhyTp3GFP0qDHPzIDH\n/wKP/gHGZjwAsoBmEEkqqBKQrJJ1vf9oGa4EoqkqkGRRJSBZQb3/wVFVIMmiSkAyLqt7/9GyqBKI\n1l0VrAAOQVWBDJJCQJJhDDAdeB94Gdg2kJ2yaubPQGRpCMCwZxAdA5wJHAb8Aoj/YGXJSQoBGY48\n4JvAIsAA+wA/8C1g+cF2dE3vP1oWh0CPIVQFtwG3A2EgH7DAXODH3f8tOU4hIENVBjwGHA8E+qxr\nAz4HvNB3J9f1/qO5IARgUFXBecBvgOI+r4eATTjV3YCqOnEvhYAMVk/v//s4vf5Eg5H/ixMQbT0v\nuLL3H80lIdCjn6ogCLyNcyovngjQgaqCnKfZQTIYxwDrgbuAIhIHAMChwA9BM38ypXsG0TnEn0G0\nDBhxkN3zcSq8KqAGmJDKtkrmKARkoE4A/gpMIvb0TzxFwHXP33bbbZdCw0Q45b/hk9dYe41rTv/k\ngD53Jr0IqHnqqaeuAS7Fucagl2XLlrF48eLolwLd+74KHJ3yBkva6XSQDNQPgP9Pn47Dq6++yiOP\nPMJRRx3FzJkzKSoq6rVT5/bt/OKkk372dnPzTNd/+bvsdFBfxpi8o4466l/Xr19/95gxY2I+x9/+\n9jfOP/98ysrKKCkp4a677uLUU0/tWR0G5tNd3UnuUCUgAzWFPn8vP/rRj/jqV7/KxIkTefjhh1my\nZAkdHR29djJHHNFx5Z49e1wfADnAWtu1devWSaNHjw7HWz9r1iwWLVrEs88+y9SpU7nlllsIh/dv\n6gc+k662SvooBGSgmoCunn+0tLTw/vvv89BDDzFnzhzuv/9+nnjiCZqamnrtlOfzHQJcB5yd3uZK\nHOcBl+bl5R3Sd8Vrr73G9u3beeONNwCYM2cOa9euxe/392wSARrT1lJJG4WADNT3cGaLADBixAhu\nvfVWTj31VMLhMCeeeCLHHHMMDQ0N8fYtAh7t/l/JjCDOhWB9p4MCcPLJJ7Np0yYaGxu59dZb6ejo\niA4AcK4BuTMN7ZQ0UwjIQL0K3A+0AhhjGD9+PAB+v599+/bxzjvvEAgkHDM+FGdWkWRGFXFmA+3a\ndeDi4FGjRjFnzhw2btwIOL/jbiGcsYAtKW+lpJ1CQAZjHhDT1e/s7KS+vp4jjzySj370o2zfvp2n\nn36aPsMARcAcoDRNbZUDxgJfI85soMcff5xzzz2XDz74AIC//OUvnHjiieTl7f9qsMB2nOtCJAcp\nBGQw2oHLrbVt0S/6fD66uro4/PDDWb58Oeeccw47d+6M7kn2yEd/c5lQSIKLvWbNmsXUqVP57Gc/\ny/Tp0/nd737HeeedR0FBAQDW2nbgcpwxAclF1lotWga8LIXKhn//93AkFLLRVq5caY0xdvr06faN\nN96wCXyQ6fYPawGb8TYMbTHW2pZEvxRrra2vr7dPPvmkff/9921XV5e11trW1tZIdXX1u8AJWfAZ\ntKRo0XUCMiDR9/xZM2LEg1c2N3/GGDOxZ/3mzZv505/+xI033pjoLVpxTif9RzramxLuvk7guzg3\ni4s7MByHtda+FQgE7m1ra1uAnm2csxQC0q8E9/z5BPAn+p/xE8Y5jTQT+HVqW5pi7g4BgK8C9+Hc\nS6ign23bcH7Hr+l5BblN52cloX7u+fMXomYLJdAKPI1zx1F3B0BueAj4GM69gEIH2a5nNtBr0O89\niMTlVAlIXAO842ch8CbwEXp3KHp6/9cBj6e+tWni/kqghwGuxHnmQ9+qoBOoA04mzmCwqoLcoxCQ\nXoZwv//jcKqCPJxQ6AT+CFwDfJj6FqdR7oRAjyOAnwH/D+f314FzUdgZwLuJdhrmU8wkyygEZL9h\n3O+/BCgHTsE51bA+ZY3MpNwLgR5n4zxe8hVgAwc/VbSfqoLcoBAQdz/tK51yNwSGTFWB+ykEPM71\nT/tKJ4VAQlFVgR+nKngrw02SAdLsII/S074kmaJmED2EM4NormYQuYMqAQ9S73+IVAkMiKoCd1El\n4CHq/Us6qCpwF1UCHqHefxKoEhg0VQXZT5VAjlPvXzLpYFVB98wiyTBVAjlMvf8kUyUwLH2rAuDm\n7lW3WmtbMtYwj1MI5CDN+08RhcCwRV1X8H0OPGBoG3CNtfaPGWuYhykEcox6/ymkEEgKY0wJ8AYw\noc+q+1BVkHY6J5cjdO5fXGQC8e8+Oxvn1tXnpLk9nqZKIAeo958mqgSSxhhTDCzCGReI9/+pqoI0\nUQi4mM79p5lCIOmMMZNxBouPi7NaYwVpoBBwKfX+M0AhkBKqCjJLIeAy6v1nkEIgpVQVZIZCwEXU\n+88whUDKqSpIP4WAC6j3nyUUAmmjqiB9FAJZTr3/LKIQSCtVBemhEEgxY8xYn883IxAITMrPzx8Z\niUR2h0KhTZ2dnaustQmfwavefxZSCGTEcKqCoR5/XqIQSBFjzJmlpaXzwuHw1MrKSltRUVFUUlJC\nS0sLNTU1batXrzZ+v39tc3PzEmvty9H7qvefpRQCGTPYqmA4x5/nWGu1JHkpKCiYXVpaGqquru5s\namqy8TQ1NdmqqqrO0tLSUEFBwWxrLQuh6BF45kPo+gmsWNAd0lrSupxlrf2Gtfb2mOV737NxXv8X\na+1pWdBuTyzAZGALYOMsW4Fzhnr8eXXJeANybSkoKJg9fvz4UF1dnR2Iuro6O378+NCpPt/9f4PQ\nC/DhEjgr05/Do8uV1tqQtbbNWtsVs3R22jivt3Xvc0kWtN8TC1AMVANdfYPAGGMPP/zwfYM9/rwc\nBBlvQC4twJmlpaWxAdDUZO2XvmRtIGDt0Udb+4tf9FpdV1dnxwWD9pvwhHr/GVvOts6X+VCFrLWn\nZMHn8MwSryoIBoM2bgA8/LC1J57oHINlZdbW1OxfVVdXZ0tLS0NAeaY/U0b+f8x0A3JpKS0t/VV1\ndXWn7evLX3aW1lbnj6+01NrNm3ttsnTp0s5gMLg605/Bw8ut1tpwzO9u4FqttZ7tTWZqia4KiouL\n7dKlS2N/M08/7XS+XnrJ+feOHc4SpaqqyrPHnwaGk8QYM7aoqGjbe++9Vzhq1KgDK1pbYdQo2LwZ\njj3WeW3GDJgwARYv3r9ZU1MTEyZMaG9vb59oNWshE34AfHsY+3cC84HF/W0oyWeMuaiwsPC3O3bs\nML2OP4CKCrjuOrj66oT7e/n4062kk8Tn882YNm2ajfkD3LIFCgoOBADAKafA66/32mz06NFUVlZa\nn883Iw3NleTTrKEM8vl8J1ZWVrbHHH9dXbB+PezcCccdBxMnwk03QUdHr828fPwpBJIkEAhMmjx5\nclHMir17IRjs/VowCC2x17dUVFQUBQKBSalqowzdV77ylbiv19TUcO2116a5NdJXwuPvgw9g3z5Y\nvRpqa+HVV+GVV2DRophNvXr85We6AbkiPz9/ZElJSeyKESOgubn3a3v2QJxtS0pKyM/PH5miJsow\nPPvss2zduhVjenf4R4wYwVNPPZWhVkmPhMdfUXcufOMbMHas89+33ALf/z7cdVevTb16/CkEkiQS\niexuidO75/jjIRKBt98+cEpo40b4+MdjNm1paSESiexOcVNlCBobG7n44otjQgBg3LhxGWiRREt4\n/I0cCUce2fu1OL9D8O7xpxBIklAotKmmpqZt9uzZvUvS4mKYNg3mz4cHHoC//hWefBJeeCHmPWpr\na9tCodCmdLVZBm7cuHG89tprmW6GJNARCr3xwnPPdc2ePTv2FPfVV8OyZfCFL0B+PtxzD1x8ccxm\nnj3+Mj09KVcWYGxRUVFb3CsUo68TOOooax95JGaTxsZGW1hY2AYclunP4tHlDutc/BXXihUrEq3q\n0WGt/VYWfA7PLUvhsnXQOrKw0MY9/vbts3bOHGtHjrR2/Hhrb77Z2o6OXpt4+fjTwHCSWGt3+v3+\ntatWreqKWTlqFPz6184g8datcMUVMZusXLnS+v3+Z6zHpqdlkXriP/wcgKsPMr2wW7j7PSRN7jCm\n6DFj/ucb8NinoOjCvDx+umJF7Ib5+bB8OezaBTt2OJWA399rk1WrVnX5/f41njz+Mp1CubSQ6Irh\nftTV1dlgMLgP+BDQ7QcysxRaa9dZ56KvwQpZa9daawuy4HN4YlkKl22GVgu2Z3kJ7OGJrhg+CF0x\nnAWNyKVlqPcOKigomA1U4FwG/zAwJtOfxYNLobX2Z9babdbappilsdHGeX2rtfYBqwBIy7IQih6F\n/wlHfflHL/+Sl9c4fvz4Vt07aOBLxhuQi0vPXQyrqqoS3sWwsbHRLl26NOYuhjiXwVcBO1QVZNkC\nNuNt8PCyFCpf79P771k+gM7/gh9aO7zjz4uLbhuRIsaY8mAwOC8cDl/Q937mtbW1PfczX9N9P/P1\ncfavAFYCG4CbrLUNaf8Q0pueJ5ARPQ9YugTO9cdZ/0d490U477vWbul5bbjHn5coBFLMGHNYgicb\n/dT2MwjV/SCNu4DpwI3W2l+npdESn0Ig7aqMqZwKD/4TxFwNvBO6fgVLZ1ub8J5Pwzn+vEIh4AKq\nCrKEQiBthtL7l6HRFFEXsNbWAqfijBNsMsZckuEmiaRMlTGVl0HjFXECYCd03Qc/OsfaoxQAyaFK\nwGVUFWSQKoGUUu8/M1QJuIyqAslF6v1njioBF1NVkGaqBJJOvf/MUyXgYqoKxM3U+88OqgRyhKqC\nNFAlkBTq/WcXVQI5QlWBuMUI+OKl6v1nDYVADrHOzc/mApcBPzTGPGyMGZPpdolE64DN22Bf9Gt/\nhHcfgBMPduGXpIZCIAepKpBstNAY89/GLL8OXn0FNtRDWL3/zNOYQI7TWEESaUxgyBYbc/Kn4Olx\nMOop+Pot1j54tzEXhqFOX/6ZpRDwAN2DKEkUAoO20BhzJPznF2H28/Di6zB1vrVxHgYsmaIQ8BBV\nBcOkEBiUeL3/TLdJYmlMwEM0ViDpEH3ufye8/QgcpgDIXqoEPEpVwRCoEuiXev/uo0rAo1QVSDKp\n9+9eqgREVcFAqRKIS71/d1MlIMmsCgKAviTdx+A823pQ1PvPDQoBAYZ1tXE+8GPgH0Az8CZwXupa\nKkl2EfB3oAWnE/BvDOB7YbExJ58LO6bAtT+HmZXWTtbUT3dSCEgvQ6gKlgNfBcbh/D0dD/wG+BkQ\nTGFTZXhGA78EHgWOxvndjQeuA36YaCf1/nOPxgQkoQGMFZyH84Uf71RCO7AXJyCeTmU70yZ3xgS+\nCKzC+b0dEmd9G/A54IXoF3XuPzepEpCE+qkKgsAvSHwuuRAYA/waVQXZoqf3/zAwivgBAFCEUyEU\ngXr/uU6VgAxInKqgCmf8oCje9tZajNnfaW4HdgFTgPrUtzZF3F0JfBz4E04YJ/ryj9YK/GSxMQ+o\n95/bVAnIgERXBRdccMFbkUjkChIEAMDu3buj/1mIM2awOqWNlIN5Eqcy6xUAGzduZNasWSxdupQd\nO3ZEryruDIdvuOHss9X7z3GqBGSwguFweJvf7x8Zb+XmzZu5//77aWhooLGxkcWLF3P66af3rN6H\nM410X7x9s557K4ESoAlnJtd+d9xxB7/5zW+YNWsWa9as4aSTTmLJkiW9dgzv3dvkHzHiSJxxAslB\nqgRksJb5/f64pxO2b9/O9ddfz7HHHsuyZcuYNm0as2bNoq6urmcTC4xNW0ulxwTiBG84HOaXv/wl\nN9xwA7fddht79uyho6Oj1zb+ESMKOchsIXE/VQIyGAlnA3V2dnL99dezceNGvv3tb3PppZcCTjCU\nlpYSDAYt8BLwybS2OJncWwkY4G/AP8Vb+ec//5kLL7yQ0047jdLSUm666SY+85nPRG8Sd7aQ5AZV\nAjJQB50NtG7dOh577DFuuukmXnzxRS666CIaGxs54ogjCAaD4AwOX5fG9iaPMRZj7P7/dh8LXE2C\nUzp5eXnce++9PPPMM0yePJknnniC5ubm6E16zRaS3KIQkIG6Ged8flz33HMPd999N1dddRVLliyh\nuLiY9vZ2fD4fQAj4AU5vVDLjJeA+nFk/vZx11llcccUVAEyfPp0NGzbQ1haTF6OAr6e6kZJ+CgEZ\nqITTQQHKy8v5xCc+AcDWrVsxxrBt2zZweqHbgcXpaKQc1G3AQW8O+Pvf/55DDz20J7yjBYDLU9Uw\nyZz8/jcRAeCvwEmJVn7kIx/hy1/+MlOnTqW9vZ1AIMDZZ59NR0dH13PPPff1z3/+85E0tlXia3/l\nxz/+zqQrr3zIV1S0f2xj3759vPPOO9x4440UFBRQXV3NmDExt43qAtantbWSFhoYloG6HOdisYR3\nm9yyZQsPPfQQX/jCFzj22GMZO3Zs689//vNXr7rqqo/iPNv4V2lrbTL1HQdw4eBw9LN+W3/yk38c\ndfXVI7ufPQ041du6deu46qqrEr1FCOdvYE062ivpoxCQwbgFWIRz8Vd/X4QWeAs42RjzCdz8vAKX\nh0Cce/48jvO7mTiA3btwBvVvBh5IZTslMzQmIINRDZwNvE2cAcY+2nHGESJ97kH0mjFmWkpbKcBB\n7/nT87vp7wKwEPAGcCYKgJylSkCGwg8sAP6V+FVBK84FRnf23dGVTzFzYSUwwDt+VgPXE3uKrwvo\nwKn6fgRoPCeHKQRkOE4FHse5D33P9NEw8AowmQRfHt3nou8CvoIbxgpcFALR5/6fhxdfh6kHedhL\nIc7U0ROAgu7XQsBWnPP/m1PeYMk4hYAMlx+4AacqeB94FueagD397eiaqsAlITDE+/2PAb4DfBo4\nFLgb59SPev8eoRCQjHJFVZDlITDI3r9ILwoByQpZXRVkcQjoaV8yXJodJFlBM4gGR0/7kmRRJSBZ\nJ+uqgiyrBNT7l2RSJSBZR1VBfOr9SyqoEpCslhVVQRZUAur9S6qoEpCs5vWqQL1/STVVAuIafasC\nnAvTrgTus9Z2pvAHZ6QSUO9f0kGVgLhG36oA52rl/wRqjDEnZLJtyaTev6STKgFxJWPMN4F/i3qp\nA7gdqE56VZDGSkC9f0k3hYC4jjHG4JwSOi3O6j8DV1tr30ziD0x5COiqX8kUhYC4kjHmcJxn5v5z\nnNXJrQpSHALq/UsmKQTEtborgq8Ay3AehN5XcqqCFIWAev+SDRQC4noprwpSEALq/Uu2UAhITkhp\nVZDEEFDvX7KNQkBySkqqgiSFgHr/ko0UApJzkl4VDDME1PuXbKYQkJyVtKpgGCGg3r9kO4WA5LSk\nVAVDCAH1/sUtFALiCUOtCowxY+825oMthYXs9fkY0dnJinD41s7OzlXW2g/j/Sz1/sVNFALiGYOp\nCowxZ5aWls4Lh8NTp3/pS4VnTplCSUkJLS0t1NTUtK1evdr4/f61zc3NS6y1L4N6/+JOCgHxnP6q\nAp/P97sRI0acv2DBgsKZM2fmjRoVmxe7du1i5cqVXXfeeWd7a2vr3IX79tWq9y9upBAQT0pUFRhj\nGDduHM8//zxlZWX9vk99fT2f/dSnIt/cudN3TFfXC+r9i9soBMTT+lYFwWCQDRs29A6AK6+EZ56B\n1lYYMwauuQa++939q+vr6znzjDPCu5ubK6y169P8EUSGRc8TEE+z1v4DuAT4WnFx8b758+fHVgDz\n5sE778CePbB2LSxbBn/4w/7VZWVl3L5gQX4wGJyX1saLJIEqARGcWUCFhYXv7tix45B4YwD7vfUW\nfO5z8MQTcPrp+19uampiwoQJ7e3t7RMTzRoSyUaqBEQAn883o7KysithANx4IwQCcNJJzqmgqAAA\nGD16NJWVldbn881IQ3NFkkYhIAIEAoFJkydPLkq4wfLlsHevMzbwve/Byy/HbFJRUVEUCAQmpbKd\nIsmmEBAB8vPzR5aUlBx8I2Pg05+Gyy6Dhx+OWV1SUkJ+fv7IFDVRJCUUAiJAJBLZ3dIywJmdkQgU\nF8e83NLSQiQS2Z3kpomklEJABAiFQptqamraYlZ8+CE8+iiEQtDV5cwKevxx+OfY68xqa2vbQqHQ\npnS0VyRZNDtIBGd2UFFR0bb33nuvsNfgcEMDXHopbNoE1sJxx8Htt8PFF/faX7ODxK1UCYgA1tqd\nfr9/7apVq7p6rRgzBp59FpqaYNcueOmlmAAAWLVqVZff71+jABC3USUg0q37pnHPrl+/vnggt4zo\nUV9fT3l5eeuePXs+rSuGxW1UCYh0s9a+3NraOnfKlCmt9fX1A9qnvr6eKVOmtLa2ts5VAIgbKQRE\nooTD4fsaGhrmlpeXt1ZXV3ft2rUr7nZNTU1UVVV1lZeXtzY0NMwNh8P3pbmpIkmh00EicRhjyoPB\n4LxwOHxBZWWlraioKOp5nkBtbW3P8wTWdD9PQBWAuJZCQOQgjDGH+Xy+GYFAYFJ+fv7ISCSyOxQK\nbers7PypBoElFygEREQ8TGMCIiIephAQEfEwhYCIiIcpBEREPEwhICLiYQoBEREPUwiIiHiYQkBE\nxMMUAiIiHqYQEBHxMIWAiIiHKQRERDxMISAi4mEKARERD1MIiIh4mEJARMTDFAIiIh6mEBAR8TCF\ngIiIhykEREQ8TCEgIuJhCgEREQ9TCIiIeJhCQETEwxQCIiIephAQEfEwhYCIiIcpBEREPEwhICLi\nYQoBEREPUwiIiHiYQkBExMMUAiIiHqYQEBHxMIWAiIiHKQRERDxMISAi4mEKARERD1MIiIh4mEJA\nRMTDFAIiIh6mEBAR8TCFgIiIhykEREQ8TCEgIuJhCgEREQ9TCIiIeNj/AdU5jvkcHINCAAAAAElF\nTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x109fe7198>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# このコードは描画用である．\n",
    "\n",
    "shortest_distance_of_N4 = nx.single_source_dijkstra_path_length(N4, 1, weight='length')\n",
    "\n",
    "def draw_shortest_paths(G, d, node_label=False, edge_label=False, edge_arrows=True, node_size=300):\n",
    "    p = nx.get_node_attributes(G, 'position')\n",
    "    nx.draw_networkx(G, pos=p, arrows=edge_arrows, with_labels=False, node_color='w', node_size=node_size)\n",
    "    edge_list = {}\n",
    "    for n in d:\n",
    "        dist = d[n]\n",
    "        for pred in G.predecessors_iter(n):\n",
    "            if dist - G.edge[pred][n]['length'] == d[pred]:\n",
    "                edge_list[(pred, n)] = True\n",
    "    nx.draw_networkx_edges(G, pos=p, edgelist=edge_list.keys(), edge_color='r')\n",
    "    if edge_label:\n",
    "        nx.draw_networkx_edge_labels(G, pos=p, edge_labels=nx.get_edge_attributes(G, 'length'))\n",
    "    if node_label:\n",
    "        nx.draw_networkx_labels(G, pos=p, labels=d, font_color='r')\n",
    "    return\n",
    "\n",
    "%matplotlib inline\n",
    "fig, ax = plt.subplots()\n",
    "ax.set_axis_off()\n",
    "draw_shortest_paths(N4, shortest_distance_of_N4, node_label=True, edge_label=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "となる．\n",
    "ここで頂点の赤い数字は，頂点の名前ではなく，頂点への最短路長である．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## ダイクストラ法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "枝長さが非負の単始点最短路問題を効率的に解く方法として，ダイクストラ法が知られている．\n",
    "ここでは，ダイクストラ法のコード例を示す．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "まず，ダイクストラ法を記述する前に，枝長さ付きの有向グラフを辞書を用いて保存する．\n",
    "\n",
    "例えば，前出の有向グラフ（と枝長さ）ならば，以下の辞書"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "V = ['1', '2', '3', '4'] # 有向グラフの頂点集合をVとする．\n",
    "\n",
    "E = [('1', '2'), ('1', '3'), ('2', '3'), ('2', '4'), ('3', '4')] # 有向グラフの枝集合をEとする．\n",
    "\n",
    "length = { # それぞれの枝の長さも辞書で保存する．  \n",
    "    ('1', '2'): 2, # ①から②への有向枝の長さは2である．\n",
    "    ('1', '3'): 6,\n",
    "    ('2', '3'): 1,\n",
    "    ('2', '4'): 5,\n",
    "    ('3', '4'): 3,\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "ダイクストラ法を以下に関数dijkstraとして定義する．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def dijkstra(V, # 有向グラフの頂点集合\n",
    "             E, # 有向枝集合\n",
    "             length, # 枝長さ\n",
    "             source, # 始点\n",
    "            ):\n",
    "    '''\n",
    "    ネットワーク上の単始点最短路問題を動的計画法（Dijkstra法）で解く関数である．\n",
    "    説明のスライドをそのままPythonでコーディングしただけである．\n",
    "    ただし，このコーディングはわかりやすさ再優先なので，特にStep 4-1の計算の効率は悪い．\n",
    "    '''\n",
    "    \n",
    "    '''\n",
    "    前準備として，頂点が与えられたらその頂点から出ている枝の先の頂点のリストを引ける辞書successorを作る．\n",
    "    '''\n",
    "    successor = {v: [] for v in V}\n",
    "    for tail, head in E:\n",
    "        successor[tail] += head\n",
    "\n",
    "    '''\n",
    "    スライドのStep 1に該当する．\n",
    "    '''\n",
    "    distance = {} # 最短路長distanceは辞書で出力することにする．\n",
    "    upper_bound_of_shortest_path_length = sum(length.values())\n",
    "    # スライドの∞の代わりに，最短路長の自明な上界として「枝長さの合計」を使うことにする．\n",
    "    for v in V:\n",
    "        distance[v] = upper_bound_of_shortest_path_length\n",
    "\n",
    "    '''\n",
    "    スライドのStep 2に該当する．\n",
    "    '''\n",
    "    distance[source] = 0 # 始点そのものへの最短路長は0である．\n",
    "\n",
    "    '''\n",
    "    スライドのStep 3に該当する．\n",
    "    '''\n",
    "    U = V[:] # 集合（リスト）Uに頂点集合をコピーする．\n",
    "\n",
    "    '''\n",
    "    スライドのStep 4に該当する．\n",
    "    '''\n",
    "    while len(U) > 0:\n",
    "        '''\n",
    "        スライドのStep 4-1に該当する．\n",
    "        '''\n",
    "        minimum_of_d = upper_bound_of_shortest_path_length\n",
    "        v = U[0]\n",
    "        for u in U:\n",
    "            if distance[u] < minimum_of_d:\n",
    "                v = u\n",
    "                minimum_of_d = distance[v]\n",
    "        '''\n",
    "        スライドのStep 4-2に該当する．\n",
    "        '''\n",
    "        U.remove(v)\n",
    "        '''\n",
    "        スライドのStep 4-3に該当する．\n",
    "        '''\n",
    "        for w in successor[v]:\n",
    "            if distance[w] > distance[v] + length[(v, w)]:\n",
    "                distance[w] = distance[v] + length[(v, w)]\n",
    "\n",
    "    '''\n",
    "    スライドのStep 5に該当する．\n",
    "    '''\n",
    "    return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "shortest_distance = dijkstra(V, E, length, '1') # 始点を①として最短路長をダイクストラ法で求める．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': 0, '2': 2, '3': 3, '4': 6}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shortest_distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最短路長がわかっているならば，最短経路，より正確には最短路を構成する枝を見つけるのも容易である．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def shortest_path_edges(V, E, length, source, distance):\n",
    "    '''\n",
    "    前準備として，頂点が与えられたらその頂点に入ってくる枝の元の頂点のリストを引ける辞書predecessorを作る．\n",
    "    '''\n",
    "    predecessor = {v: [] for v in V}\n",
    "    for tail, head in E:\n",
    "        predecessor[head] += [tail]\n",
    "    \n",
    "    '''\n",
    "    distance(pred) + length[(pred, v)] = distance(v)\n",
    "    となっている頂点対(pred, v)があったら，\n",
    "    それは最短路で使われているはずである．\n",
    "    '''\n",
    "    edges = [] # 最短路で使われている枝を保存するリスト\n",
    "    for v in V: # それぞれの頂点に関して以下を行う．\n",
    "        if v == source: # vが始点ならば\n",
    "            continue # なにもしない．\n",
    "        for pred in predecessor[v]: # vに入ってくる枝（の元）それぞれに関して，\n",
    "            if length[(pred, v)] == distance[v] - distance[pred]:\n",
    "                # もしも最適性条件を満たしているならば，\n",
    "                edges += [(pred, v)] # それは最短路で使われているはずである．\n",
    "                break\n",
    "    return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('1', '2'), ('2', '3'), ('3', '4')]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shortest_path_edges(V, E, length, '1', shortest_distance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Networkxの利用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "単始点最短路問題を含む，グラフ上の最適化問題は多くの場面で有用である．\n",
    "よって，グラフを入力とするアルゴリズムを実装したパッケージが広く流通している．\n",
    "\n",
    "ここでは，そのようなパッケージの1つである[networkx](http://networkx.github.io/)を利用してみる．\n",
    "（すでに上記の描画で利用しているが．）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import networkx as nx # モジュールnetworkxをnxという略称でimportする．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "G = nx.DiGraph() # これでGという名前の（中身は何もない）有向グラフが作られる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "G.add_edge('1', '2', edge_length=2) \n",
    "# これで有向グラフGに「'1'から'2'への有向枝」が「edge_lengthという属性の値が2」というおまけ付きで加えられる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "G.add_edge('1', '3', edge_length=6) \n",
    "G.add_edge('2', '3', edge_length=1) \n",
    "G.add_edge('2', '4', edge_length=5)\n",
    "G.add_edge('3', '4', edge_length=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': 0, '2': 2, '3': 3, '4': 6}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.single_source_dijkstra_path_length(G, '1', weight='edge_length')\n",
    "# networkxのメソッドsingle_source_dijkstra_path_lengthは，「グラフG，始点'1'，長さの属性edge_length」を引数として，最短路長を返す．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## 計算時間の比較"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "あまりおもしろい例ではないが，以下のようなグリッドグラフに枝重みをランダムに設定し，ダイクストラ法の計算時間を測ってみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA6EAAAHfCAYAAACh7N6yAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3WGMZf1dH/bvzxkgeyHLi6RKUiwcUOQijbrOPrZhGpMw\nOzMkhKgmVVOV3UaR8oI3SWWUpJU37gvvrtQSJru0VO2LohJTIxMiWyAINFGY2Rki021ieLCvGdsY\nBQGGgEUUYtdlVRj23xc7zz6e55ndmdm593//O/P5SEe79+6Z8//P+c6Zs985Z+6t1loAAACghzcs\negIAAABcHEooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDdKKAAAAN3MpIRW1d+rqr2qmlbVB6rqS2ex\nXQAAAM6XM5fQqnpTku9IcrW1diXJUpJvP+t2AQAAOH+WZrCNzyf5vSRfXlWPkkyS/JsZbBcAAIBz\n5sxXQltrv5PkXpJfS/IbSf59a23rrNsFAADg/KnW2tk2UPW1SX4iyTcm+VySDyX5YGvth16z3tkG\nAgAAYGittTpunVm8MNHbkvxMa+3ftdb+IMmPJPmzT5mQZYDlve9978LnYJHFiIs8xllkMc4ii3EW\nWYyzyGKsRR7jLCc1ixL6i0lWquoPV1UlWU/yyRlsFwAAgHNmFr8T+rEk70/yc0k+lqSSfN9ZtwsA\nAMD5M4tXx01r7R8k+Qez2Bbzt7q6uugpcEAWY5HHOGQxDlmMQxbjkMVY5PHiOfMLE514oKrWaywA\nAAD6qqq0Ti9MBAAAACeihAIAANCNEgoAAEA3SigAAADdKKEAAAB0o4QCAADQjRIKAABAN0ooAAAA\n3SihAAAAdKOEAgAA0I0SCgAAQDdKKAAAAN0ooQAAAHSjhAIAANCNEgoAAEA3SigAAADdKKEAAAB0\no4QCAADQjRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDdKKAAAAN0ooQAAAHSjhAIAANCN\nEgoAAEA3SigAAADdKKEAAAB0o4QCAADQjRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDdK\nKAAAAN0ooQAAAHSjhAIAANCNEgoAAEA3SigAAADdnLmEVtWbq+rnq+rlgz8/V1XvmsXkAAAAOF/O\nXEJba59urV1trb2U5K1J/t8kP3rmmTFz0+k0N27cyFve8pbcuHEj0+l00VO6sGQxFnmMQxbjkMU4\nZDEOWYxFHi+uWd+Ou5HkX7fWPjPj7XJG0+k06+vrefvb354f+IEfyEsvvZSVlZVU1VyW82Je+2dl\nZSVvfetbZXEK89o/PfM4L85DFuclD1mMQxZjkcU4eh0bb3/727O+vq6IvihaazNbknx/kr/5lH9r\nLM7169fb93zP9xx6bnNzs00mk5Zk5st5MY99M5lM2t27dw+NI4vjzWPf9M7jvDgPWZyXPGQxDlmM\nRRbj6Hls3Lt3r924cWNBnymttVe+do/tjTO7ElpVX5LknUk++LR1bt269WTZ3d2d1dCcwN7eXlZX\nVw89t7GxkaWlpbmMN8+fevVc5mFpaSlra2uHnpPF4n4i3DOPRe9DWRy26P0oi1ctej/K4lWL3o8j\n5yGLcbJIjs7j2rVr2dvbm9uYvN7u7u6hjndSszxq/lKSn2ut/fbTVjjNxJit5eXl3L9/P1evXn3y\n3NbWVvb39+cy3uMfhLz45vHNc39/XxbPYV4nsp55yOLZHBunJ4txyGIszt/j6Hls7OzsZHl5eS7j\ncbTV1dVDF7pu3759oo+bZQm9nuQfzXB7zNDNmzezsrKSR48eZWNjI1tbW9nc3MyDBw9y5cqVRU9v\nWPM4AUynU1k8h3mdjOVxerIYhyzGIYuxOH+Po/exsb29PZfxmK2axRdGVU2S/GqSr22t/T9PWaed\nl5/ovKiqKpPJJEtLS9nf3/dNc4FkMRZ5jEMW45DFOGQxDlmMRR7jqaq01o69/D2TEnoSSujivfZ2\nCHksjizGIo9xyGIcshiHLMYhi7HIYzwnLaGzfosWAAAAeColFAAAgG6UUAAAALpRQgEAAOhGCQUA\nAKAbJRQAAIBulFAAAAC68T6hF9DB+/csehpEFqORxzhkMQ5ZjEMW45DFWOQxDu8TCgAAwHCUUAAA\nALpRQgEAAOhGCQUAAKAbJRQAAIBulFAAAAC6UUIBAADoRgkFAACgGyUUAACAbpRQAAAAulFCAQAA\n6EYJBQAAoBslFAAAgG6UUAAAALpRQgEAAOhGCQUAAKAbJRQAAIBulFAAAAC6UUIBAADoRgkFAACg\nGyUUAACAbpRQAAAAulFCAQAA6EYJBQAAoJtqrfUZqKr1GoujVdWhx/JYHFmMRR7jkMU4ZDEOWYxD\nFmORx3iqKq21Om49V0IBAADoRgkFAACgGyUUAACAbpRQAAAAulFCAQAA6EYJBQAAoBslFAAAgG5m\nUkKr6iur6oNV9cmq2quqb5jFdgEAADhflma0ne9N8n+21v6LqlpKMpnRdgEAADhHznwltKouJ/lz\nrbX3JUlrbb+19vkzz4y5mEwmuXz5ciaTSabT6aKnc6HJYizyGIcsxiGLcchiHLIYizxeTLO4Evo1\nSf5tVb0vyVuS/GyS72ytPZzBtpmR6XSaS5cu5c6dO1lbW8v29nZWVlby8OF8YmqtzWW7vVXVXLYr\ni9ObVxZJvzxkcTzHxunIYhyyGIvz9zh6Hhvr6+vZ3t7OlStX5jYmM9JaO9OS5K1Jfj/J2w4e/09J\nbh+xXmNxrl+/3u7evXvouc3NzTaZTFqSmS/nxTz2zWQykcVzmMe+6Z3HeXEesjgvechiHLIYiyzG\n0fPYuHfvXrtx48aCPlNaa6987R7bIWfxwkS/nuQzrbWfPXj8oSQvHbXirVu3niy7u7szGJqT2tvb\ny9ra2qHnNjY2srQ0q18LPqyqzsUyD0tLS7IYJIukbx6L3oeyOGzR+1EWr1r0fpTFqxa9H0fOQxbj\nZJEcnce1a9eyt7c3tzF5vd3d3UMd76TOfNS01j5bVZ+pqje31j6dZD3JJ45a9zQTY7aWl5dz//79\nXL169clzW1tb2d/fn8t4zS0kT7W/vy+L5zCvE1nPPGTxbI6N05PFOGQxFufvcfQ8NnZ2drK8vDyX\n8Tja6upqVldXnzy+ffv2iT5uVj+6eVeSD1TVlyT55SR/Y0bbZUZu3ryZlZWVPHr0KBsbG9na2srm\n5mYePHjgvvlnmMcJYDqdyuI5zOtkLI/Tk8U4ZDEOWYzF+XscvY+N7e3tuYzHbFWvn7JUVTsvP9F5\nUVVVJpNJlpaWsr+/75vmAsliLPIYhyzGIYtxyGIcshiLPMZTVWmtHXv5Wwm9QF57O4Q8FkcWY5HH\nOGQxDlmMQxbjkMVY5DGek5bQWbwwEQAAAJyIEgoAAEA3SigAAADdKKEAAAB0o4QCAADQjRIKAABA\nN0ooAAAA3Xif0Avo4P17Fj0NIovRyGMcshiHLMYhi3HIYizyGIf3CQUAAGA4SigAAADdKKEAAAB0\no4QCAADQjRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDdKKAAAAN0ooQAAAHSjhAIAANCN\nEgoAAEA3SigAAADdKKEAAAB0o4QCAADQjRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDdK\nKAAAAN0ooQAAAHSjhAIAANBNtdb6DFTVeo3F0arq0GN5LI4sxiKPcchiHLIYhyzGIYuxyGM8VZXW\nWh23niuhAAAAdKOEAgAA0I0SCgAAQDdKKAAAAN0ooQAAAHSjhAIAANCNEgoAAEA3S7PYSFX9SpLP\nJXmU5Pdba18/i+0CAABwvszqSuijJKuttasK6Ngmk0kuX76cyWSS6XS66OlcaLIYizzGIYtxyGIc\nshiHLMYijxfTTK6EJqm4tXdo0+k0ly5dyp07d7K2tpbt7e2srKzk4cOHcxmvtTaX7fZWVXPZrixO\nb15ZJP3ykMXxHBunI4txyGIszt/j6HlsrK+vZ3t7O1euXJnbmMxIa+3MS5JfTvJyko8k+Y6nrNNY\nnOvXr7e7d+8eem5zc7NNJpOWZObLeTGPfTOZTGTxHOaxb3rncV6chyzOSx6yGIcsxiKLcfQ8Nu7d\nu9du3LixoM+U1torX7vH98eTrHTsRpI/efDnf5Dko0m+8Yh12nvf+94ny87Oztx3Aq+6cuVKe/nl\nlw899/LLL7fLly/P7ZuD5ejl8uXLshhokcc4iyzGWWQxziKLcRZZjLU8LY+3vOUtJ/8PMme2s7Nz\nqOMlJyuhM7kdt7X2mwd//nZV/WiSr0/y4deud+vWrVkMx3NYXl7O/fv3c/Xq1SfPbW1tZX9/fy7j\nNbeQPNX+/r4snsO8bufpmYcsns2xcXqyGIcsxuL8PY6ex8bOzk6Wl5fnMh5HW11dzerq6pPHt2/f\nPtHHnbmEVtUkyRtaa1+oqi9P8heSnGx0url582ZWVlby6NGjbGxsZGtrK5ubm3nw4IH75p9hHieA\n6XQqi+cwr5OxPE5PFuOQxThkMRbn73H0Pja2t7fnMh6zVWf9wqiqr0nyo3l8aXwpyQdaa3//iPXa\nefmJzouqqjKZTLK0tJT9/X3fNBdIFmORxzhkMQ5ZjEMW45DFWOQxnqpKa+3Yy99nLqEnpYQu3mtv\nh5DH4shiLPIYhyzGIYtxyGIcshiLPMZz0hLqbVUAAADoRgkFAACgGyUUAACAbpRQAAAAulFCAQAA\n6EYJBQAAoBslFAAAgG6UUAAAALqpXm/qWlXNG8iO4eBNZBc9DSKL0chjHLIYhyzGIYtxyGIs8hjH\nQRZ13HquhAIAANCNEgoAAEA3SigAAADdKKEAAAB0o4QCAADQjRIKAABAN0ooAAAA3SihAAAAdKOE\nAgAA0I0SCgAAQDdKKAAAAN0ooQAAAHSjhAIAANCNEgoAAEA3SigAAADdKKEAAAB0o4QCAADQjRIK\nAABAN0ooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDdKKAAAAN1Ua63PQFWt11gcraoOPZbH4shiLPIY\nhyzGIYtxyGIcshiLPMZTVWmt1XHruRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDdKKAAA\nAN0ooQAAAHSjhAIAANDNzEpoVb2hql6uqh+f1TYBAAA4X2Z5JfQ7k3xihttjDiaTSS5fvpzJZJLp\ndLro6VxoshiLPMYhi3HIYhyyGIcsxiKPF9PSLDZSVW9M8q1J/vskf2cW22S2ptNpLl26lDt37mRt\nbS3b29tZWVnJw4cP5zJea20u2+2tquayXVmc3ryySPrlIYvjOTZORxbjkMVYnL/H0fPYWF9fz/b2\ndq5cuTK3MZmR1tqZlyQfTPJnknxTkh9/yjqNxbl+/Xq7e/fuoec2NzfbZDJpSWa+nBfz2DeTyUQW\nz2Ee+6Z3HufFecjivOQhi3HIYiyyGEfPY+PevXvtxo0bC/pMaa298rV7bH888+24VfWXk3y2tfbR\nJHWwHOnWrVtPlt3d3bMOzSns7e1lbW3t0HMbGxtZWprJxfDXqapzsczD0tKSLAbJIumbx6L3oSwO\nW/R+lMWrFr0fZfGqRe/HkfOQxThZJEfnce3atezt7c1tTF5vd3f3UMc7qVkcNe9I8s6q+tYkl5L8\nkap6f2vtr792xdNMjNlaXl7O/fv3c/Xq1SfPbW1tZX9/fy7jNbeQPNX+/r4snsO8TmQ985DFszk2\nTk8W45DFWJy/x9Hz2NjZ2cny8vJcxuNoq6urWV1dffL49u3bJ/q4M5fQ1tp7krwnSarqm5L83aMK\nKIt18+bNrKys5NGjR9nY2MjW1lY2Nzfz4MED980/wzxOANPpVBbPYV4nY3mcnizGIYtxyGIszt/j\n6H1sbG9vz2U8Zqtm+YXxRSX0nUf8WzsvP9F5UVVVJpNJlpaWsr+/75vmAsliLPIYhyzGIYtxyGIc\nshiLPMZTVWmtHXv5e6Yl9JkDKaEL99rbIeSxOLIYizzGIYtxyGIcshiHLMYij/GctITO8n1CAQAA\n4JmUUAAAALpRQgEAAOhGCQUAAKAbJRQAAIBulFAAAAC6UUIBAADoxvuEXkAH79+z6GkQWYxGHuOQ\nxThkMQ5ZjEMWY5HHOLxPKAAAAMNRQgEAAOhGCQUAAKAbJRQAAIBulFAAAAC6UUIBAADoRgkFAACg\nGyUUAACAbpRQAAAAulFCAQAA6EYJBQAAoBslFAAAgG6UUAAAALpRQgEAAOhGCQUAAKAbJRQAAIBu\nlFAAAAC6UUIBAADoRgkFAACgGyUUAACAbpRQAAAAulFCAQAA6EYJBQAAoBslFAAAgG6qtdZnoKrW\nayyOVlWHHstjcWQxFnmMQxbjkMU4ZDEOWYxFHuOpqrTW6rj1XAkFAACgGyUUAACAbpRQAAAAulFC\nAQAA6EYJBQAAoBslFAAAgG6UUAAAALpZOusGqurLkvyLJF96sPxYa+09Z90uAAAA58+Zr4S21v6/\nJNdaa1eTXEmyVlXvOPPMmIvJZJLLly9nMplkOp0uejoXmizGIo9xyGIcshiHLMYhi7HI48V05iuh\nSdJa+92Dv35ZHhfb35nFdpmd6XSaS5cu5c6dO1lbW8v29nZWVlby8OHDuYzXWpvLdnurqrlsVxan\nN68skn55yOJ4jo3TkcU4ZDEW5+9x9Dw21tfXs729nStXrsxtTGaktXbmJY+L588n+XySzaes01ic\n69evt7t37x56bnNzs00mk5Zk5st5MY99M5lMZPEc5rFveudxXpyHLM5LHrIYhyzGIotx9Dw27t27\n127cuLGgz5TW2itfu8f2x5m8MFFr7VF7fDvuG5P8+ar6pqPWu3Xr1pNld3d3FkNzQnt7e1lbWzv0\n3MbGRpaWZnIx/HWq6lws87C0tCSLQbJI+uax6H0oi8MWvR9l8apF70dZvGrR+3HkPGQxThbJ0Xlc\nu3Yte3t7cxuT19vd3T3U8U5qpkdNa+3zVfWTSd6W5Kdf+++nmRiztby8nPv37+fq1atPntva2sr+\n/v5cxmtuIXmq/f19WTyHeZ3IeuYhi2dzbJyeLMYhi7E4f4+j57Gxs7OT5eXluYzH0VZXV7O6uvrk\n8e3bt0/0cbN4ddw/luT3W2ufq6pLSb45yclGp5ubN29mZWUljx49ysbGRra2trK5uZkHDx64b/4Z\n5nECmE6nsngO8zoZy+P0ZDEOWYxDFmNx/h5H72Nje3t7LuMxW3XWL4yq+o+T/B9JKo9/N/QHW2t3\nj1ivnZef6LyoqiqTySRLS0vZ39/3TXOBZDEWeYxDFuOQxThkMQ5ZjEUe46mqtNaOvfx95hJ6Ukro\n4r32dgh5LI4sxiKPcchiHLIYhyzGIYuxyGM8Jy2hM3lhIgAAADgJJRQAAIBulFAAAAC6UUIBAADo\nRgkFAACgGyUUAACAbpRQAAAAulFCAQAA6KZ6valrVTVvIDuGgzeRXfQ0iCxGI49xyGIcshiHLMYh\ni7HIYxwHWdRx67kSCgAAQDdKKAAAAN0ooQAAAHSjhAIAANCNEgoAAEA3SigAAADdKKEAAAB0o4QC\nAADQjRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDdKKAAAAN0ooQAAAHSjhAIAANCNEgoA\nAEA3SigAAADdKKEAAAB0o4QCAADQjRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0E211voMVNV6jcXR\nqurQY3ksjizGIo9xyGIcshiHLMYhi7HIYzxVldZaHbeeK6EAAAB0o4QCAADQjRIKAABAN0ooAAAA\n3SihAAAAdKOEAgAA0I0SCgAAQDdnLqFV9caqul9Ve1X18ap61ywmBgAAwPkziyuh+0n+TmttOcl/\nkuRvVdXXzWC7zMFkMsnly5czmUwynU4XPZ0LTRZjkcc4ZDEOWYxDFuOQxVjk8WJaOusGWmu/leS3\nDv7+har6ZJKvSvKps26b2ZlOp7l06VLu3LmTtbW1bG9vZ2VlJQ8fPpzLeK21uWy3t6qay3ZlcXrz\nyiLpl4csjufYOB1ZjEMWY3H+HkfPY2N9fT3b29u5cuXK3MZkRlprM1uS/Kkkv5LkK474t8biXL9+\nvd29e/fQc5ubm20ymbQkM1/Oi3nsm8lkIovnMI990zuP8+I8ZHFe8pDFOGQxFlmMo+exce/evXbj\nxo0Ffaa01l752j22N87shYmq6iuSfCjJd7bWvnDUOrdu3Xqy7O7uzmpoTmBvby9ra2uHntvY2MjS\n0pkvhh+pqs7FMg9LS0uyGCSLpG8ei96Hsjhs0ftRFq9a9H6UxasWvR9HzkMW42SRHJ3HtWvXsre3\nN7cxeb3d3d1DHe+kZnLUVNVSHhfQH2yt/djT1jvNxJit5eXl3L9/P1evXn3y3NbWVvb39+cyXnML\nyVPt7+/L4jnM60TWMw9ZPJtj4/RkMQ5ZjMX5exw9j42dnZ0sLy/PZTyOtrq6mtXV1SePb9++faKP\nm9WPbv5hkk+01r53Rttjxm7evJmVlZU8evQoGxsb2drayubmZh48eOC++WeYxwlgOp3K4jnM62Qs\nj9OTxThkMQ5ZjMX5exy9j43t7e25jMds1Vm/MKrqHUn+RZKP59X7tN/TWvtnr1mvnZef6LyoqiqT\nySRLS0vZ39/3TXOBZDEWeYxDFuOQxThkMQ5ZjEUe46mqtNaOvfx95hJ6Ukro4r32dgh5LI4sxiKP\ncchiHLIYhyzGIYuxyGM8Jy2hM3thIgAAADiOEgoAAEA3SigAAADdKKEAAAB0o4QCAADQjRIKAABA\nN0ooAAAA3Xif0Avo4P17Fj0NIovRyGMcshiHLMYhi3HIYizyGIf3CQUAAGA4SigAAADdKKEAAAB0\no4QCAADQjRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDdKKAAAAN0ooQAAAHSjhAIAANCN\nEgoAAEA3SigAAADdKKEAAAB0o4QCAADQjRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDdK\nKAAAAN0ooQAAAHSjhAIAANBNtdb6DFTVeo3F0arq0GN5LI4sxiKPcchiHLIYhyzGIYuxyGM8VZXW\nWh23niuhAAAAdKOEAgAA0I0SCgAAQDdKKAAAAN0ooQAAAHSjhAIAANCNEgoAAEA3MymhVfX9VfXZ\nqprOYnsAAACcT7O6Evq+JH9xRtsCAADgnJpJCW2tfTjJ78xiW8zXZDLJ5cuXM5lMMp26cL1IshiL\nPMYhi3HIYhyyGIcsxiKPF9PSoidAH9PpNJcuXcqdO3eytraW7e3trKys5OHDh3MZr7U2l+32VlVz\n2a4sTm9eWST98pDF8RwbpyOLcchiLM7f4+h5bKyvr2d7eztXrlyZ25jMSGttJkuSNyWZPuPfG4tz\n/fr1dvfu3UPPbW5utslk0pLMfDkv5rFvJpOJLJ7DPPZN7zzOi/OQxXnJQxbjkMVYZDGOnsfGvXv3\n2o0bNxb0mdJae+Vr99ju2PXVcW/duvVk2d3d7Tn0hbe3t5e1tbVDz21sbGRpaT4Xw6vqXCzzsLS0\nJItBskj65rHofSiLwxa9H2XxqkXvR1m8atH7ceQ8ZDFOFsnReVy7di17e3tzG5PX293dPdTxTmqW\nR00dLE91mokxW8vLy7l//36uXr365Lmtra3s7+/PZbzmFpKn2t/fl8VzmNeJrGcesng2x8bpyWIc\nshiL8/c4eh4bOzs7WV5enst4HG11dTWrq6tPHt++fftEHzeTElpVP5RkNckfrapfS/Le1tr7ZrFt\nZuPmzZtZWVnJo0ePsrGxka2trWxububBgwfum3+GeZwAptOpLJ7DvE7G8jg9WYxDFuOQxVicv8fR\n+9jY3t6ey3jMVvX6KUtVtfPyE50XVVVlMplkaWkp+/v7vmkukCzGIo9xyGIcshiHLMYhi7HIYzxV\nldbasZe/ldAL5LW3Q8hjcWQxFnmMQxbjkMU4ZDEOWYxFHuM5aQnt+sJEAAAAXGxKKAAAAN0ooQAA\nAHSjhAIAANCNEgoAAEA3SigAAADdKKEAAAB0431CL6CD9+9Z9DSILEYjj3HIYhyyGIcsxiGLschj\nHN4nFAAAgOEooQAAAHSjhAIAANCNEgoAAEA3SigAAADdKKEAAAB0o4QCAADQjRIKAABAN0ooAAAA\n3SihAAAAdKOEAgAA0I0SCgAAQDdKKAAAAN0ooQAAAHSjhAIAANCNEgoAAEA3SigAAADdKKEAAAB0\no4QCAADQjRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0I0SCgAAQDfVWuszUFXrNRZHq6pDj+WxOLIY\nizzGIYtxyGIcshiHLMYij/FUVVprddx6roQCAADQjRIKAABAN0ooAAAA3SihAAAAdKOEAgAA0I0S\nCgAAQDdKKAAAAN3MpIRW1bdU1aeq6tNV9e5ZbBMAAIDz58wltKrekOR/SfIXkywnuV5VX3fW7TIf\nk8kkly9fzmQyyXQ6XfR0LjRZjEUe45DFOGQxDlmMQxZjkceLaWkG2/j6JL/UWvvVJKmqH07ybUk+\nNYNtMyPT6TSXLl3KnTt3sra2lu3t7aysrOThw4dzGa+1Npft9lZVc9muLE5vXlkk/fKQxfEcG6cj\ni3HIYizO3+PoeWysr69ne3s7V65cmduYzEhr7UxLkv88yfd90eO/luR/PmK9xuJcv3693b1799Bz\nm5ubbTKZtCQzX86LeeybyWQii+cwj33TO4/z4jxkcV7ykMU4ZDEWWYyj57Fx7969duPGjQV9prTW\nXvnaPbZDdn1holu3bj1Zdnd3ew594e3t7WVtbe3QcxsbG1lamsXF8NerqnOxzMPS0pIsBski6ZvH\novehLA5b9H6UxasWvR9l8apF78eR85DFOFkkR+dx7dq17O3tzW1MXm93d/dQxzupWRw1v5Hkq7/o\n8RsPnnud00yM2VpeXs7u7m6uXr365Lmtra3s7+/PZbzmFpKn2t/fz/3792VxSvM6kfXMQxbP5tg4\nPVmMQxZjcf4eR89jY2dnJ8vLy3MZj6Otrq5mdXX1yePbt2+f6ONmUUI/kuRPV9Wbkvxmkm9Pcn0G\n22WGbt47AZsQAAAHR0lEQVS8mfX19bTWcu3atezs7GRzczMPHjxw3/wzzOMEMJ1Os76+nqqSxSnM\n62Qsj9OTxThkMQ5ZjMX5exw9j43v+q7vyvb29lzGY7ZqFl8YVfUtSb43j19t9/tba3//iHXaefmJ\nzotqOp3mu7/7u7O3t5fl5eW8+93v9k1zQWQxFnmMQxbjkMU4ZDEOWYxFHuOpqrTWjr38PZMSehJK\nKAAAwPl10hLa9YWJAAAAuNiUUAAAALpRQgEAAOhGCQUAAKAbJRQAAIBulFAAAAC6UUIBAADoRgkF\nAACgGyUUAACAbpRQAAAAulFCAQAA6EYJBQAAoBslFAAAgG6UUAAAALpRQgEAAOhGCQUAAKAbJRQA\nAIBulFAAAAC6UUIBAADoRgkFAACgGyUUAACAbpRQAAAAulFCAQAA6EYJBQAAoBslFAAAgG6UUAAA\nALpRQgEAAOhGCQUAAKAbJRQAAIBulFAAAAC6UUIBAADoRgkFAACgGyUUAACAbpRQAAAAulFCAQAA\n6EYJBQAAoBslFAAAgG6UUAAAALpRQgEAAOhGCQUAAKAbJRQAAIBuzlRCq+qvVtUvVNUfVNVLs5oU\n87W7u7voKXBAFmORxzhkMQ5ZjEMW45DFWOTx4jnrldCPJ/nPkvz0DOZCJw7UcchiLPIYhyzGIYtx\nyGIcshiLPF48S2f54NbaLyZJVdVspgMAAMB55ndCAQAA6KZaa89eoeqnkvzxL34qSUvy37XW/snB\nOjtJ/m5r7eVnbOfZAwEAAPBCa60de5fssbfjtta+uddkAAAAON9meTuukgkAAMAznfUtWv5KVX0m\nyUqSn6iqfzqbaQEAAHAeHfs7oQAAADArXV8dt6r+alX9QlX9QVW91HNsHquqb6mqT1XVp6vq3Yue\nz0VVVd9fVZ+tqumi53LRVdUbq+p+Ve1V1cer6l2LntNFVVVfVlX/sqp+/iCP/2HRc7roquoNVfVy\nVf34oudy0VXVr1TVxw6Oj3+16PlcZFX1lVX1war65MH3qm9Y9Jwuoqp688Hx8PLBn59zDl+cqvp7\nB8fDtKo+UFVf+sz1e14Jrar/KMmjJP9bkv/mWa+my+xV1RuSfDrJepJ/k+QjSb69tfaphU7sAqqq\nb0zyhSTvb61dWfR8LrKq+hNJ/kRr7aNV9RVJfi7JtzkuFqOqJq21362qP5TkZ/L4ldd/ZtHzuqiq\n6m8neWuSy621dy56PhdZVf1ykre21n5n0XO56KrqB5L8dGvtfVW1lGTSWvv8gqd1oR38H/fXk3xD\na+0zi57PRVNVb0qyk+TrWmu/V1X/OMlPttbe/7SP6XoltLX2i621X4oXMVqUr0/yS621X22t/X6S\nH07ybQue04XUWvtwEv+RGEBr7bdaax89+PsXknwyyVctdlYXV2vtdw/++mV5fI5ynCxIVb0xybcm\n+d8XPReSPP6/k/d3X7Cqupzkz7XW3pckrbV9BXQIG0n+tQK6MJ9P8ntJvvyVH8zk8QWvp/LN7GL5\nqiRffHD+evxnG56oqj+V5M8k+ZeLncnFdXD7588n+a0ku621Tyx6ThfY/5jkv83j9wZn8VqSn6qq\nj1TVdyx6MhfY1yT5t1X1voPbQL+vqi4telLkv0zyjxY9iYvq4A6Ne0l+LclvJPn3rbWtZ33MzEto\nVf3Uwb3ArywfP/jzP531WACzcnAr7oeSfOfBFVEWoLX2qLV2Nckbk/z5qvqmRc/pIqqqv5zkswd3\nCVTcwTSCd7TWXsrjq9N/6+DXOuhvKclLSf7Xgzx+N8nNxU7pYquqL0nyziQfXPRcLqqq+tokfzvJ\nm5L8h0m+oqpuPOtjlmY9idbaN896m8zMbyT56i96/MaD5+BCO7h15ENJfrC19mOLng9Ja+3zVfWT\nSd6W5KcXPZ8L6B1J3llV35rkUpI/UlXvb6399QXP68Jqrf3mwZ+/XVU/mse/YvPhxc7qQvr1JJ9p\nrf3sweMPJfFCj4v1l5L8XGvttxc9kQvsbUl+prX275Kkqn4kyZ9N8kNP+4BF3o7rp6r9fSTJn66q\nNx28YtW3J/GKh4vj6sI4/mGST7TWvnfRE7nIquqPVdVXHvz9UpJvTvLRxc7qYmqtvae19tWtta/N\n43PFfQV0capqcnC3Rqrqy5P8hSS/sNhZXUyttc8m+UxVvfngqfUkfm1gsa7HrbiL9otJVqrqD1dV\n5fFx8clnfUDvt2j5K1X1mSQrSX6iqv5pz/EvutbaHyT5r5P88yR7SX64tfbMLxDmo6p+KMn/leTN\nVfVrVfU3Fj2ni6qq3pHkv0qy9kUv9f4ti57XBfUnk+wc/E7o/53kx1tr2wueE4zgjyf58BcdG/+k\ntfbPFzyni+xdST5QVR9N8pYk3k5qQapqkscvSvQji57LRdZa+1iS9+fxOwx8LI8vsnzfsz6m61u0\nAAAAcLF5dVwAAAC6UUIBAADoRgkFAACgGyUUAACAbpRQAAAAulFCAQAA6EYJBQAAoJv/H4BdjakP\ncfPQAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x109fe3ba8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "m = 2 ** 3 \n",
    "n = 2 ** 3\n",
    "gmn = nx.grid_2d_graph(m, n).to_directed()\n",
    "for i in range(m):\n",
    "    for j in range(n):\n",
    "        gmn.node[(i, j)]['position'] = (i, j)\n",
    "import random\n",
    "for tail, head in gmn.edges():\n",
    "    gmn.edge[tail][head]['length'] = random.randint(0, 100)\n",
    "    \n",
    "%matplotlib inline\n",
    "plt.figure(figsize=(16, 8))\n",
    "nx.draw_networkx(gmn, pos=nx.get_node_attributes(gmn,'position'), arrows=True, with_labels=False, node_size=32,\n",
    "                 node_color='w', alpha=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "枝長さの表示は省略する．\n",
    "\n",
    "まず，networkxのDiGraph形式のデータを読み込んで，ダイクストラ法を実行する関数を再度定義して実行してみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def argmin(U, d):\n",
    "    minimum_node = U[0]\n",
    "    minimum_distance = d[minimum_node]\n",
    "    for n in U:\n",
    "        if d[n] < minimum_distance:\n",
    "            minimum_distance = d[n]\n",
    "            minimum_node = n\n",
    "    return minimum_node\n",
    "\n",
    "def dijkstra(G, s):\n",
    "    edge_length_sum = sum(nx.get_edge_attributes(G, 'length').values())\n",
    "    d = {}\n",
    "    for n in G.nodes():\n",
    "        d[n] = edge_length_sum # ∞の代わりに枝長さの合計を代入\n",
    "    d[s] = 0\n",
    "    U = G.nodes()\n",
    "    while len(U) > 0:\n",
    "        v = argmin(U, d)\n",
    "        U.remove(v)\n",
    "        for w in G.successors_iter(v):\n",
    "            if d[w] > d[v] + G.edge[v][w]['length']:\n",
    "                d[w] = d[v] + G.edge[v][w]['length']\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 719 µs, sys: 13 µs, total: 732 µs\n",
      "Wall time: 725 µs\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "shortest_distance_of_gmn = dijkstra(gmn, (0, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "次にnetworkxのメソッドで実行時間を測ってみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 258 µs, sys: 0 ns, total: 258 µs\n",
      "Wall time: 260 µs\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "shortest_distance_of_gmn = nx.single_source_dijkstra_path_length(gmn, (0, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Networkxのメソッドの方が早いが，このくらいならば大差ないと思える．\n",
    "\n",
    "次に，グラフの大きさ（頂点数と枝数）を変えて，計算時間をプロットしてみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import time\n",
    "import numpy as np\n",
    "\n",
    "def dijkstra_time(max_size=10):\n",
    "    log = []\n",
    "    for m in range(2, max_size + 1):\n",
    "        n = m\n",
    "        gmn = nx.grid_2d_graph(m, n).to_directed()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                gmn.node[(i, j)]['position'] = (i, j)\n",
    "        for tail, head in gmn.edges():\n",
    "            gmn.edge[tail][head]['length'] = random.randint(0, 100)\n",
    "            \n",
    "        size = len(gmn.nodes())\n",
    "        \n",
    "        start_time = time.time()\n",
    "        dgmn = dijkstra(gmn, (0, 0))\n",
    "        simple_dijkstra_time = time.time() - start_time\n",
    "        \n",
    "        start_time = time.time()\n",
    "        dgmn = nx.single_source_dijkstra_path_length(gmn, (0, 0))\n",
    "        nx_dijkstra_time = time.time() - start_time\n",
    "        \n",
    "        log.append((size, simple_dijkstra_time, nx_dijkstra_time))\n",
    "    return log"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "log = np.array(dijkstra_time(100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA74AAAH4CAYAAABt4DFZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3Xl4VeW9t/H7CZPIIIOKBjTEqFVqHao4D+AxWhxbqxYF\nNVatrQoOtXWoIUmjntqix1e0KrUIFI51wOpxlioIjnXCCRUNIWhSFQEFokIxz/vHDiFAEoOwszLc\nn+vaF3uvvfazfmsbkC/PFGKMSJIkSZLUWmUkXYAkSZIkSelk8JUkSZIktWoGX0mSJElSq2bwlSRJ\nkiS1agZfSZIkSVKrZvCVJEmSJLVqBl9JkhophLBNCGFJCCE0g1ruCCEsCiG88B0/v8a9hBAeCSGc\nWv389BDCzI1ZryRJSTL4SpJalBDCKSGEl0IIS0MI5SGEh0MI+1e/VxBCWFEd6BaFEJ4JIexb672/\n1dFeVQhhu3quVRpCOHTV6xjjhzHG7jHGmK77a4wQwoHAfwGZMcZ963j/9BDCyurvYUkIoSSEMC6E\nsMOqc9a+lxjjkTHG2t/Pet9jQ9+lJElJMvhKklqMEMLFwPXAVcCWwLbAzcCxtU77e4yxO7AF8Cww\npdZ7dYW5REPsd9QfmBdj/LqBc56r/h42Aw4DvgJeCSEMSGNdDX6XIYR2aby2JEn1MvhKklqEEEJ3\noAg4N8b4QIzxqxjjNzHGR2KMl619fozxG2ACsFUIoVdDTddzvYmkgvWD1b2ml4QQsqp7NTOqz5kW\nQigOITxb3QP9QAihdwhhUgjhixDCiyGEbWu1uVMI4YkQwsIQwjshhBMbuN+tq9tbGEKYE0I4q/r4\nz4G/APtV11XQ0PcWU0pjjOcBTwOF1e3UdS8/r6eWP4UQZoQQuoUQckII00MIn4cQPg0h3Fl9ztPV\n3+Ub1XWdGEI4JITwYQjhtyGEfwPjQgg9QggPVn92YfXzzIbuQZKkDWXwlSS1FPsBnYD7G3NyCKET\ncAbwYYxx0fpeLMZ4GjAfOLp6SPDoVW+tderPgGFAJrA98DzwV6An8C5QUF3PpsATwCRgc2AocHMI\nYad6Srir+vpbAScC14QQBsUYxwG/BJ6vrqtoPW7rPuCg2rfZ0Mkh5S/ALkBujHEpUAw8HmPsAfQD\nxgDEGA+p/tgPquu6p/r1VkAPUv+I8AtSf/cYB2xTfexL4Kb1uAdJktabwVeS1FL0Bj6LMVZ9y3k/\nCyEsAsqAPYAfb+B1v20hqztijPOqQ+GjwPsxxmnVdd5TXQPA0UBpjHFidS/s66SC6Dq9viGEfqSC\n/qUxxv9Un3s7cNoG3ksF0FDvd20dgTtJhdZjYozLq4//B8gKIfSNMa6IMT63dvlrvf4GKKi+j+Ux\nxkUxxn9UP68E/hs4BEmS0qh90gVIktRIC4HNQwgZ3xJ+76rurV3bSqBD7QMhhFX/H/zPBtT1Sa3n\nX9Xxumv18yxg3+pQDqmA2A5YZ8EtUr3Hi2KMX9Y6VgbsuQF1AvQFGtv7vT2wK7B3jHFlreO/ITXH\n+l/V93J9jPGOBtpZEGOs+X5DCJ2BG4AjSIXqAHQNIYSkFw2TJLVe9vhKklqK54HlfPce3PmkFoWq\nbTtSobe8ns9szCD2ITA9xtir+tGzekjweXWcWwH0CiF0qXVs2wbqbKyfAI3dpmg2qaHij4UQdlx1\nMMb4aYzxFzHGvqSGXP/5W1ZyXvs7/DWwAzCwerj0wdXHE98iSpLUehl8JUktQoxxCan5sjeHEI4L\nIXQOIbQPIQwJIfyhEU08BuwUQhhW/blewNXAvQ30IH9MKhzX9l0D2kPAjiGE4dXX7xBC2KuuOb4x\nxo+A54D/DiF0CiHsCpxJ3b3D9Vm1P29GCKF/CGEMqSHFhY29lxjjXcAVwD9XhdsQwgkhhL7Vp3wO\nVFU/oO7va23dSPWEL6n+b1DY8OmSJG04g68kqcWIMV4PXAxcCXxKqhf3XBqx4FWMcQEwhFQv5afA\nG6SG/Z7bwMf+AORX7wl88aqmaje7HrUvAw4ntahVRfXjD6Tm0tblZCC7+rwpQH6McVpjr0dqWPUS\n4AtgGqkh1wNjjLPXp/4Y40Tg98CT1StUDwRerG77fmBkjHFe9emFwMTq7+uEepq8AdgU+IxUuH9k\nPe5JkqTvJDTFdJrqrRJeBj6KMR5bx/s3kvrLSCWQF2OclfaiJElSjertiP4SY5yUdC2SJG1sTdXj\newGpuULrCCEMAXJijDsA5wC3NlFNkiSJmq2WtgNKk65FkqR0SHvwrd6S4UhS2zDU5ThgIkCM8UVg\nsxBCn3TXJUmSIISwBfBvYFqM8dmk65EkKR2aYjuj/yG19cFm9bzfl9RKl6uUVx/7pO7TJUnSxlI9\n97m+/0dLktQqpDX4hhCOAj6JMc4KIQxiA7YqCCG4t58kSZIktWIxxrRsb5fuHt8DgGNDCEcCnYFu\nIYSJMcbTap1TDmxT63U/6tmn0H3t1RoUFhZSWFiYdBnSBvHnWK2FP8tqDfw5VmsRQvq2dE/rHN8Y\n4xUxxm1jjNuR2r7hqbVCL8D/AacBhBD2BT6PMTrMWZIkSZK0UTTFHN91hBDOAWKMcWyM8ZEQwpEh\nhA9IbWd0RhI1SZIkSZJapyYLvjHGp4Gnq5/fttZ75zdVHVLSBg0alHQJ0gbz51ithT/Lag38OZa+\nXWgp82ZDCLGl1CpJkiRJWj8hhBa7uJUkSZKkJta/f3/KysqSLkOqU1ZWFvPmzWvSa9rjK0mSJLUy\n1T1nSZch1am+n8909vimdVVnSZIkSZKSZvCVJEmSJLVqBl9JkiRJUqtm8JUkSZIktWoGX0mSJEmJ\n++///m9+8YtfpKXtwYMHM27cuLS0DbDLLrswY8YMYM37KCsrIyMjg6qqqrRdW43jdkaSJEmSEnf5\n5ZcnXcI6ysrKyM7OpmvXrgB06dKFgQMHMnLkSA477LCa8956662a52vfRwjrv0jx4MGDOfXUU/n5\nz3/+HSvX2uzxlSRJktqI0tIyhg8vYvDgAoYPL6K0dP33+t0YbbQkIQS++OILlixZwuuvv85hhx3G\nT37yEyZOnJhYTd98801i126pDL6SJElSG1BaWkZu7hgmT76E6dOLmDz5EnJzx6xXcN0YbVx77bX0\n69eP7t27s/POOzNt2jQAioqKOPXUU4HVQ4THjx/Ptttuy+abb86tt97Kyy+/zG677UavXr0YMWJE\nTZsTJkzgwAMPZMSIEfTo0YMBAwbw1FNP1VvDuHHjGDBgAL1792bIkCHMnz+/wZpX7Tm75ZZbMnLk\nSAoLC/ntb39b8352dnbN9Wrfx9qmTJnCdtttx+zZs1m+fDmnnnoqm2++OT179mSfffZhwYIFXHnl\nlcycOZPzzz+f7t27M3LkSAAyMjL485//zI477siOO+4IwIUXXsi2227LZpttxsCBA3nmmWcavI+2\nzOArSZIktQH5+eMpKSkCulQf6UJJSRH5+eObrI05c+Zw880388orr7BkyRIef/xx+vfvX/P+2sOC\n//Wvf/HBBx9w5513cuGFF3L11Vfz1FNP8dZbb3H33Xczc+bMmnNffPFFdthhBxYuXEhhYSHHH388\nn3/++To1PPDAA/zhD3/g/vvvZ8GCBRx00EGcfPLJjf4OAI4//ng+/fRT3nvvvTrfr2t48x133MHl\nl1/Ok08+yYABA5gwYQJLliyhvLycRYsWceutt9K5c2euuuoqDjroIG666SaWLFnCjTfeuEbtL730\nErNnzwZg77335o033mDx4sWccsopnHjiiaxYsWK97qWtMPhKkiRJbUB5eRWrA+sqXZg8uYoQaNRj\n8uS626ioaNziTe3atWPFihW89dZbrFy5km233Zbs7Ow6zw0hMGrUKDp27Ehubi5du3Zl2LBh9O7d\nm8zMTA466CBee+21mvP79OnDyJEjadeuHSeddBLf+973ePjhh9dp97bbbuPyyy9nxx13JCMjg8su\nu4xZs2bx4YcfNuoeADIzMwFYtGjRt54bY+R//ud/uO6663j66adr7rdDhw4sXLiQOXPmEEJgjz32\nqJlLXJ8rrriCzTbbjE6dOgFwyimn0KNHDzIyMrjoootYvnx5vWG8rTP4SpIkSW1A374ZQOVaRysZ\nNiyDGGnUY9iwutvIzGxcrMjJyeGGG26gsLCQPn36cMopp/Dxxx/Xe/6WW25Z87xz587rvF62bFmt\n++u7xmezsrKoqKhYp82ysjIuuOACevXqRa9evejduzchBMrLyxt1D0DNub17927U+aNHj+a8885j\n6623rjl22mmnccQRRzB06FD69evHpZde+q1zd/v167dOuwMGDKBnz5707NmTJUuW8NlnnzX6PtoS\ng68kSZLUBhQX55GTU8Dq4FpJTk4BxcV5TdrG0KFDmTlzJmVlqXnBl156aaM/25C1g+v8+fNremZr\n22abbbjttttYtGgRixYtYvHixSxbtox999230de677776NOnT81c24aEEHjiiScoLi7mvvvuqzne\nrl078vPzefvtt3nuued46KGHahbMqm8l6NrHn3nmGf70pz9x7733snjxYhYvXkz37t1r5iNrTQZf\nSZIkqQ3Izs5i6tQRDBs2msGDCxg2bDRTp44gOzurydqYM2cO06ZNY8WKFXTs2JHOnTuTkVF3JFnf\nAPfpp58yZswYVq5cyT333MO7777LUUcdtc55v/zlL7nmmmtq5sl+8cUX3HvvvfW2G2OsqeXTTz/l\npptuori4mD/84Q+NqivGyPe//30ee+wxzj//fB588EEApk+fzltvvUVVVRVdu3alQ4cOtGvXDkgN\n2547d26D7S5dupQOHTrQu3dvVqxYwe9//3uWLl3aqJraIvfxlSRJktqI7OwsJk0qSKyN5cuXc9ll\nl/Huu+/SoUMH9t9/f8aOHVvnuWv3en7b63322Yf333+fzTffnK222oopU6bQo0ePdc798Y9/TGVl\nJUOHDmX+/Plsttlm5ObmcsIJJ9RbR8+ePYkx0qVLF/baay/uvfdecnNz662lrjp33XVXHnzwQY4+\n+mjGjx/P4sWL+eUvf0l5eTldu3Zl6NChDB8+HIALLriA008/nVtuuYVTTz2VG264YZ1rHHHEERxx\nxBHsuOOOdO3alYsuuohtttmm3jrautBSusJDCLGl1CpJkiQlKYTQpoa8Tpgwgb/+9a/MmDEj6VIo\nKCigvLyc22+/PelSmq36fj6rj9f/rwgbwKHOkiRJkrQRxBiZPXt2vStVKzkOdZYkSZKkjWDPPfdk\nk0024eabb066FK3Foc6SJElSK9PWhjqrZXGosyRJkiSpTSktLWP48KK0XsMeX0mSJKmVscdXzVnt\nn8/S0jJyc8dQUlIEdLXHV5IkSZLUuuTnj68OvV3Seh2DryRJkiQpEeXlVaQ79ILBV5IkSZKUkOXL\nM4DKtF/H4CtJkiSpWfnVr37F1VdfDcAzzzzDzjvvXPNednY2Tz31VFKl1ZgwYQIHHXRQ0mU0qY39\n3f/jHzBnTh7bbFNAusOvwVeSJElSk+nfvz+bbropm222Gb169eLAAw/ktttuW2MxrltuuYXf/e53\nABx44IG88847G3TNoqIiTjvttA1qoy4hpGUdpvUyePBgxo0bl3QZ6+2JJ+Ccc+Dxx7N4+ukRDBs2\nOq3XM/hKkiRJbUTpvFKGjxzO4LzBDB85nNJ5pU3eRgiBhx9+mC+++IKysjIuu+wyrr32Ws4888z1\nrmVjchXs+n3zzTcbvc1hw+C++2DPPSE7O4tJkwo2+jVqM/hKkiRJbUDpvFJyz89lcrfJTM+ezuRu\nk8k9P3e9guvGaANWh8xu3bpx9NFHc9dddzFhwgRmz54NwBlnnMGoUaMAePrpp9lmm23qbOedd95h\nu+2246677gLg2muvpV+/fnTv3p2dd96ZadOm8fjjj3PNNddw11130a1bN/bYYw8g1VN65ZVXcuCB\nB9KlSxdKS0sZP348AwYMoHv37my//faMHTu2wfuoqqpixIgR9OjRgwEDBtQMA7733nvZa6+91jj3\n+uuv5yc/+Umd7QwePJhRo0Zx4IEH0r17d370ox+xaNGimvdfeOEFDjjgAHr27Mkee+zB008/DcCV\nV17JzJkzOf/88+nevTsjR46ksLCQkSNHArBy5Uq6du3KpZdeCsDXX39N586d+fzzzwH4v//7P3bZ\nZRd69erFoYceyrvvvltzzezsbP74xz+y22670bVr13XCb+3vfu7cufTu3ZtZs2YBUFFRwZZbbsmM\nGTPq/e7uvBMOPLDBr3ejMvhKkiRJbUD+9fmU7FYCHasPdISS3UrIvz6/Sduoy8CBA+nXrx8zZ86s\n8/26hhS/+uqr/OhHP+Lmm2/mZz/7GXPmzOHmm2/mlVdeYcmSJTz++OP079+fI444giuuuIKf/exn\nLF26lNdee62mjUmTJnH77bezdOlStt12W/r06cMjjzzCkiVLuOOOO7joootqwlxdXnzxRXbYYQcW\nLlxIYWEhxx9/PJ9//jnHHnss8+bN47333lvjWqeffnq9bd15551MmDCBBQsWsHz5ckaPTg39LS8v\n5+ijj2bUqFEsXryY0aNH89Of/pSFCxdy1VVXcdBBB3HTTTexZMkSbrzxRg455JCaYPzSSy+x1VZb\n1QTQ5557jp122okePXowZ84cTjnlFG688UYWLFjAkCFDOOaYY1i5cmVNTX//+9959NFH+fzzz2nX\nrl293/12223HH//4R4YPH85XX33FGWecwRlnnMHBBx9c7/0edli9b6WFwVeSJElqA8qXlK8OrKt0\nhMlvTCYUhUY9Jr8xuc42KpZUbHB9mZmZa/RyNmTGjBkcd9xxTJo0iSFDhgDQrl07VqxYwVtvvcXK\nlSvZdtttyc7ObrCdvLw8dtppJzIyMmjfvj1Dhgyhf//+ABx00EEcfvjh9YZxgD59+jBy5EjatWvH\nSSedxPe+9z0efvhhOnbsyIknnsikSZMAePvttykrK+Ooo46qt60zzjiDnJwcOnXqxEknnVQTuCdP\nnsxRRx3FEUccAcB//dd/sddee/HII4/U2c5+++3H+++/z+LFi5kxYwZnnnkm5eXlfPnll8yYMYND\nDjkEgLvvvpujjz6aQw89lHbt2nHJJZfw1Vdf8dxzz9W0dcEFF5CZmUmnTp0a/O4BzjzzTLbffnv2\n2WcfPvnkE6666qqGvvomZ/CVJEmS2oC+3fvCirUOroBhuw4jFsRGPYbtOqzONjK7Z25wfeXl5fTq\n1atR5952220ccMABa6yqnJOTww033EBhYSF9+vThlFNO4eOPP26wnbWHUD/66KPst99+9O7dm549\ne/Loo4/y2Wef1fv5vn37rvE6KyuLiorUPwKcfvrp/O///i+Q6u096aST6NChQ71tbbXVVjXPN910\nU5YtWwZAWVkZd999N7169aJXr1707NmTZ599tt5722STTdhrr72YPn06M2bMYNCgQey///4888wz\nPP300zXBt6KigqysrJrPhRDYZpttKC8vrznWr1+/ddqv67tf5ayzzuLtt99mxIgRDd5rEgy+kiRJ\nUhtQfHExOa/nrA6uKyDn9RyKLy5u0jbq8tJLL1FRUdHo7YFuvfVW5s+fz8UXX7zG8aFDhzJz5kzK\nysoAaua21rf6cu3jK1as4IQTTuC3v/0tCxYsYPHixQwZMqTBRa9qh0SA+fPnk5mZ+keAfffdl44d\nOzJz5kz+93//l1NPPbVR97a2bbbZhtNOO41FixaxaNEiFi9ezNKlS/nNb35T770dfPDBPPXUU8ya\nNYuBAwdy8MEH8/jjj/PSSy/VDD/OzMys+Z5W+fDDD9cIu3W1Xd93X1lZyYUXXsiZZ55JYWFhzTzi\n5sLgK0mSJLUB2f2zmXrTVIYtHcbg0sEMWzqMqTdNJbt/w8OBN3YbtS1dupSHHnqIk08+mVNPPZUB\nAwY06nPdunXjscceY8aMGVx++eUAzJkzh2nTprFixQo6duxI586dychIxZ0+ffowb968BkPsihUr\nWLFiBZtvvjkZGRk8+uijPPHEEw3W8cknnzBmzBhWrlzJPffcw7vvvsuRRx5Z8/7w4cM5//zz6dix\nI/vvv3+j7m1tw4cP58EHH+SJJ56gqqqKr7/+mqeffrqmZ7lPnz7MnTt3jc8ccsghTJw4kQEDBtC+\nfXsGDRrE7bffTnZ2Nr179wbgpJNO4uGHH2batGmsXLmS0aNHs8kmm7Dffvs1WE9d3z3AyJEj2Xvv\nvRk7dixHHnkk55xzzne633Rpn3QBkiRJkppGdv9sJt04KfE2jjnmGNq3b09GRgYDBgzgkksuaXRQ\nWtUL2b17d6ZOncqhhx5Kx44dOeGEE7jssst499136dChA/vvv3/Nqsyr5tv27t2b7bbbjpdffnmd\n3syuXbty4403cuKJJ7JixQqOOeYYjjvuuAZr2XfffXn//ffZfPPN2WqrrZgyZQo9e/asef/UU09l\n1KhRFBQ0vFVPQ/sB9+vXjwceeIDf/OY3nHzyybRv3569996bW265BUjNwz399NO55ZZbOPXUU7nh\nhhvYf//9+frrr2uGNQ8YMIDOnTvXvAbYcccdmTRpEueffz4VFRXsvvvuPPjgg7Rv377emur77vfc\nc0+eeOIJ3nzzTSC1gvUee+zBnXfeycknn9zgvTeV0FL2qwohxJZSqyRJkpSkEEKr2Zd22rRpnH32\n2XzwwQdJl7Levv76a/r06cOrr75KTk5O0uU0G/X9fFYfr/9fATaAQ50lSZIkNVtvvvnmt67O3Fz9\n+c9/ZuDAgYbeZsChzpIkSZKapQsvvJAHH3yQiRMnJl3KelsV1u+///6EKxE41FmSJElqdVrTUGe1\nPg51liRJkiRpIzP4SpIkSZJaNYOvJEmSJKlVc3ErSZIkqZXJyspqcG9YKUlZWVlNfk17fCVJkqRW\nZt68ecQYfbSyx9y588jJ+TWwDIjAMnJyfs3cufOorIy8917kyScj48dHrroqcs45kaOOiuy6a6RX\nr0inTpGcnMhmm42q/vyaj4EDR/Hpp5FvvtmwWr7ts/PmzWvy3xP2+EqSJElSC5CfP56SkiKgS/WR\nLpSUFLHTTqMJoYC+fWGbbaBfv9SvP/gBHHnk6tebbw4hwPDhGUyeXFmrHYBKdtwxgy22aFwt2dlZ\nTJ06gvz80VRUVJGZmUFx8Qiys5u+N7cxDL6SJEmS1AKUl1exZlgF6MLAgVXMnJkKtY1RXJzHCy8U\n1ArRleTkFFBcPGK96snOzmLSpIL1+kxS0hp8QwidgBlAx+rHAzHGK9Y65xDgAWBu9aH7YoxXpbMu\nSZIkSWpp+vbNANbtqe3fP6PRoRdaXm/txhBiTO/G1iGETWOMX4YQ2gHPAr+OMT5b6/1Dqo8d+y3t\nxHTXKkmSJEnN1UsvlbHvvmOoqlqzp3bq1NYRWkMIxBjTsipb2oc6xxi/rH7aidRiWovrOM0l5yRJ\nkiSpAdddl8WZZ47gyy/bTk/txpL24BtCyABeAXKAW2OMs+s4bb8QwiygHPhNPedIkiRJUpv04IPw\n8svwxhtZbLppy5hX25w0RY9vFbBHCKE78EQI4ZAY49O1TnkF2LZ6OPQQ4H5gx7raKiwsrHk+aNAg\nBg0alLa6JUmSJKk5+OILOPdcmDgRNt006Wo2nunTpzN9+vQmuVba5/iucbEQ8oEvY4zXNXBOKbBn\njHHRWsed4ytJkiSpzfnVr+Cbb2Ds2KQrSa8WO8c3hLA58J8Y4xchhM5ALlC01jl9YoyfVD/fm1QY\nX7Rua5IkSZLUtsyYkRrm/NZbSVfSsqV7qPPWwIQQQiC1sNXfYoxPhhDOAWKMcSxwQgjhV8B/gK+A\nn6W5JkmSJElq9r76Cs46C266CXr0SLqalq1JhzpvCIc6S5IkSWpLLr8cPvgA7rkn6UqaRosd6ixJ\nkiRJWn+vvQbjxsHrryddSeuQkXQBkiRJkqTVVq5MDXG+9lrYaqukq2kdDL6SJEmS1Ixcfz307g2n\nn550Ja2Hc3wlSZIkqZl4/33Ybz946SXIzk66mqaVzjm+9vhKkiRJUjMQI/ziF/C737W90JtuBl9J\nkiRJagZuvx2+/BJGjky6ktbHoc6SJEmSlLDycth9d5g2DXbZJelqkuFQZ0mSJElqpWKE886Dc89t\nu6E33dzHV5IkSZISdO+9MGcO3HVX0pW0Xg51liRJkqSELFqU6uWdMiW1mnNbls6hzgZfSZIkSUrI\nGWdAt25w441JV5K8dAZfhzpLkiRJUgKmTk0tZvXWW0lX0vq5uJUkSZIkNbFly1J79t52G3TtmnQ1\nrZ9DnSVJkiSpiV10ESxcCBMnJl1J8+FQZ0mSJElq4UpLy8jPH88771Qxe3YGzz6bB2QlXVabYI+v\nJEmSJKVZaWkZubljKCkpAroAleTkFDB16giysw2/kN4eX+f4SpIkSVKa5eePrxV6AbpQUlJEfv74\nBKtqOwy+kiRJkpRm5eVVrA69q3ShoqIqiXLaHIOvJEmSJKVZ374ZQOVaRyvJzDSSNQW/ZUmSJElK\ns1//Oo+MjAJWh9/UHN/i4rzkimpDXNxKkiRJktLsiitg7twy2rcfT0VFFZmZGRQX57mwVS3pXNzK\n4CtJkiRJabRgAey0E7z6KmSZc+vlqs6SJEmS1EL98Y8wdKihN0n2+EqSJElSmnz8MQwYAG++CX37\nJl1N8+ZQZwy+kiRJklqeCy9M/XrDDcnW0RIYfDH4SpIkSWpZPvoIdt0VZs+GrbZKuprmz+CLwVeS\nJElSy3LeebDppvCnPyVdSctg8MXgK0mSJKnlKCuDH/4Q3n0Xttgi6WpaBld1liRJkqQW5Oqr4Zxz\nDL3NhT2+kiRJkrQRzZ0Le+8Nc+ZAr15JV9Ny2OMrSZIkSS1EcTGcf76htzlpn3QBkiRJktRazJkD\nDz0E77+fdCWqzR5fSZIkSdpIfv/71N69PXokXYlqc46vJEmSJG0Es2fD4MHwwQfQrVvS1bQ8zvGV\nJEmSpGausBB+/WtDb3Nkj68kSZIkbaA33oDDD4eSEujSJelqWiZ7fCVJkiSpGSsogEsvNfQ2V/b4\nSpIkSdLaNjMcAAAgAElEQVQGeOUVOPbY1Nzezp2TrqblssdXkiRJkpqpggK4/HJDb3PmPr6SJEmS\n9B29+GJqfu+UKUlXoobY4ytJkiRJ39GoUfC730GnTklXooYYfCVJkiTpO3jmGZgzB844I+lK9G0M\nvpIkSZL0HYwaBfn50LFj0pXo2xh8JUmSJGk9TZsG8+fDaaclXYkaw+ArSZIkSeshxlRvb0EBtHe5\n4BbB4CtJkiRJ62HqVFiwAE45JelK1FgGX0mSJElqpFW9vYWF0K5d0tWosdLaMR9C6ATMADpWPx6I\nMV5Rx3k3AkOASiAvxjgrnXVJkiRJ0vooLS0jP388b7xRxfz5GQwcmAdkJV2WGimtwTfGuDyEMDjG\n+GUIoR3wbAjhgBjjs6vOCSEMAXJijDuEEPYBbgX2TWddkiRJktRYpaVl5OaOoaSkCOgCVHLEEQVM\nnTqC7GzDb0uQ9qHOMcYvq592qr7e4rVOOQ6YWH3ui8BmIYQ+6a5LkiRJkhojP398rdAL0IWSkiLy\n88cnWJXWR9qDbwghI4TwGvAxMD3GOHutU/oCH9Z6XV59TJIkSZISV15exerQu0oXKiqqkihH30Ha\nF9+OMVYBe4QQugNPhBAOiTE+/V3aKiwsrHk+aNAgBg0atFFqlCRJkqT6rFyZQWo5otrht5LMTNcK\n3hDTp09n+vTpTXKtEGNskgsBhBDygS9jjNfVOnYrMC3GeFf163eBQ2KMn6z12diUtUqSJEnSuHFw\n2WVldOo0ho8+Wj3HNyfHOb4bWwiBGGNIR9vpXtV5c+A/McYvQgidgVygaK3T/g84D7grhLAv8Pna\noVeSJEmSmtp118GYMfDMM1l06DCC/PzRVFRUkZmZQXGxobclSWuPbwjhB8AEIJCaT/y3GOPoEMI5\nQIwxjq0+7ybgR6TGD5wRY3y1jrbs8ZUkSZKUdjFCfj5MmQJPPAHbbJN0RW1DOnt8m3So84Yw+EqS\nJElKt6oqGDECXngBHnsMttgi6YrajhY71FmSJEmSWor//Afy8uCjj2DaNOjePemKtLEYfCVJkiS1\neV99BSedlBrm/Nhj0Llz0hVpY3L9bUmSJElt2pIlMGRIqof3H/8w9LZGBl9JkiRJbdaCBTB4MHz/\n+/C3v0GHDklXpHQw+EqSJElqkz78EA4+ONXbe9NNkGE6arX8TytJkiSpzXn/fTjoIDjrLLjqKghp\nWUtYzYWLW0mSJElqU2bNgiOPhOJiOPPMpKtRUzD4SpIkSWrVSkvLyM8fT3l5FR06ZPDyy3mMHZvF\nCSckXZmaisFXkiRJUqtVWlpGbu4YSkqKgC5AJVtvXcCee44AshKuTk3FOb6SJEmSWq38/PG1Qi9A\nF/797yLy88cnWJWamsFXkiRJUqtVWlrF6tC7ShcqKqqSKEcJMfhKkiRJapXuvRdefTUDqFzrnUoy\nM41CbYn/tSVJkiS1KosXw/DhcMUVMHlyHjk5BawOv5Xk5BRQXJyXXIFqciHGmHQNjRJCiC2lVkmS\nJEnJeOKJ1BZFP/4xXHstbLrp6lWdKyqqyMzMoLg4j+xsF7ZqbkIIxBjTsqOywVeSJElSi1dZCb/9\nLTz4IIwbB4cdlnRFWl/pDL4OdZYkSZLUoj3/POy+OyxdCm+8YejVutzHV5IkSVKLtGIFFBamenj/\n/Gc4/vikK1JzZfCVJEmS1OK88QacdhpkZcHrr0OfPklXpObM4CtJkiSp2Vq1MFV5eRV9+2ZQWJjH\nffdl8ac/wZ/+BKefDiEts0LVmri4lSRJkqRmqbS0jNzcMZSUFAFdgEo22aSA3XYbwV13ZZHlwsyt\niotbSZIkSWpz8vPH1wq9AF34+usicnLGG3q1Xgy+kiRJkpql8vIqVofeVbrw739XJVGOWjCDryRJ\nkqRmqW/fDKByraOVZGYaY7R+/ImRJEmS1Cyde24e7doVsDr8VpKTU0BxcV5yRalFcnErSZIkSc3O\n8uVw8MFw8MFl/Pvf46moqCIzM4Pi4jyys53g2xqlc3Erg68kSZKkZufss+Hzz+Huu92uqK1IZ/B1\nH19JkiRJzcrYsfDcc/DCC4ZebRz2+EqSJElqNp5/Ho47Dp55BnbcMelq1JTcx1eSJElSq/fxx3DS\nSTBunKFXG5fBV5IkSVLiVqyAE0+Es86Co49Ouhq1Ng51liRJkpS488+H+fPh/vshw+65NsnFrSRJ\nkiS1WhMmwNSp8K9/GXqVHvb4SpIkSUrMK6/AkCEwfToMGJB0NUqSi1tJkiRJanUWLIDjj4dbbjH0\nKr3s8ZUkSZLU5FauhMMPh333hWuuSboaNQfp7PE1+EqSJElqcr/+Nbz9Njz8MLRrl3Q1ag5c3EqS\nJElSq3HnnfCPf8DLLxt61TTs8ZUkSZLUZF5/HQ47DP75T9htt6SrUXPi4laSJEmSWrxFi1KLWd14\no6FXTcuhzpIkSZLSprS0jPz88Xz0URVz5mQwZEgeJ5+clXRZamMMvpIkSZLSorS0jNzcMZSUFAFd\ngEqmTy+gtHQE2dmGXzUdhzpLkiRJSov8/PG1Qi9AF+bOLSI/f3yCVaktMvhKkiRJ2uiWLIEXX6xi\ndehdpQsVFVVJlKQ2zOArSZIkaaOZOxcuugiys2HFigygcq0zKsnMNIaoafkTJ0mSJGmDxAjTp8OP\nfwz77AObbAKzZsH06Xnk5BSwOvxWkpNTQHFxXmK1qm1yH19JkiRJ38nXX8Pf/w433ADLl8OFF8Lw\n4dCl1ujmVas6V1RUkZmZQXFxngtbqU7p3MfX4CtJkiSpXquCa3l5FX37poJr585Z3HIL3HYb7LFH\nKvDm5kKG40m1AVps8A0h9AMmAn2AKuAvMcYb1zrnEOABYG71oftijFfV0ZbBV5IkSWpCdW1H1LVr\nASGMYNiwLEaOhJ13TrpKtRYtOfhuBWwVY5wVQugKvAIcF2N8t9Y5hwC/jjEe+y1tGXwlSZKkJjR8\neBGTJ1/CmiszV3LCCaO5556CpMpSK5XO4JvWwQgxxo9jjLOqny8D3gH61nFqWm5OkiRJ0ndXXl73\ndkQLF7odkVqWJhuFH0LoD+wOvFjH2/uFEGaFEB4OIQxoqpokSZIk1e2bb+Cjj9yOSK1D+6a4SPUw\n53uBC6p7fmt7Bdg2xvhlCGEIcD+wY13tFBYW1jwfNGgQgwYNSku9kiRJUlu2fDkMGwZbbJHHN98U\nUFq6eo5vajuiEUmXqFZg+vTpTJ8+vUmulfZVnUMI7YGHgEdjjP+vEeeXAnvGGBetddw5vpIkSVKa\nLV0KP/kJ9OgBkydDRYXbEalptNjFrQBCCBOBz2KMF9fzfp8Y4yfVz/cG7o4x9q/jPIOvJEmSlEYL\nFsCRR8IPfwh//jO0a5d0RWpL0hl80zrUOYRwADAMeDOE8BoQgSuALCDGGMcCJ4QQfgX8B/gK+Fk6\na5IkSZK0rvnz4fDD4ac/hauuguDys2pF0t7ju7HY4ytJkiSlxzvvwBFHwEUXpR5SElpsj68kSZKk\n5u1f/4Jjj4U//hFOOy3paqT0MPhKkiRJbdTUqXDKKTBuHBxzTNLVSOnjBlySJElSG3TPPTB8ONx3\nn6FXrZ89vpIkSVIbc+utUFwMTzwBu+2WdDVS+hl8JUmSpDYiRrj6arjjDpgxA3Jykq5IahoGX0mS\nJKmVKi0tIz9/POXlVWRmZtCxYx6vvprFM8/A1lsnXZ3UdAy+kiRJUitUWlpGbu4YSkqKgC5AJZts\nUsALL4xg662zki5PalIubiVJkiS1Qvn542uFXoAufP11EX/60/gEq5KSYY+vJEmS1EzVHqrct28G\nxcV5ZGfX3Vv7xRfw6qvw8svwyivwwANVrA69q3ShoqIq3WVLzY7BV5IkSWqG6hqq/MILBUydOoJe\nvbJ49dVUwH3llVTY/fe/YffdYc894aijYNmyDB5+uJI1w28lmZkO+lTbE2KMSdfQKCGE2FJqlSRJ\nkjbU8OFFTJ58CWsH127dRlNVVcBuu6VC7l57pX7daSdo1271mXUF55ycVHCur9dYSlIIgRhjSEfb\n9vhKkiRJzVB5ed1DlXfaqYrnnoP23/I3+ezsLKZOHUF+/mgqKlKrOhcXG3rVNhl8JUmSpGaob98M\nYN2hyjvumPGtoXeV7OwsJk0qSEN1UsviAH9JkiSpGdp++zzaty8gFX5h1VDl4uK85IqSWijn+EqS\nJEnNzPjxMGoUTJpUxtix42sNVa5/VWeppUvnHF+DryRJktSM3H03XHghTJsG3/te0tVITcfFrSRJ\nkqQ24KGHYMQImDrV0CttTAZfSZIkqRl48kn4+c9T4XfXXZOuRmpdDL6SJElSwp59FoYOhSlTYO+9\nk65Gan1c1VmSJElK0Kuvwk9+ApMmwcEHJ12N1DoZfCVJkqSEvP02HHkk3HYbHHFE0tVIrZfBV5Ik\nSUrABx/A4YfDddelenwlpY/BV5IkSWpi8+dDbi4UFsKwYUlXI7V+Bl9JkiSpCX38MRx2GFxwAZx9\ndtLVSG2DqzpLkiRJDSgtLSM/fzzl5VX07ZtBcXEe2dlZ36mthQtTPb2nnQYXXrhx65RUvxBjTLqG\nRgkhxJZSqyRJklqH0tIycnPHUFJSBHQBKsnJKWDq1BGNDr+rgnNZWRWzZ2dw4ol53HJLFiGktXSp\nxQkhEGNMy+8Mg68kSZJUj+HDi5g8+RJSoXeVSgYPHs011xTQrRt07w7duqUe7dqt+fmNEZyltiKd\nwdehzpIkSVI9ysurWDP0AnRh1qwqLrwQlixJPZYuhWXLYJNNUkF4VRj+6KPxfPJJUa02ulBSUkR+\n/mgmTSpo2puR2jCDryRJklSPnj0zgErW7vE98sgMJk1a89yqKvjyyzXD8NlnV/HJJ+sG54qKqvQW\nLmkNjVrVOYSQFUI4rPp55xBCt/SWJUmSJCVr2TKYMyePXr0KSIVfWDVUubg4b53zMzKga1fIzISd\ndoKBA2GXXTJqfZaaNjIz3VxFakrfOsc3hHA28AugV4wxJ4SwA3BrjPG/mqLAWnU4x1eSJElN4ptv\n4Mc/hi23hN/9roxRo8ZTUVFFZub6rersHF+p8RJd3CqEMAvYG3gxxrhH9bE3Y4w/SEdBDdRh8JUk\nSVLaxQgjRsB778Ejj0CHDhvW3qpVnb9LcJbakqSD74sxxn1CCK/FGPcIIbQHXo0x7pqOghqow+Ar\nSZKktLv+erjjDnjmGdhss6SrkdqOpFd1fjqEcAXQOYSQC5wLPJiOYiRJkqQkTZmSCr7PP2/olVqT\nxvT4ZgBnAocDAXgcuL2pu1/t8ZUkSVI6Pf88HHccPP447LFH0tVIbU+iQ52bC4OvJEmS0qWkBA48\nEP76VzjyyKSrkdqmdAbfb11HPYRwdAjhtRDCohDCkhDC0hDCknQUI0mSJDW1hQtTYbegwNArtVaN\nGer8AXA88GaSXa72+EqSJGlj+/pryM2F/feHa69NuhqpbUt6VefpwKExxqp0FNBYBl9JkiRtTFVV\nMGxYas/ev/8dMr51LKSkdEp6VedLgUerA/DyVQdjjNenoyBJkiSpKVx5JcyfD08+aeiVWrvGBN9i\nYBmwCdAxveVIkiRJ6Td2LNxzT2ol5002SboaSenWmOCbGWPcJe2VSJIkSU3gscdSC1nNnAmbb550\nNZKaQmOC7yMhhMNjjE+kvRpJkiQpDUpLy8jPH89771Xx5psZTJqUx/bbZyVdlqQm0pjFrZYCXUjN\n7/0PEIAYY+ye/vLWqMPFrSRJkrTeSkvLyM0dQ0lJEam/1laSk1PA1KkjyM42/ErNRaL7+MYYu8UY\nM2KMnWOM3atfN2nolSRJkr6r/PzxtUIvQBdKSorIzx+fYFWSmlK9Q51DCDvFGN8NIfywrvdjjK+m\nryxJkiRpw8UIr75axerQu0oXKioS3a1TUhNqaI7vxcAvgOvqeC8Ch35b4yGEfsBEoA9QBfwlxnhj\nHefdCAwBKoG8GOOsby9dkiRJqt/nn8O550J5eQapv2bWDr+VZGa6h5HUVtT7uz3G+Ivqp0NijINr\nP4AjG9n+SuDiGOP3gf2A80IIO9U+IYQwBMiJMe4AnAPcut53IUmSJNUyYwbsvjv06gXPP59HTk4B\nqfALq+b4FhfnJVegpCbVmMWtXo0x/vDbjjXqYiHcD4yJMT5Z69itwLQY413Vr98BBsUYP1nrsy5u\nJUmSpAb95z9QWAjjxsHtt8NRR6WOr1rVuaKiiszMDIqL81zYSmpm0rm4VUNzfLcC+gKdQwh7kFrN\nGaA7sOn6XiiE0B/YHXhxrbf6Ah/Wel1efewTJEmSpEZ6/30YNgy22AJmzYI+fVa/l52dxaRJBckV\nJylRDc3xPQLIA/qRmue7KvguAa5Yn4uEELoC9wIXxBiXrX+ZkiRJUt1iTPXwXnZZqrf33HMhpKXP\nSFJLVW/wjTFOACaEEH4aY5zyXS8QQmhPKvT+Lcb4QB2nlAPb1Hrdr/rYOgoLC2ueDxo0iEGDBn3X\nsiRJktQKLFwIZ58NJSUwfTp8//tJVySpsaZPn8706dOb5FrfOsd3gy8QwkTgsxjjxfW8fyRwXozx\nqBDCvsANMcZ96zjPOb6SJEmq8c9/Ql4eDB0KV18NnTolXZGkDZHOOb5pDb4hhAOAGcCbpLZAiqSG\nSWcBMcY4tvq8m4AfkVpq74y69gg2+EqSJLVdqxanKi+vYqutMujaNY9HH83ijjsgNzfp6iRtDC02\n+G5MBl9JkqS2qbS0jNzcMZSUFJHai7eSTTctYObMEfzwh67MLLUWiQTfEMLxax2KwGfArBjj0nQU\n0xCDryRJUts0fHgRkydfQir0rlLJsGGjXalZakUS2c4IOKaOY72AXUMIZ8YYn0pHQZIkSVJt771X\nxZqhF6ALFRVVSZQjqQVqaFXnM+o6HkLIAu4G9klXUZIkSdJXX8Hvfw9vvplBaimYNXt8MzMzEqpM\nUkuz3n9axBjLgA5pqEWSJEkCYNo02HVXmDsXZszIIyengFT4BagkJ6eA4uK85AqU1KKs9+JWIYTv\nAeNjjPulp6R6r+scX0mSpFZu8WL47W/h8cfh5pvhmOrJd6tWda6oqCIzM4Pi4jyys13YSmpNklrc\n6kFSC1rV1gvYGhgeY3w+HQXVx+ArSZLUesUIU6bAyJFw/PFwzTXQvXvSVUlqSkkF30PWOhSBhcD7\nMcYV6SimIQZfSZKk1qm8HM47D+bMgb/8BQ44IOmKJCUhncG33jm+McangZ7AQGCTGOOMGOPbSYRe\nSZIktXylpWUMH17E4MEFDB9eRElJGbfeCrvvnnq89pqhV1J6NNTj+2fg+8BzwH8BD8YYi5uwtrXr\nscdXkiSphSotLSM3dwwlJUWkVmeuZJNNCth55xH87W9ZfP/7SVcoKWmJ9PgCBwOHxhgvBwYBP05H\nAZIkSWr98vPH1wq9AF34+usidt55vKFXUto1FHxXxBi/AYgxfgmkJXlLkiSp9Ssvr2LNfXgBuvDv\nf1clUY6kNqZ9A+/tFEJ4o/p5AHKqXwcgxhh3TXt1kiRJavH++U94/fUMUvvw1g6/lWRmNtQPI0kb\nR0NzfBvcGC3GWJaWiurhHF9JkqSW5bXX4LLLYO5cuOCCMm64Yc05vjk5BUydOsL9eCUByW1ntD3Q\nJ8b47FrHDwA+jjGWpKOg+hh8JUmSWobSUrjySnjqKRg1Cs46Czp0SC1wlZ8/noqKKjIzMyguzjP0\nSqqRVPB9CLg8xvjmWsd/AFwTYzwmHQXVx+ArSZK08awKoeXlVfTtu3FC6IIFcPXV8Le/wQUXwMUX\nQ9euG6deSa1fOoNvQ3N8+6wdegFijG+GEPqnoxhJkiSlX11bC73wQuOGHdcVmLfcMosbboD/+R8Y\nOhRmz4Y+fZriTiSpcRrq8X0/xrhDPe99EGPcPq2VrXtNe3wlSZI2guHDi5g8+RLWXmjqpz8dzd13\nF5BRz3pTdQXmzTcvIIQRHHpoFlddBds36d8QJbUmSfX4vhxCODvG+Je1ijkLeCUdxUiSJCn96tta\n6P77q+jUCbbYItVju+qx5ZapX++7b929eD/7rIgjjhjN3/9e0LQ3IUnroaHgeyHwjxDCMFYH3b2A\njsBP0l2YJEmS0qNXr7q3Fho6NIO//jU1V/eTT9Z8VFRASUndgXnFCvfildS81Rt8Y4yfAPuHEAYD\nu1QffjjG+FSTVCZJkqSNLkZYtiyPHj0K+PzzNbcWKi4eQadO0K9f6rG2Tz/NYPJk9+KV1PLUO8e3\nuXGOryRJ0oa7+24oLIT77ivjqqvWb2uhuub4uhevpI0lke2MmhuDryRJ0oZZsAB+8AO4/37Yd9/v\n1oZ78UpKF4MvBl9JkqQNdcopsPXWcN11SVciSetKalVnSZIktRIPPAAvvQSvv550JZLU9OzxlSRJ\nauUWL4ZddoE774SDD066Gkmqm0OdMfhKkiR9V2ecAV26wE03JV2JJNXPoc6SJEn6Th59FKZPhzff\nTLoSSUqOwVeSJKmVWrIEzjkHxo2Drl2TrkaSkuNQZ0mSpFbqnHMgRhg7NulKJOnbOdRZkiRJ6+XJ\nJ1PDnB3iLEmQkXQBkiRJ2riWLYOzz4Zbb4XNNku6GklKnkOdJUmSWpmRI+GLL2DChKQrkaTGc6iz\nJEmSGmXmTJgyxSHOklSbQ50lSZJaia++gjPPhJtvhl69kq5GkpoPhzpLkiS1Er/5DXz4Ifz970lX\nIknrz6HOkiRJatCLL8Lf/uYQZ0mqi8FXkiSphSotLSM/fzwffljFrFkZFBfnscUWWUmXJUnNjkOd\nJUmSWqDS0jJyc8dQUlIEdAEqyckpYOrUEWRnG34ltTzpHOrs4laSJEktUH7++FqhF6ALJSVF5OeP\nT7AqSWqeHOosSZLUgsQIb70FzzxTxerQu0oXKiqqkihLkpo1g68kSVIzF2Nq0ap77kk9vvoKNt00\nA6hkzfBbSWamA/okaW3+yShJkpSw0tIyhg8vYvDgAoYPL6K0tIwY4fXX4corYaed4Nhj4euvYeJE\nmDcPHnkkj5ycAlLhF1bN8S0uzkvsPiSpuXJxK0mSpATVtUhVjx4FbLbZCELI4sQT4cQTYa+9IIR1\nP5ufP56KiioyM1OrOruwlaSWKp2LWxl8JUmSEjR8eBGTJ1/C2kOWf/Sj0TzySME6YVeSWitXdZYk\nSWqF5s2DadPqXqRq+fIqQ68kbSQGX0mSpCb2zjtw+umw557Qo8eqRapqc5EqSdqY/BNV0v9v787j\no6rOP45/ngmJbKKgFUiAMaCCIKioKFUUanGpVURxJa3R4laN+17TIY3VH0q1iq0Wt6iguFQF64oK\nriAIgoqgGEOEhEVlFZFA5vz+mEkyyb1ZCJms3/frlVdm7pxz7pnkQu4z55zniIhIPfnkEzj9dBg6\nFHr3htxc+N//lKRKRCTe4rrG18weAX4PrHbODfB5/RhgKvBt9NALzrnbKmlLa3xFRESkyXEO3n0X\nbr89MtJ7/fUwZgy0bVtWRkmqRESacHIrMzsK+Al4oorA91rn3Ck1aEuBr4iIiDRaJcFrQUGYlJQA\nf/tbOl9+GeT22+GHH+CmmyAtDZKSGrqnIiKNUzwD31bxaLSEc+4DM6vu40qlbRAREZEmzW9Louee\nC9GzZwZZWUFOPx0SEhq6lyIiLVdjWOM72MwWmNkrZta3oTsjIiIisqMyM3Nigl6AdhQVZTFwYA5n\nnqmgV0SkocV1xLcG5gE9nHM/m9mJwEvAfpUVHjt2bOnjoUOHMnTo0Hj3T0RERKRaixb5b0m0cmW4\nIbojItIkzJw5k5kzZ9bLueK6xhcgOtX5Zb81vj5l84BDnHNrfV7TGl8RERFpVD7/PLJ29913s9i8\n+TrKB7+bGT16PJMmhRqqeyIiTUo81/jWx1Rno5J1vGbWOebxICKBuCfoFREREWlMVqyACy6AY4+F\n446DefO0JZGISGMW16nOZvYUMBTYw8y+A0JAEuCccxOBUWZ2KbAN2AKcFc/+iIiIiOyMDRtg3Dj4\nz3/g4oth6VLYbTeAINOnZ5CZOT5mS6IMbUkkItJIxH2qc13RVGcRERGpDxW3JcrOTiclJcgDD0T2\n4j3pJPjb36Bbt4buqYhI89JktzMSERERaUr8tiV6660QiYkZDBgQ5K23oH//hu6liIjsqMawnZGI\niIhIo+C3LdHq1Vn07p3DK68o6BURaaoU+IqIiIhEFRT4b0sUDmtbIhGRpkyBr4iIiAjwyy+wdm2A\nsszMJTaTnKxbJhGRpkz/i4uIiEiL97//Qb9+0KVLOj16aFsiEZHmRlmdRUREpMX65hu46qrItkT3\n3QfHH1+W1blsW6J0bUskIlIP4pnVWYGviIiItDibN8Mdd8CDD8INN0SC36Skhu6ViEjLFs/AV1Od\nRUREpMVwDp5/Hvr2hW+/hYULI4Gvgl4RkeZN+/iKiIhIs1UybbmgIEy7dgHWrUtn48YgTzwBxxzT\n0L0TEZH6osBXREREmqW8vHyGD58Qsy/vZvbYI8SsWRnsu6/W7IqItCSa6iwiIiLN0o035sQEvQDt\n+PHHLLKychqwVyIi0hA04isiIiLNSmEh3HsvvPhimLKgt0Q7CgvDDdEtERFpQBrxFRERkWZhyRIY\nMwYOOAB++QVOOilA2X68JTaTnKzbHxGRlkb/84uIiEiTNmsWnHpqJFlVjx6RPXnvvRfuuSedXr1C\nlAW/m+nVK0R2dnrDdVZERBqE9vEVERGRRi82O3NKSoCsrHQWLw4ybhwUFMC118L550Pbtv71CgvD\nJCcHyM5OJzVVia1ERBqjeO7jq8BXREREGjW/7MyJiSH23TeDzMwgo0ZBK2UtERFp8uIZ+Gqqs4iI\niDRqmZne7MzbtmVx0EE5nH22gl4REameAl8RERFp1AoK/LMzr1yp7MwiIlIzCnxFRESkUWvTRtmZ\nRURk5+gvhoiIiDRaK1bA/PnpdO6s7MwiIlJ7Sm4lIiIijdLGjTBkCKSlwahRys4sItLcKaszCnxF\nRFqu53oAACAASURBVERaku3b4eSTIRiEBx4Ai8ttkIiINCbK6iwiIiIthnNw+eWRx/ffr6BXRER2\nnjYAEBERkUZl/HiYNQvef19bFYmISN3QnxMRERFpNJ5/Hu67LxL4dujQ0L0REZHmQoGviIiINAqz\nZ8Oll8Kbb0K3bg3dGxERaU60xldEREQaXG4ujBwJjz8OBx/c0L0REZHmRiO+IiIiUit5eZEthgoK\nwqSk1H6LobVr4aSTIDMTfve7uu+niIiItjMSERGRHZaXl8/w4RPIzc0C2gGb6dUrxPTpGTsU/G7d\nCscdB4ceCv/4R9y6KyIiTYC2MxIREZFGJTMzJyboBWhHbm4WGRk5hMM1a8M5GDMG9twT7rorXj0V\nERHRVGcRERGphQULwpQFvSXa8fbbYTp1gsMPh8GDI1+DBkHHjpESsdOjf/ghQCCQzqxZQQL6KF5E\nROJIga+IiIjU2MqVcPnl8N13AWAz5YPfzZx+eoB//AM+/jiyJdH//R988gl07w79+uXz7rsT+P77\nsunRe+8dYvXqHZseLSIisqP0+aqIiIhUyzl49FE48EDYf3+YMyedXr1CRIJfKFnjm52dTufOcMop\ncMcdMGMGrFsHTz0F+fk5MUEvQDuWLcsiMzOnId6SiIi0IBrxFRERkSp9+y1cdBGsXw/Tp0eCXwgy\nfXoGmZnjKSwMk5wcIDvbf+S2VSs46CBo185/enRhYQ0XBYuIiNSSAl8RERHxVVwM994Lt98ON90E\nV10VCWJLpKYGmTQpVOP2UlL8p0cnJ2sCmoiIxJe2MxIRERHPnryjR6cTCgVp1w4eegj22aduzlEX\nWyCJiEjzFM/tjBT4ioiItHB+AWkgECI7O4Obbw5idXgLUhJgl02PTlfQKyIigAJfQIGviIhIvKSl\nZTF58nVUnII8evT4HZrKLCIisjPiGfhqUY2IiEgLl5enpFMiItK8KbmViIhIC1VUBPfdB598oqRT\nIiLSvOkvmoiISAtUsi3R22/Dq69WvieviIhIc6A1viIiIi1Ifj5ccw18+in8859w8slgpqRTIiLS\n8JTcCgW+IiIiO2PLFrjrrsjU5iuvhOuvh9atG7pXIiIiZeIZ+GqNr4iISDMTuydvcnKAo49OZ9y4\nIAMHwrx5ENRAroiItDAa8RUREWlG/PbkTUwM8cgjGfzhD4p4RUSk8dJ2RiIiIlIjmZk5MUEvQDu2\nbcvijTdyGrBXIiIiDUtTnUVERJqBcBhefx1efVV78oqIiFQU1xFfM3vEzFab2WdVlLnPzJaa2QIz\nOyie/REREWluNm6ECROgTx+49Vbo3btkT95Y2pNXRERatnj/FXwMOL6yF83sRKCXc25f4GLgwTj3\nR0REpEnJy8snLS2LYcNCpKVlkZeXD8DSpZHszHvvDR98AI89Fklc9dRT2pNXRESkorgntzKzIPCy\nc26Az2sPAjOcc89Eny8GhjrnVvuUVXIrERFpUfwSVXXtGqJ37wwWLQpy4YVw6aXQrZu3nvbkFRGR\npqY5b2eUAiyPeV4QPeYJfEVERFoav0RVK1dm0aPHePLzQ7Rp418vNTXIpEmh+uqmiIhIo9fQge8O\nGTt2bOnjoUOHMnTo0Abri4iISLwVFPgnqmrbNlxp0CsiItJUzJw5k5kzZ9bLuRo68C0Ausc87xY9\n5is28BUREWnu2rYtSVQVG/wqUZWIiDQPFQczs7Ky4nau+vjLadEvP9OAPwKY2RHAer/1vSIiIi3N\nK6/ArFnp7LWXElWJiIjsrLgmtzKzp4ChwB5E1u2GgCTAOecmRsvcD5xA5K/6+c65+ZW0peRWIiLS\n7DkHd98d+frvf6FzZyWqEhGRliGeya3intW5rijwFRGR5q6oCC65BObPh2nToEePhu6RiIhI/WnO\nWZ1FREQE+P57OP102GOPyL687ds3dI9ERESaD2XHEBERaWBffAGHHw5DhkSmNyvoFRERqVsa8RUR\nEWlAr7wC558fWdObltbQvREREWmeFPiKiIjUo7y8SLKqgoIwGzcGWL48nalTgwwe3NA9ExERab4U\n+IqIiNRSbBCbklJ9xuW8vHyGD59Abm4Wkb15NxMMhujSJQNQpmYREZF4UVZnERGRWvALYnv1CjF9\nekZp8LthA3z3HSxfHvk+YUIWX355XbR8ic2MHj2eSZNCDfAuREREGg9ldRYREWlkMjNzYoJegHbk\n5mZx5JHj6dQpxHffQTgc2ZKo5Ovnn8OUD3oj9QoLw/XbeRERkRZGga+IiMgOWrIEPvrIP4jdc88w\nkyZB9+6w++5gMZ9bp6UFWLZsMxVHfJOTtcmCiIhIPOkvrYiISFReXj5paVkMGxYiLS2LvLx8AJyD\nefPgL3+Bvn3ht7+FxMQAsLlCC5sZMCDAgAHQsWP5oBcgOzudXr1CMfUi06Ozs9Pj+bZERERaPK3x\nFRERwX/NbnJyiOOPz+Dtt4MkJcFpp0W+DjsM8vOrX+Nb2XkyM3MoLAyTnFx9QiwREZGWIp5rfBX4\nioiIAGlpWUye7E081b//eJ56KkS/ft4RXAWxIiIidUfJrUREROKsoKDyNbsHHOBfJzU1qGzMIiIi\nTYDW+IqISIu3ahUsWeK/ZleJp0RERJo+/TUXEZEW7ZVX4OCDYdSodHr2VOIpERGR5khrfEVEpEX6\n5Re4/nqYNg0mTYIhQ7RmV0REpCEpuRUKfEVEpO588QWcc05ka6IHH4xsPSQiIiINK56Br6Y6i4hI\ni+Ec3H8/DBsG11wDU6Yo6BUREWkJlNVZRESarZKpywUFYfbYI8Datels2hTko49g330bunciIiJS\nXxT4iohIs5SXl8/w4RPIzc0isk3RZnbfPcTs2Rnsu6/W7YqIiLQkmuosIiLNUmZmTkzQC9CO9euz\nyM7OacBeiYiISENQ4CsiIs3SZ5+FKQt6S7SjsDDcEN0RERGRBqTAV0REmpWVK+HMMyEvL0DZnrwl\nNpOcrD99IiIiLY3++ouISLMQDsPEiTBgQCRx1Zw56fTqFaIs+N1Mr14hsrPTG66TIiIi0iC0j6+I\niDR5ixfDRRfB9u2R4Ld//8jxkqzOhYVhkpMDZGenk5qqxFYiIiKNUTz38VXgKyIiTUbs9kQpKQEy\nM9N5+ukg//oXjB0Ll1wCCQkN3UsRERGpDQW+KPAVEWmOKgayVY3I+m1PlJgY4phjMnjssSDdutVn\nz0VERKSuxTPw1T6+IiLSIPwC2dmzQ0yfnuEb/N5yi3d7om3bsujceTzduoXqseciIiLS1CjwFRGR\nBuG3z25ubhannTaeYcNCrFoFq1fDqlWRr7VrtT2RiIiI1I4CXxERaRAFBf6B7I8/hklJgYEDoUuX\nsq8rrwzw1FObK9TR9kQiIiJSPQW+IiJS77Zvh40bS/bZLR/IHn10gGuv9da57bZ0Pv44VG5qdGR7\noox66bOIiIg0XUpuJSIi9eqTTyJbD7Vunc+KFRNYvrx8IFvZGl/Q9kQiIiLNmbI6o8BXRKSp27QJ\nbr0VnnkG7rwT/vAHWLZMgayIiIhEKPBFga+ISFP20kuQkQHDh0eC3j33bOgeiYiISGOj7YxERKTJ\niN2bd/fdA/z0UzrLlwd58kkYOrSheyciIiItkQJfERGpM35783bsGGLWrAx699YUZhEREWkY2gNC\nRETqRDgMl1zi3Zt33bossrNzGrBnIiIi0tJpxFdERKoVO305JaUsCdX27fDuu/DCC/Dii7Bhg//e\nvIWF4QbotYiIiEiEAl8REamS3/Tlt98OcdRRGcyYESQ1FU47DWbMgOzsAJMne/fmTU7WBCMRERFp\nOMrqLCIiVUpLy2Ly5OuoGMwecsh4XnghRI8eZUf9guTq9uYVERERAWV1FhGRBpSb6z99uUOHcLmg\nFyA1Ncj06RlkZo6P2ZtXQa+IiIg0LAW+IiLiKxyG+++H+fMDQM2nL6emBpk0KVQfXRQRERGpES26\nEhERj6++gqOPhmefhVdeSadXrxCR4BdKpi9nZ6c3XAdFREREdoDW+IqISKnt22H8+MjX2LHw5z9D\nIFCW1bls+nK6pi+LiIhInYrnGl8FviIiLZDf9kSbNgW54ALo2BEeegj23ruheykiIiItiQJfFPiK\niNQVv8zLHTuGcC6D8eMjwa/F5U+OiIiISOUU+KLAV0SkOn6juH7TkSvbnmjkyMj2RCIiIiINQdsZ\niYhIlfxGcWfNCvHooxk4F2T5ckq/XnvNf3ui9evD9d9xERERkXoQ96zOZnaCmS0xs6/N7Eaf148x\ns/VmNj/6dWu8+yQi0txkZubEBL0A7fj22yxOOimHzEx47TXYsAH69YMDDijZnihW5dsTiYiIiDR1\ncR3xNbMAcD9wLFAIzDWzqc65JRWKvuecOyWefRERac6WLPEfxR00KMw775Q/etJJ6QwfHio3OhzZ\nniijfjorIiIiUs/iPdV5ELDUOZcPYGZTgBFAxcBXaVRERGqhsBBuuQUWLSoZxS2/btdvFDc1Ncj0\n6RlkZo6P2Z4oQ9sTiYiISLMV78A3BVge83wFkWC4osFmtgAoAK53zn0Z536JiDRpP/8M//gH3Hsv\nXHQRzJmTzsiRNR/FTU0NMmmSElmJiIhIy9AYklvNA3o45342sxOBl4D9/AqOHTu29PHQoUMZOnRo\nffRPRKRBxWZrTk4OMGhQOnffHeTww2HuXEhNBdAoroiIiDQtM2fOZObMmfVyrrhuZ2RmRwBjnXMn\nRJ/fBDjn3Lgq6uQBhzjn1lY4ru2MRKTF8cvWnJQU4oknMjjrLAW1IiIi0nzEczujeKfwnAvsY2ZB\nM0sCzgamxRYws84xjwcRCcbXIiIi3HqrN1tzUVEWL7+c04C9EhEREWla4jrV2TlXbGaXA28SCbIf\ncc4tNrOLIy+7icAoM7sU2AZsAc6KZ59ERJqCFSvg8cfhhRf8szUXFmrPXREREZGaivsaX+fc60Dv\nCsf+E/P4X8C/4t0PEZHGJHbdbkpKgOzsdLp2DTJ1Kjz6aGTt7plnwjHHBHjjjZplaxYRERERf3Fd\n41uXtMZXRJoCv4C2YoIpv3W7HTqEMMvgsMOCnH8+jBwJbdr4l+3VK8T06UpcJSIiIs1LPNf4KvAV\nEakjfkFqMBhi4sQM2rULsm4drFsH996bxbx511FxFHfEiPG89JJ3i6GSYLosW7M3mBYRERFp6uIZ\n+DaG7YxERJqF66/3JqLKz8/ijDPG07dviI4doWNHWLXKf93uxo3+63a1566IiIjIzlHgKyKyk774\nAv75T3jpJf+A9pBDwrzzTtmRtLQAkydr3a6IiIhIfdFdlohINfLy8klLy2LYsBBpaVnk5eUTDsOr\nr8Jxx8Hw4RAMwqmnBoDNFWp7A9rs7HR69QrFlI2s283OTo/3WxERERFpkbTGV0SkCn7rdvfcM0SH\nDhl06BDk6qvhrLNgl112LBGV1u2KiIiIlKfkVijwFZGGkZaWxeTJ3kRUxx47nunTQ1iF/5oV0IqI\niIjUjpJbiYg0kKVL/dfthsNhT9ALSkQlIiIi0hhpja+IiI8PP4QRI2Dhwpqt2xURERGRxkt3biLS\nYlVMWpWbm8+LL8Kvfw1//COccALMn69EVCIiIiJNndb4ikiL5JeIqlWrEPvvn8Ff/xpk5EhISCgr\nq3W7IiIiIvGl5FYo8BWRmisJVAsKwqSkeAPVLVtg5Mgs3njDm7Tq3HPHM3my1uiKiIiI1DcltxIR\nqSG/kdyZM0NceGEG+flB5s2DpUshIcE/adXKleH677SIiIiIxJXW+IpI3FVcS5uXlx+3tm64IScm\n6AVoR0FBFk8+mcPhh8Mjj8C6dTBihJJWiYiIiLQUGvEVkbjyG4GdPTvE9OkZO7xO1q+tjz4KkZmZ\nwZdfBnn7bVi40H8kt0ePMBdfXHYkOzud2bND5dqKJK3KqP2bFREREZFGSUMbIhJXmZneEdjc3Cwy\nM3PqpK28vCxuuimHXXeFCRPgzDNrNpKbmhpk+vQMRo8ez7BhIUaPHl+rYFxEREREGj+N+IpIXH3+\nuf8I7NKlNV9L6xx8/DHMnOnfVr9+Yf7618iz5OR05s6t2UhuamqQSZOUyEpERESkuVPgKyJxsWUL\n3HADfPNNyQhs+ezJn30W4Kij4KKL4IwzYNWq8pmY//a3dDZuDDJlCkyZAq1bQ6dOAQoKvG3FjuaW\njORmZo6P2X5II7kiIiIiLZm2MxKROrdwIZx7LvTvDzfdlM+oURM8I7CvvRZZlztxInzwQT4wgY0b\ny8okJobYa68M/vCHIGefDQMGwLJl3jW+vXrVbr2wiIiIiDQu2scXBb4ijVHF/XKzstKZNi3I7bfD\n3XdDWhqYlZUrG4Etv6/uqadmMXVqzfbUra4tEREREWmatI+viNS5ikHrjgaQfhmWX3ghxP77ZzBn\nTpDU1LKy1a2l3bCh5nvqal2uiIiIiOwoBb4iLVBNthiqLjD2y7C8ZUsWvXuPJzV1xwLTlBT/dcDa\nU1dERERE6oLuKkVaoFtv9d9i6KqrcnCuLDCePPk6Zs7MYvLk6xg+fAJ5efn88gt88AHMmuU/Srtq\nVc2zNZfIzk6nV68QZdsQlWRiTq/dGxQRERERiaERX5EWZt06eOst/6D19dfDdO0KiYk5rFjhDYwH\nDRrPzz+H6NsXEhPrbpRWmZhFREREJJ4U+Iq0IDNnwnnnwe67B1izxhu0jhoV4I474MQT/QPjbt3C\nvP8+tG8PeXnpDB9es/1ya0Jrd0VEREQkXjTVWaQFKCqCG2+MbDH04IPw+uv+U4tvuy2dHj3g4IMD\nMa9RWqZfvwDt20eelYzSjh49nmHDQowePV7bComIiIhIo6TtjESaodjEVO3aBcjLS6dXryAPPwx7\n7VW+jN+2QH7Jr7RfroiIiIjEk/bxRYGvSInqsi37Ba177hni448z6Nlzx7Yr0n65IiIiIlJfFPii\nwFeajp3dH7e6tisbie3RI8iSJTBmTBazZ19HxfW7o0eP1xpaEREREWm04hn4KrmVSB2qyf64NWmj\nssDZb+/c3NwsjjhiPFu2hOjSBTZs8E9MVVi449sMiYiIiIg0B0puJVKHKgtMMzNzalS/sv1zFy7M\nZ/p0+Ogj/6C2a9cwy5bB11/D8OH+ialqs82QiIiIiEhzoDthER95efmkpWUxbFiItLQs8vLya1Sv\noMA/MF28OExxcfVtVxY4H3poDrfdBq1b+we1BxwQoFOnyLPsbP+MzdnZ6TV6DyIiIiIizY2mOotU\nUNvpytu2wQ8/lASm5dfX5uYG6NwZjjwyn9mzJ7BmTVnb06eHGDkyg+XLg7z9tn/gfNRRYWbMqNne\nuSXbDGVmjo9JTKVszCIiIiLScim5lUgFaWmRKcY7khzqm28gLQ2SkvL57rsJ5Od7k08lJAQ544ws\n5szxtj1gwHiyskI89lgW06ZVfW5lWxYRERGR5kjJrUTqUV6e/6jrsmXh6OtlyaeSkwMccEA6d98d\nJBSCyy4LsmxZ5aOtbdv6t73HHmFOPRUOPDCdRYuqH9FVdmYRERERkZpT4CsSY+pUmD/ff7rynDkB\nhgzJ5+uvy09VTkoKMW1aBscfHwluqwpMU1L82y5JPKVpyiIiIiIidU9TnaVRiOfetzU53w03pHPP\nPUHeew/uuCOfW27x7pU7bVoGF12Uw4cf1n6P3Kr24VVwKyIiIiItmaY6S7NWF3vfVtauXzDtd75n\nnglxxhkZLFwYpH37IIcd5j/qmpi4c3vkakRXRERERKT+KfCVBlf53rfVj6LuSHBbEkz7nW/79iwC\ngfG0bx85X2XTlaubqlwTWqMrIiIiIlK/FPhKg6ts79vI8boLbnNzsxgyZDw//lj7Udvs7HRmz646\n+ZSIiIiIiDQuCnylwbVp4z+KOn9+gKysfB5/fAJ5eTUPbocNG8/atf7BbceOYQ4+OMD//le7UVtN\nVRYRERERaXqU3ErqVezobdeuAZKT03nkEUhKKp8puWQU9cYbc1i+3JtMqmvX8axfH2bLlizPOfr0\nCdG9e4Dp0/2TUGVnpyvBlIiIiIhII6PkVtIoVZWJ2e81wBNwtmkT4s03M0hJ8R9FnTgxzPLl3pHb\nPfeMjNy++qp35PaQQwLR4NZ/SrJGbUVERESkpctblkfm3ZkUbCwgpUMK2ddkk7p3akN3K2404ivV\nqmkQWzJq6vdaSkqI5GRj7tyx7MhWQGlpWUyeXLuR25J+lwW38d0iSURERETqXl0EaGrD28bwy4eT\ne2AuJAFF0GthL6bfP32H2qqr4LmknckTJsdtxFeBbwtQWeBaWcKo2OMXXfRbLrjgxXLBZc+eIXr3\nNl57bSwVA9L99hvPzz/DihXeYDUp6VKKip7w9G/YsBDvvOOdslzSdwW3IiJSW7W5KavtjdzO3ADq\nnPGtq3M3bKC1s+9/ZwM0tVGec45zMs7hmd2eibRRogjO2XgOT014qt764mnndhT4tuTAt6aBa2XH\nKgaO3btfjVkbvvvudmKDyUcfHekJcpOSzqGo6GkqBrFwKeANYvfZJ8Quu8CiRd5AtnPn01i9+klP\nW1WN+Ma+fwW3IhJvO3pzVh9BVX0Fbo25zs6ca0dvymp7I7czN4A6Z3zr6twNG2jtaP2K9/tpV6bx\n1K5PeQK0szacxcN3P0zYhUu/isPF5Z6HXZhiV8yVN13JtD2medo4Yc0JjA2NZXt4O9vD2yl2xZHv\n4WLP8/vuvI+Pun/kaaN/bn9OvvBkftn+C1uLt7J1+1Z+Kf6Frdu3srV4a+R49PFXz3/FuoHrPG10\nmt+J3qN6k5SQVO3Xm4+8yeL9Fnva2GfJPgxOG8yW7Vv4edvPbNm2pdLHv2z/BWaAG+YTW82AhN8k\nsEurXdglYZfS70kJSZ5jS55fwsoBKz196bGoB4ePPhyHwznn+R524XLHPn3607J2xirwbTaBr9+I\n6sSJb1UawO6220Y+/TRcLkj1C1wrC2b79TOmTRtL+WAzE7iJigFoYuIf2bbtiQrHbwVu87yPqoJY\nwHd68ogRt/LFFwlKKiU7pSY3vzW9Qa7rcs2xzXi3He8gcEf7siM3Z/URVNVX4NaY6+xMvbQr0pi8\n62TPTdmZG85k4viJpTfFJTfLxa6Yy2+8nKmdpnrqjPhxBPeNu4+ABTCMgAVKv8yMS6+/lOd3f973\nXA//42Ec5e9hYu9pLrz2Qp7b/Tnfuo/e/ShmhmGe7+dddR5Pd3jaU++0dadxzx33sHX7VoqKi9ha\nHP0evfkuKi7izr/fyfvd3vfUPWrFUVxz0zUkBBJIsATP979n/53pXaZ76h278lhu+MsNpQFEyde2\n4m2lj/9z93+YG5zrqTsgdwCjLh1V+juoGMAUu2JefehVvur9ladun6/68PuLfk/AAqV99Hs85f4p\nfNrzU0/9g749iLMvO7tcoORw5Z6/+OCLfLnvl95zf92Hky48yfP7jP1dO+d47eHXfPvea3Evjjnv\nGMKEy12DsY/nTp5LQf8CT93OCzvTZ1QfT5BX8T0se2kZ6weu99TvMK8DyScnE6uy++zClwvZdOgm\nTxtt57Sl44kdy/2e/ILQrW9vJTw47KnPR8BQ31OWNwMY5j1sM422w9uW+7dY8vuueGz1/1azdchW\nTxvtP2xP3zP70irQigRLiHwPJPg+n/nYTNYMWuNpIzg/yJhrx7BLwi60btW6NCiMfbxLq8jzK264\ngnl95nnaOGTJIdw77l6Kiosq/doW3kZRcRETxk3g24O+9bSx32f7cUvmLbRJbEPbxLa0aRX9ntjG\n87hNYhv+eOUfff9/PHfTueTck1MaxFf8/yP22NU3Xc1nfT/z9KXvF335a+ivvv93lfwfGnvslltv\n4fN+n0cqj41f4Bv35FZmdgLwTyAAPOKcG+dT5j7gRCJDienOuQXx6k9s4LnbbhtxrhUbN7at0WO/\nQDX2eU3Klh9RXcwzz4xj+/Z/URIIvvdexQC2YpDajuXLO1dy7GzodDG0L4CfUsjNvZnc3HHAGuiU\nWXqctZ18jmWzyy7t2Lat4vE9gEXQ6Y6YYzdzxBFB5n96Fct/2gTtV8NPnenefleys28F4L33va/d\nc8+tLF+xnPOuGsz64o3sntCBR//578iU5SpuTuv7tXjWBXh6ytO88tErta5fV4FffZ2nrvtcevO7\nB1AEsy+fXe7mtyZl4lGuObZZVfkZ58zgg6c/2Km266IftSn/6r2v0r1H9/I35+FtXD3u6rLACiAJ\ncg/M5U9Zf+LKG69ky/bIp+Qln5w/ce8TvuV/f8PvOf3S00tvmmJvnCZNmORb59zMc7n42os9NwT/\nHv9v3/Ln3HoO6Vel+wYXz/77Wd86J994MqddclrZzaGV3RxO+dcU3zqn3HgKv7/w92wLb2Nb8bZy\n32fmzCT/wHxPncGXD2b/M/YvvfEtuZEvdsV8++K35W/Co3UGXjqQniN7lvar5Ma1pI+Ln1/MqgNX\neeod9ufD6D6iO9uKt3luDouKi9j0+SbvjXUSPL/oeV675zUSAgkUf1tM631al94w//D1D3C0t87r\nS1/nqEePqjQ42rB4Axzjf65X734VAKP8vZxZ5PnmLzdX2s+X73q50lGT4s+LvQFBEry85GXmPjq3\ndIQmKSGp3IhNUkISi79fDD29dZd8v4THFz5e7vcW+33hioXQw1tvXuE87vroLhIDiaXXfclXYkIi\nrawVK9avgH29dddvWU9RcVHp7zwpIclzjRaHi8vfoEfrbivexl7t9vIEjNuKt7HVbS09/v3m733r\n/7j5R9ZuWVvuQ4ySx60CrQhYgC1FW/zPvX0bXdp3Kft9xvx+S363QKV9T7AEBncfXC5Ar/hv4Jv/\nfkNBUoGnbtf2XRk7dGxpXxfMXsChvz7U88HMRe9exCdJn3jq99mjDzln5lBRbL9LnDfrPOYkzfG0\ncWDnA3l2zLPlg04rH3QmBBI48esTeS/pPU/9ocGhvPPXd6o8N0Daj2lMLvIJ0Pqfy6RbJvnWKP5e\nEQAAFNpJREFU8bTxrX8bI/qMYNKYGrbxnn8bRwWP4tajb61RG31+1Yd5RfO8H6L8qg9H9jiyRm18\n0v0Tvi361tPGYSmHcd5B59WoDYDsa7KZfflszweKt91/G4kJiSQmJNI+qX2VbfTv3J/Pij7z9OXg\nrgdz1gFn1bgvU7pM4fOiz73/TupYXANfMwsA9wPHAoXAXDOb6pxbElPmRKCXc25fMzsceBA4wre9\nZINdAAdsaQWtwtDKgQUIbE8ksU1btv/yC61aty73vfVuu9G+uDXFLswPmzfD9raQtAds2AAJ+0P7\nH2HDmmoeb4bP2jH56Vmw++6RgK7c8/xqynbmvy+8xy9b7osJTn9k+9q7ygWry5d3BC6KOfYDrB0O\nnSZWE7gmQO8RcHrZxct/Z9NhdVc2dj4WTs8rOz6lAyS+BKcvjyn7EW03dOOnlIplu8Auj8DIzaXH\nWk37H2efO5FPt1wPh35Xetw+6QF2S+R31edNz2vLC/7ABeMuYNkJkT6uL4ILxqXzqD3KBf93ge/N\nLFDpjW48XkvdO7XKm+udqVvy+mV/vYx1Z6yrdf26CPzq6zw7059Zl83ihbtfYK/kvUoDjmv/fq3v\nzfmlf7+U2/92OwmWwF9u/4tvmSvvuJI7/35n6U3qjbff6FtuzN/GcM1N15TeQP9z3D99y53xlzM4\n74qyPzAOxxP3+QdCZ996Nhdec2HpjcDEf0z0D2Yyz2HM1WPK3bzl3JvjW/ak60/i+D8dX3qT/9aj\nb5F3YJ6n3LCrhnHkH48sN2IzM2emb5vDrhrGoeceWm6EqKi4iCXPLWHtwLXlyhe2KuSwPx9G71G9\ny93gfvHsFxQeWOhpe8gVQzj4nIPLggbnWPjMQt9gZtCfB9HrtF6eEYT8l/LZcMgGT/kDLjygdNQh\ntvymNzax7YhtnvJ9xvQh6dikyM14TN/Xfr3WN+BZsHIBj3z6SOkn5a1btaZNqzas21Jhulq0/JZt\nW2gVaMX28HaKthWVm0K3auMq3zrL1i1jxrIZnilg3/z4DfTylv9u/XcsWLWgfHARDTh+2vqT7zl+\n3vozrQKtCLtwaVBQ8rP6cfOPvnV+2voTu+6yK4mByE1Q7Pc5reb41unSrguZR2eWu4Ev+X7pzEt9\nb8L36bgPD/z+gXLBcuzj6169jlVJqzz1grsFeeiUh0gMJJabCpiYEHl+yYpLeKbIZw1b/3OYdHPk\nZnfs2LGMvX5s6ctpy/xvbkf1G8Wkqyu/QU5b4V8v9lyV1i2sou5fqjjnD/71zjzgzCr7CpA227/u\n8fscz6Szqzjnp/71TtrvJCb9oZpzvu1fd0hwCNm/ya6y7qfdPuWbom88dY/ofgTXH3l9lXUBVv5v\npe+5j977aMYN94zJlLPk+SXkFeX5nvu6X19X7bnnd5vv2/fDUg5jzMAxVdZ9ocsLfFH0haduv736\nMXTvoaWH3nr0LY4403v73HvP3nxS9Imn/r577Mv+v9q/2r5DpOycojmeNnp26km3Dt2qrd99t+6R\ne8oK9VM6pFQa7MaqLEDLvr/qa0ZtVC1171Sm3z+dzLszKdxYSHKHZLLv37G123XVl3LtxFFcpzqb\n2RFAyDl3YvT5TYCLHfU1sweBGc65Z6LPFwNDnXOrK7TlOAI4BJhFJPjdJfp8PjCwku/DgJ+B2TFl\nY4/9poaPk4Dvgfdawcnbvc+rK1sETNkVEjvC6d9VUaYDJO5egzK7lQ9cn0qCc4s8/6m0mbIrW86u\nMD3lbWAInrJ7vboXa363pkZlU95KoeC33qk3v//h9zgcr+z5iue1rm91ZeVvvesAKjv+21W/BeCt\nLm95Xhu2chg4mJE8w/PaMYWRj9zfTX7X+8d1xRAcjg+6feB57fD8wzn/qvN55J5HmLu3dyrWIcsO\nAWDe3t5P6g7+9mDOufwcnrr/KRb0XOD9A/VNP06+8GSm/mcqi1ctht+Wf733V705YcwJvP7w677T\nofZbsh/H/ek43njkDZb2Wer9A7ZkX449/9jIz+uxt/imj/cPbHBRkMPTDqc4XMzHkz5mRf8V3t/F\nZ1056OyDWDBlge+ajc4LO9PvzH6EXZgvn/uSNQeu8ZTpOL8j3U7pVvope8HLBfx06E+ecq0/bk2H\nEzoQdmE2vrGRosO912/i7EQ6ndipNOBYPnU5Px35ExXt+uGu7HP6PmwPbyf3hVx+PupnT5k277eh\nx6k9SoPPZS8uY/NRmz3lOs7qyOA/Di69kX43513fqU0pn6Qw8tKR5Y69+MCLFBxa4CnbdW5XfnfR\n70qDjNcfep3Vg1Z7ynWZ24WTLjqp3KfmUx+c6ttmzwU9ueyGy0pv9O+54x6W9F/iKdf3i77cnHlz\nuWD6rr/fxdcDvvYtO3bsWM8I0RU3XsH8PvPLF54BA7sO5L5x95UbOb3+luvLpivF6L+oP3/P/nu5\nEZWb/nITC/su9JQduGQg/7rrX54RhAuvuZC5ved6yg9eOphn//2sp/ypl5zKB70+8JQfljeMd3Le\n8RyvbFrs6E2jmXSf94Z+R8s31nM09jo7U68mU6THjh3L2LFjd6hObc9V13Vbyjl3tm5LOHfF67iu\n+t7Q7z+2jXIB2k4k6FIbdauu+lLSTjyzOsd7qnMKsDzm+QpgUDVlCqLHvHeFvyGyHqBkhu+Q6PNh\nVXxPij7+TSXHavoYYBFlAWjF59WVTQJSNsGQTdWU2QhDNu5YmSSge4WgIXp8S/tN3uMBfMuucWtq\nXLZwa6Hv8bdz3458epfsfW110WrfOpUdn7sieoPrM6VqQWF0Nvze3tc+X/V5pa8t/n5x5LHP9K78\n9fnMWzmPgo0Fvv1ZtWlV5AMXn9d+2PwDazavqXTU5OetP7PrLruydftWSPC+XhwuZu/d9650OpRz\njv322I833Bu+rxtG/879MYx3eMe3TLvEdozsM5JWgVZ81forViSt8JT5Vdtfcfmgy7l52s2sTFrp\neb1Luy7cctQtBCzANa9dw5qkNZ4yvTr24uGRD5eO8qTPSvedIjWw60BeuOQFAhZg5Ocj+TDpQ0+Z\no7ofxTvXlQUoaV/5jxac0ucUJl0cuflNW+xf5rS+pzHp8rIb5LQl/uV+t9/vmHRuTLn3/csNTR3K\nhN9NKNflda+v8y37m56/4eFTHi5r8x3/No/teWy5cgAb3tjgW3Zw98FcM/ia0kPvJb/HkqIl3g9l\nuh5M2oC0cm3OTJnJ10Vf+5Y9o98ZVLT/r/ZnftH88uWLI8crTs16ssuT3ulKRTCgywBO7n1yubKT\nOk9iYdFCT9n9f7U/R3Tzjlzst+d+zC3yfihV2ahDcPcgHxR5P+RK7lDxP6iIHf3kujafdDfGczT2\nOjtTrzYjGrUdBdmZ0ROdM751de6dG9VrLH2o6kMutdFw6qovJe1MnjC5DnrlL94jvqcDxzvnLoo+\nTwMGOeeuiCnzMnCHc+6j6PO3gBucc/MrtNX0M1uJiIiIiIhIpZrqiG8B5cfrukWPVSzTvZoycfsB\niIiIiIiISPMWiHP7c4F9zCxoZknA2cC0CmWmAX+E0jXB6yuu7xURERERERGprbiO+Drnis3scuBN\nyrYzWmxmF0dedhOdc6+a2e/M7Bsi2xmdH88+iYiIiIiISMsS1zW+IiIiIiIiIg0t3lOd64SZnWBm\nS8zsazO7saH7IxLLzLqZ2TtmtsjMPjezK6LHO5rZm2b2lZm9YWa7xdS52cyWmtliMzsu5vhAM/ss\neq3/syHej7RsZhYws/lmNi36XNexNDlmtpuZPRe9NheZ2eG6lqWpiV6Xi6LX4GQzS9J1LE2BmT1i\nZqvN7LOYY3V27Ub/LUyJ1pllZhX3gPHV6ANfMwsA9wPHA/2Ac8ysT8P2SqSc7cA1zrl+wGDgsug1\nehPwlnOuN/AOcDOAmfUFzgT2B04E/m1lO7g/APzJObcfsJ+ZHV+/b0WEK4EvY57rOpam6F7gVefc\n/sCBwBJ0LUsTYmZB4ELgYOfcACLLE89B17E0DY8Rid1i1eW1+ydgrXNuX+CfwJ016VSjD3yJ7Pu7\n1DmX75zbBkwBRjRwn0RKOedWOecWRB//BCwmkp18BPB4tNjjwKnRx6cAU5xz251zy4ClwCAz6wLs\n6pyLbmDMEzF1ROLOzLoBvwNiNxPWdSxNipl1AIY45x4DiF6jG9C1LE3LRqAIaGdmrYA2RHY90XUs\njZ5z7gNgXYXDdXntxrb1PHBsTfrVFALfFGB5zPMV0WMijY6Z7Q0cBMwGOpdkKHfOrQL2ihareE0X\nRI+lELm+S+hal/p2D3A9EJv8QdexNDWpwA9m9lh02v5EM2uLrmVpQpxz64B/AN8RuSY3OOfeQtex\nNF171eG1W1rHOVcMrDezTtV1oCkEviJNgpm1J/Kp05XRkd+KmeOUSU4aLTM7CVgdnb1Q1b7puo6l\nsWsFDAT+5ZwbSGTHiJvQ/8nShJhZT+BqIAgkExn5HY2uY2k+6vLareq+pVRTCHwLgNgFy92ix0Qa\njeg0pOeBJ51zU6OHV5tZ5+jrXYA10eMFQPeY6iXXdGXHRerDkcApZvYt8DTwGzN7Elil61iamBXA\ncufcJ9Hn/yUSCOv/ZGlKDgU+dM6tjY5ovQj8Gl3H0nTV5bVb+pqZJQAdnHNrq+tAUwh85wL7mFnQ\nzJKAs4FpDdwnkYoeBb50zt0bc2wakB59fB4wNeb42dGMdKnAPsCc6LSPDWY2KLqo/48xdUTiyjl3\ni3Ouh3OuJ5H/Z99xzv0BeBldx9KERKfSLTez/aKHjgUWof+TpWn5CjjCzFpHr79jiSQe1HUsTYVR\nfiS2Lq/dadE2AM4gkiyrWq1q+UbqjXOu2MwuB94kEqg/4pxb3MDdEillZkcCo4HPzexTIlM3bgHG\nAc+a2QVAPpGMdTjnvjSzZ4n8AdsG/NmVbah9GZADtCaSkfT1+nwvIj7+D13H0vRcAUw2s0TgW+B8\nIAFdy9JEOOcWmtkTwDygGPgUmAjsiq5jaeTM7ClgKLCHmX0HhIjcTzxXR9fuI8CTZrYU+JHIB/bV\n96usXREREREREZHmpylMdRYRERERERGpNQW+IiIiIiIi0qwp8BUREREREZFmTYGviIiIiIiINGsK\nfEVERERERKRZU+ArIiIiIiIizZoCXxERaZTM7INa1hthZn3quj+1ZWZdo3sU1kVbb5nZrhWO3W5m\nx0Tf94072N6eZjbbzOZF9ySvM2aWZ2adalHvbjM7qi77IiIiosBXREQaJedcbYOfU4F+ddmXneGc\nW+mcO3Nn2zGzYcBXzrlNFV46HPgYOAZ4bweb/S3wmXPuEOfchzvbxwpcLes9ANxQlx0RERFR4Csi\nIo2SmW2Kfj/GzGaY2XNmttjMnowp839mtsjMFpjZnWY2GDgFuNPM5ptZqpmNMbM5ZvZptI3W0bqP\nmdm9ZvahmX1jZqfFtHujmX0WrXN79FhPM3vNzOaa2btmtp9Pn4+O1pkfHUVtZ2ZBM/s8+vpD0dc/\nNbM1ZpYZPX5dtI8LzCxUyY/kXGBqzLnuNLOFwKHAR8AY4AEzu9WnX0Eze9vMFprZdDPrZmYHAuOA\nEdH+7lKhTp6ZjY2+j4Ul79fMOprZi9FjH5lZ/+jxTmb2hpl9bmYPARbT1mgz+zh6ngcsIhD9HXwW\nbetKAOfcUiBoZrtV8nMQERHZYQp8RUSksYodMTwIuALoC/Qys19Hp9Ge6pzr55w7CLjNOTcLmAZc\n75wb6JzLA/7rnBvknDsYWAL8KabdLs65I4GTiQSBmNmJ0eeHRevcGS07EbjcOXcYcD2RkcmKrgP+\n7JwbCAwBtsS+F+fchdE2RwDfAzlmNhzY1zk3CDgYOLSSqb5HAZ+U/nCcuyH6XnKAw4CFzrmDnHO3\n+dSdADzmnDsQeAqY4JxbCPwVeCb6s9rqU2+Nc+4Q4MHoewPIAuZH2/oL8ET0eAh43znXH3gR6AEQ\nnXZ+FvDr6M8lDIwm8jtNcc4NiLb1WMx5FwCDffojIiJSKwp8RUSkKZgTnTLsiARFewMbgC1m9rCZ\njaQsyKyov5m9Z2afERk1jZ0G/RKAc24xsFf02LFEgsSt0dfWm1k74NfAc2b2KfAfoLPPuT4E7jGz\nDKCjcy5csUB0xPk5IkH0cuA4YLiZzQfmA72BfX3aTnbOra1wbCDwGbA/kaC+MoOBp6OPnwRqup73\nxej3eUR+5hAJwJ8EcM7NADpF1x0fDUyKHn8VWBctf2y0n3OjP7vfAD2Bb4HU6Kj78UDsFO7CmPOJ\niIjstFYN3QEREZEaiB2NLAZaOeeKzWwQkcDqDODy6OOKcoBTnHNfmNl5RNbC+rVrVC4ArIuOWFbK\nOTfOzP4HnAR8aGbHVTgHREaKn48GjSXnvcM591BVbRMzAh6dppwDdCMyctwuenw+MNhn9La2621L\n2imm6nsGv/Yt5vvjzrm/eApE3sfxwMXAmZSNxlslbYqIiNSKRnxFRKSxqioQxczaArs7514HrgEG\nRF/aBHSIKdoeWGVmiUSm2FZ3vunA+WbWJnqejtGEUnlmNirm/AM8DZj1dM4tcs7dCcwF+lR4/TKg\nvXPurpjDbwAXREeVMbNkM/uVT/8Ko9O7cc4tjE6Z/so51xd4BziuiinLHwHnRB+nAe9X8XOozvvR\nNjCzocAPzrmfiCTWGh09fiKwe7T828CokvcUXSPcw8z2ABKccy8CmUSmeZfoCuTvRB9FRETK0Yiv\niIg0VpWN+JUc7wBMLUlWBVwd/T4FeCg63XgUkaBqDrCGSPbjXSu0U65d59wb0ZHIT8xsK/AqcCuR\nYK8keVSr6Hk+q9DGVRbJvlwMLAJeA5JjXr8WKIpO+XXAg865iWa2PzDLzCASuKcRGcmN9QGRRFZv\nQmQrIsqmE/d2zn3l/+MCIuujHzOz66Ltnl9F2XI/Dx9jgUejibU2A+dFj2cBT5vZ2UQC7e8gMo08\n+jN708wCQBFwGfBLtE+B6LluijnHwdE+i4iI1AmLLJcSERGRxiw6unqWc+7Shu5LPEWzR9/lnBvR\n0H0REZHmQ1OdRUREmgDn3Exgn2giqebsEuCuakuJiIjsAI34ioiIiIiISLOmEV8RERERERFp1hT4\nioiIiIiISLOmwFdERERERESaNQW+IiIiIiIi0qwp8BUREREREZFm7f8BygdJUMe5uO8AAAAASUVO\nRK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10d784be0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "plt.figure(figsize=(16, 8))\n",
    "plt.title('CPU time of Dijkstra')\n",
    "plt.xlabel('instance size (# of nodes)')\n",
    "plt.ylabel('CPU time')\n",
    "plt.yscale('linear')\n",
    "plt.plot(log[:,0], log[:,1], 'o-', label='simple Dijkstra')\n",
    "plt.plot(log[:,0], log[:,2], 'o-', label='Dijkstra by networkx')\n",
    "z = plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "先程適当にコーディングしたdijkstraはわかりやすさのため，データ構造の工夫は施していない．\n",
    "一方で，networkxのメソッドには（おそらく）データ構造の工夫も施されている．\n",
    "これが計算時間の違いに現れている．\n",
    "\n",
    "データ構造の工夫のないコードは，枝数とは関係なく，頂点数の2乗に比例して計算時間がかかる．\n",
    "データ構造の工夫を施すと（ものすごく大雑把に言うと）「頂点数と枝数にほぼ比例」した計算時間で済む．"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}