Arbirtrage_F20.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bellman Ford\n",
    "\n",
    "Bellman Ford is an algorithm that takes in a graph with (possibly negative) edge weights and a starting vertex v and returns the length of the shortest path from v to all other vertices. If there is a negative cycle, then it will return the message \"negative cycle\".\n",
    "\n",
    "In the following implementation of Bellman Ford, we will be using an adjacency matrix. The value of the [i,j] cell of the matrix is the weight of the edge that connects vertex i to vertex j. If there is no edge between vertex i and vertex j, then we would like to set that value to 'X'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from pandas import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Bellman_Ford(G,starting_index):\n",
    "    \"\"\"G is an adjacency matrix with positive, zero or negative edge weights. cell G[i,j] = 'X' if there is no edge from i to j. Edges not in the graph are given the weight of 10^6 which will be a makeshift infinity\"\"\"\n",
    "    inf = 10000                                   #this is just some large number that will essentially act as infinity\n",
    "    si = starting_index\n",
    "    n = len(G)                                       #this is the number of vertices of G\n",
    "    B = [[0]*(n) for i in range(n)]              #this initializes the DP array called B which has rows numbered 0 to n-1 and columns numbered 0 to n-1\n",
    "                                                    #B[i,t] is the length of the shortest path from vertex starting_index to vertex i using t or fewer edges.\n",
    "    prev = [['null']*(n) for i in range(n)]           #this will initialize a prev array to all 0's which is just a place holder for now.\n",
    "    for i in range(n):                             #this initializes B[i,0]=inf meaning that the shortest path from starting_index to i using 0 edges is infinity\n",
    "        B[i][0] = inf\n",
    "    B[si][0] = 0                               #the shortest path from starting_index to starting_index using 0 edges is 0 from the                                      \n",
    "   \n",
    "    for t in range(1,n):\n",
    "        for i in range(n):\n",
    "            C = inf                                     #C will be the variable we use to compute the running minimum. We will start it out at a large number.\n",
    "            for j in range(n):\n",
    "                if G[j][i] != 'X':\n",
    "                    if C > B[j][t-1] + G[j][i]:            #this checks to see if the current shortest path from starting_index to i is longer than the path that goes through j\n",
    "                        prev[i][t] = j                   #update prev\n",
    "                        C = B[j][t-1] + G[j][i]            #update C\n",
    "            if C < B[i][t-1]:\n",
    "                B[i][t] = C\n",
    "            else:\n",
    "                B[i][t] = B[i][t-1]\n",
    "                prev[i][t] = prev[i][t-1]\n",
    "                                                              #set the value for B[i,t] and prev[i,t]\n",
    "    for i in range(n):\n",
    "        if B[i][n-2] != B[i][n-1]:\n",
    "            \n",
    "            print(\"negative cycle!\",i)                 #if any of the vertices changed their length after from t=n-1 to t=n, then there must be a negative cycle.\n",
    "    return ([B[k][n-1] for k in range(n)],[prev[k][n-1] for k in range(n)])"
   ]
  },
  {
   "attachments": {
    "image.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfIAAAEzCAYAAADKJYHBAAAgAElEQVR4Ae2dTagWR/bG9b8YFWbhx4wzajIzjO4Gw2CcjAsDAxGMutFsXIg4KH5csglZKKhhyEKJoGSRCI4Is3DhLhNF3cmEcZNFRHGRhShZiGQTDOJSpP48r3PurVt2v13dfaq6qvopeOmPt7vq1K+ePqerP6oXGCYSIAESIAESIIFsCSzI1nIaTgIkQAIkQAIkYBjIKQISIAESIAESyJgAA3nGjUfTSYAESIAESICBnBogARIgARIggYwJMJBn3Hg0nQRIgARIgAQYyKkBEiABEiABEsiYAAN5xo1H00mABEiABEiAgZwaIAESIAESIIGMCTCQZ9x4NJ0ESIAESIAEGMipARIgARIgARLImAADecaNR9NJgARIgARIgIGcGiABEiABEiCBjAkwkGfceDSdBEiABEiABBjIqQESIAESIAESyJgAA3nGjUfTSYAESIAESICBnBogARIgARIggYwJMJBn3Hg0nQRIgARIgAQYyKkBEiABEiABEsiYAAN5xo1H00mABEiABEiAgZwaIAESIAESIIGMCTCQZ9x4NJ0ESIAESIAEGMipARIgARIgARLImAADecaNR9NJgARIgARIgIGcGiABEiABEiCBjAkwkGfceDSdBEiABEiABBjIqQESIAESIAESyJgAA3nGjUfTSYAESIAESICBnBqoJPDo0SNz/Phxs3btWrNgwYLJb/fu3eb27duV23MlCZAACZDAMAQYyIfhnnSpCOLLli2bBO+ZmRlz5swZs3Xr1tmAzmCedPPROBIggZERYCAfWYP7VPfevXuTwI2Abif00NE7R8+ciQRIgARIIA0CDORptEMWVqAnjkCO3jkTCZAACZBAGgQYyNNohyysuHHjBgN5Fi1FI0mABMZEgIF8TK3do64//fST2bhx4ySQI6AzkQAJkAAJpEGAgTyNdkjSCjzkhh/ujePhN/wuXLiQpK00igRIgATGSoCBfKwt71Fvee1MpngVDYEdvXMmEiABEiCBNAgwkKfRDslbgcvpcmkdUyYSyJUAHtrEa5XyiiWmWHbf0si1frR7fAQYyMfX5p1rjJ64OL8rV650zoc7ksBQBOSBTVxlwgmpPT4CtM2rTUO1DMvtQ4CBvA+9Ee4rjg+X2JlIIDcCeMYD4yDYvW+MmyAnqHwGJLcWpb0gwEBOHbQiIIGcDq8VNm6cOAEZ7IhjJCTeUDSvkgADeSWWca+Up9VdCui5yINvdo/G3Y7LJJAbAWge2mYgz63laC8IFBnIb926ZU6ePGn2799vtm/fbjZs2GBWrVplFi5cOJlieceOHZP/T5w4YbA90xwB9Lbh1PCUOnoqcHJ4GEiCOO+Pz7EaYo761qcu+uYtI322XXKkxttRKyKQ4wGVy5cvmz179pjly5ebTZs2mU8//dRcunTJXL9+3dy5c8c8efLEvHz5cjLFMtbjf2yH7bEf9kc+fODFGARruYyOAI57iPz6WbuDS2tr6luLZHU+4Cv3yHHViSk+AWq8H/OsA/mzZ88mPe/FixebXbt2mYsXL5rHjx93IoL9sD/yWbRo0SRf5M9EAkMRoL7jkJf74+iVM8UlQI3r8M4ykL948cKcOnXKLF261Bw6dMg8fPhQh8b/ckF+hw8fnuR/+vRpg/KYSCAWAeo7Fmlj5HU03Ebilbh43KlxXdbZBfKbN29O7nPv3bvX3L9/X5eGkxvyRzmrV682KJeJBEIToL5DE57LX147w2V1XlKf4xJ6jhrXJ5xVID937tzkXvbVq1f1SUzJEeWtWLHCnD17dspW/IsE+hGgvvvxa7O3BHE8/8Eg3oZcv22p8X786vbOJpDjCfTNmzebBw8e1NUl6HqUi/JhBxMJaBOgvrWJ1udnB3G+gVHPSfsfalyb6Fx+WQTyLVu2TO6Fz5k93NzBgwcN7GEiAS0C1LcWyeZ8cB9cvhnAIN7MS2sLalyLZHU+yQfyffv2mQMHDlRbP9Ba2AO7mEigLwHquy/BdvvjFUp5nRKvV1b9eKm9HdOmranxJkL9/086kOO1kG3btvWvZYAcYBfsYyKBrgSo767kuu8ngVwGN6qa4utoTDoEqHEdjk25JBvIz58/b9avX2+ePn3aVIdB/oddsA92MpFAWwLUd1ti3D43AtR4vBZLMpBjFLYlS5aYa9euxSPRoSTYh8FoYC8TCfgSoL59SXG7XAlQ43FbLslAfuTIEXP06NG4JDqWduzYMQN7mUjAlwD17UuK2+VKgBqP23LJBfJvv/3WrFy50jx//jwuiY6lwU7YC7uZSKCJAPXdRIj/506AGo/fgskFcnyV7IsvvohPokeJsBd2M5FAEwHqu4kQ/8+dADUevwWTCuR3794169ati09BoUTYDfuZyiLwj3/8w3z00UcqlaK+VTAyE0UCmvqGWdS4YuO0yCqpQI5Pin788cctzE9nU9gN+5nKIgBHJ68o9Q3o1HdZ2iihNpr6Bg9qfBhVJBXI3377bfPNN9+oksDoTTKSExwy5kOM6AS7YT9TWQRsR9c3oIfQt9CGpvHxD/xCJOo7BNXh89TUN2qjrXG804/Py8r34jHF8qNHj9Th5azxZAL5999/b958803VxkGDw/niE4VnzpyZDOAigsCydoL9qAdTOQSqHF2XgB5C36CMIUfdQU5C0ae+Q5EdLl8tfaMG2hqXT8xKBwyj8MmxBz8e4rOzuWo8mUD+2WefmQ8//FBN0TiTEwHYmeJMToK59lkd7Ec9mMohMM3RiVPxueSurW8QxlCiOEmFHRhBS+wJRZ/6DkV2uHy19I0aaGv8woULk5NU20/bH7zB/9opV40nE8gBUPNpdeml4KzOTeL0tIUA+1EPpnII+Dg6CaDTArq2vkEYV5VwUipDioodoehT36HIDpevlr5RgxAaryIj/hs9dO2Uq8aTCeQ7d+40X331lVq7SK+7KkO5ZINgr5lgvzhTTheMlkVVQNfWN3SLnop9eVE0p6lpOy/qe7yaFm1hWqVv6CSExm39yTxOYGFHiEAOjaMeuaVkAvk777yjOqgKGhqXHauSXHbXFgIGQrAFz/lxOz7b4Wnru0rXoreq/zTWUd/j1rPoS6a2vqGvGBpHOfLsU4jnnKBx1CO3lEwgX7NmjXn8+LEKv6ZAjfssEKN2IIf9InJO6fREA3B4mvquO0ikvLr/+66nvqlp0Zg9lYAeQ+O4AiVXW0N8bhYaf+ONN/oeKtH3TyaQL1y40Lx8+VIFQFMgRyEQonYgf/HiBQP5Ajo728ktXbrU4D6kpr7rDhIpt+7/vuupb2pbNCZT0ffPP/8cReNyfxy98hBJNB4i75B5JhPIcTb3448/qtS1KZDj3iKEqB3I2WOho6tycBC1pr7rDhIpu+7/vuupb+pbNGYHcNFVaI3Ls024ZWo/GyLla0zZI+9JEfclvvvuu565vNodjQzB8R45HY84nljTKgcHVWrqu+4gkTrW/d93Pe+R83iq03dojctrZ7isHuKSuhwbvEcuJDpO8aTg119/3XHv13eb5tTkzA6XaTRTrk88ajIoLS/f13OmOTgw0dZ3Fedpmq/avu066rstsfS319I3ahpK4xLEoe+QQRx1yFXjyVxaxzuIX375pZrycdkcDV/1Hrk89ag9VGuu7yCqQS8woyZH1xTABYm2viVfexo6kFPfNu0y5rX0DRohNG4HcW1/XdWCuWo8mUCuPSoQGh2Ozb0PLsLAJRrtBCFzZDdtqsPmV+fofAO4WK+tb8nXnoYO5NS3TbuMeS19g4a2xnGLVL6TESOIow65ajyZQK49Ti8aRUSAKd45xKV0eXWhqqfe99DMdZzevvUueX/X0bUN4MImhL5xUgpdy08CuSxrOz/qW1qznKmWvkFEW+MyOid8NjpkVT/tS+25ajyZQA4haH85B2d0CN4yHjUcHcSBp9q1U85fztFmUVJ+4ui6BnCbhba+McSwBO+qad3DnrZNvvPUty+pvLbT1DdqrqlxCeRV2pZ1mr48Z40nFcj5Ldu8nMAYrP38888n74HjPdm+ifruS5D7axPQ1Ddso8a1W8gvv6QC+d27d826dev8LE9sK9gN+5lIoI4A9V1HhutLIUCND9OSSQVyINixY4fqV9BiYMWTjrCbiQSaCFDfTYT4f+4EqPH4LZhcIMcL+StXrjTPnz+PT6NDibAT9sJuJhJoIkB9NxHi/7kToMbjt2BygRwIjhw5Yo4dOxafRocSjx49OrG3w67cZaQEqO+RNvyIqk2Nx23sJAP5kydPzOLFi821a9fi0mhZGuxbsmSJgb1MJOBLgPr2JcXtciVAjcdtuSQDORCcP3/erF+/3jx9+jQuEc/SYNdbb701sdNzF25GArMEqO9ZFJwplAA1Hq9hkw3kQIB3wN9///14NFqU9Ic//MH8/ve/b7EHNyWB+QRwIrh8+fL5KxNZor4TaYiMzfj73/9ufve73yXrw7dt2zaJMRkjnjU96UAOK/ft22cOHDgwa3AKM3/9619nB+L485//bDTeMU6hXrQhDgHoBU5OBrX47W9/G6dgz1Kob09Q3KySgKvv3/zmN8n5cMQUxJZSUvKBHKC3bNliDh48mATzTZs2zTpgccQM5kk0TRZGwMnhK1GiHZmiB5xCor5TaIV8bajT969//etkfDhiyXvvvZcv5ArLswjksHv//v1m8+bN5sGDBxXVCL8K5f7xj380v/jFL15zwnDGGMKTA8KEb4ecS6hzchLMV69eTX3n3MAjt71J33/6058G9+HvvvvuJJaU1lTZBHKAP3v2rFmxYoW5evVq1HZAeSj3L3/5S2UQF0fMYB61WbIqDE7ub3/721T9rFmzhvrOqlVprBDw0TeuXA7tw8+dOycmFzXNKpCD/M2bN82qVavM3r17zf3794M2BvJHOSgP5SLZ9zYlgNtTBPP//Oc/Qe1i5nkRwJUaXDq3deLOy+0Z6juvtqW1ZnIl0lff4DW0xktss+wCORrhxYsX5vTp05PL2YcPHzYPHz5UbRvkd+jQoUn+p06dmpRnF/DRRx9Ndcpw0gzmNrHxzvsEcfTU0aORRH0LCU5TJ9BF36jT0BpPnWtb+7IM5FLJZ8+emZMnT5pFixaZXbt2mYsXL5rHjx/L362m2A/7f/DBB5PBaD755BOD/OuSfP7P7VnZy//617/qduf6ERCAk8MVGlsT7jxOCu0gbmOhvm0anE+NQF99oz5Dajw1nn3syTqQS8Xx3fHLly+bPXv2TN7LxZO3+JzepUuXzPXr182dO3cmo6+9fPlyMsUy1uN/bIft8T4v9kc+yM8nIVC7jtldxmcCmcZHAFdk+gRxmxj1bdPgfAoENPWN+gyl8RRYathQRCB3Qdy6dcucOHFi8u7i9u3bzYYNG8yvfvWrSdDFk8FYxnq8S4gePbbvmiBoN3i7y+i9M42HAE7efIJ4VyK2vl2tyTL13ZUu92siEFrfKN/WeGgf3lTfHP4vMpBXgcd9SDxQFCIxmIegmmeePk5O8yqNBG53qkmP+takmXdesfVt0wrpw+1ycpwfRSC3HRHu64RIyNd1pu4yhMhULgE4ObfN7WX00rWfm7Dzt+e1KVPf2kTzy28IfQulGD5cyspxOopAjgAqTi5UrxyN7/PwB4N5jodJs81NbzIgiP/73/9uzqjlFqJrd9oyG6/NqW8vTEVuNJS+BWYsHy7l5TYtPpDbZ3Li7OCQQqUffvhhcglfyqqahjyZCFUv5ltNAE+c+4wtECKIw6IqfWFdqER9hyKbZr5D6xtUYvvwNFtiulXhjvjp5Ub71z6TE6cXOpBC/ChDyqua4v+6146iwWFBvQig/arGTbfbO1RPXAy3y7Ln5f8QU+o7BNX08kxB36AyhA9PrzWmW1R0IK86kxNnF7JXDuQ+zg6jIaGHw5QfAR8nF6N9Rc/uNDRR6js04WHzT0XfQ/rwYVugXelFB/KqMzlxeKF75dIM02yALeixhT6pEFs41SHg4+SgrxgnaaJnd6pT0+ZcqO9mRrltkZK+p+krlg/Pof2KDeTTzuTE6cUKoD73UGPZkoMoU7YRwbnNuNKh6yJadqehy7Xzp75tGnnPp6TvWD780aNH5vjx42bt2rWzt0N3795tbt++nU1jFhvIp53JidOLeUbX9NQnbIJwmdIlgJOtpiAO3aFHEyuJlt1prPKlHOpbSOQ7TU3fMXw4gviyZcsmAXxmZsacOXPGbN26dTag5xLMiwzkPmdy4vhi9oR9nF2op5vzdS9pWA6d4DaI6KZqip5pzCAOMlV2YN0QifoegrpOmanpO5YPv3fv3iRwI6DbCT10HEfomeeQhjniA5PxOZMTBxizV45q82MrgRs/QPZwKk1BHEEsdhBHVUXH7jQABq8sqW8vTEltlKK+h/bh6InjmELvPIdUXCBvcyYnzi9mrxyiQK9byq6bag7jmYMQU7URI7H5BPGh7K/Tz1D2oFzqe0j67cpOUd8p+PAbN24wkLeTku7Wbc7kxAnG7pWjxj5i5cdWdLXRNjefcaWHbiPRsDttW1ft7alvbaL6+aWq76F9OL7EtnHjxkkgR0DPIRXVI/dxHq7Dk+XYvXKIw8de3Hdlik9gyHGl29RW9OtO2+QRalvqOxTZ/vmmqm8fzbhal+U+PhwPueGHe+N4+A2/Cxcu9AcdKYeiAnmXMzkRwRC9crSxz0MmqBdTPAJN93lxqV374yddayf6dadd89Pej/rWJto/v5T1PZQPd48fvIqGwI7eeQ6pmEDe50xOGrHPGV2fxka5Pq819SmD+zYTwMNqPu9Ep/RmgWjXnTbXNt4W1Hc81tNKSl3foXw4etbS45bptNfKcDldLq1jmkMqJpD3OZMTJzhUrxxCwUGG8sWWqin+H+LJ6ByE3NfG1J1cXf2qdIJ1qSXqe9gWyUHfoXy4vCduHysI6NMSeuKy35UrV6ZtmsR/6R3xyljsxrPnlYtRyY7OTgVj60zA3efjJ0NdsZlWIVvT9vy0fYb6j/oehnzO+gYxW9f2fGiaMjBMU9APbYdP/gzkPpQib9N0Zop7tCkGlciYVIrzcXK4EhJj3PQuFbIdmz3fJa9Y+1DfsUi/utLXdJKasr5Byta1PR+aogTyHB56YyAPrYaO+TcdfAzmHcFau/n2EFMN4qiK7djseauaSc5S3+GbpQR9h9a43DN3WwMjvsnx5I765m6bwjIDeQqtUGODz4NXeECEqT0B3wew4AxTTuJs3GnKNott1LeQ0J+Wom+QcbUtyxrU0NtGfnhKHa+eIbBjzHUpI4f74xNGGjBSzkMaxJ2mbLNtm8/41QzmNrHmeTq5ZkaxtqC+9UmXpG/QcX23LGuRQ7CWy+jIGw+58etnWnSV8pFGd6dK2UfJpum9T9QtlfeaowDpUQicnM+Qq6n3xAWBq2tZlv9zmFLfeq1Umr5BRjTtTvWo5Z8TL61n0oYI1K6Q3WWM1sRUTwBXLkoK4qipqwFZrqeQ5j/Ud/92KVHfJWm8fwvX58BAXs8muX9woIqjrpuid8P0OgGfcaVxmTe3VKeD3OoBe6nv7q1Wqr5BpCSNd2/h6XsykE/nk9y/dHbtm8THyeV6NaM0J0d9U98ugdI07tZPY5mBXINi5DxwH6xO3LIe7+oyGYMALUyqprjUnvPzBVV1wrqcE/Xt33ql6xskStS4fwv7bZn3Ee9Rx1JF4PNQy9iDedMT0QjiKY2b7iHn1zahvl9DMpoVY9A3GrNUjWsKlYFck2bkvDBQic/47JHNGrw4PHHu845y7kEcoEt2ctR39aE0Jn2XrvHqFm6/loG8PbOk9sBB7RPMc3mdqi9c1NNn1LASgjhYlRzIUT/qe/4RMTZ9j0Hj81u42xIDeTduSe3l4+zwmVRcji85+Tg5cEh5yNW27VN6IAcP6vuVKsaob9R8DBpve9y72zOQu0QyXh7zxyh8nFzqH4foIr0xOTnqe2dtUIMOStQ3jokxabyLD5gw6rpjLvuNTQQ+94ZL65mjh42edl1bi5NDsC8t1dW5tHpKfajvBZU6RxAvUd9o97FpXLTeZsoeeRtamWzb9DQrDgy8r1tCwklJUxBHT45OroTWflUH6nt+MC9Z32hxBvLmY5eBvJlRlluMYfxqn1fw0IMrNYiP2clR36+Ceen6HrPG2wQeBvI2tDLb1sfZ5TqiGa4olDZuehd5jbm3Qn1/VPRJqhwPY9a4MGiaMpA3Ecr8f58hL3ML5hiJzSeIZ950XuaP3clR314yyXqjsWvcp/EYyH0oZb6Nj7ND7yaHhJOOpiCeS100eNPJlfWxFer79aOCGn+dibuGgdwlUuiyTzDHQCopJzi5uoMa6xHgcx43vQv7Oh5d8sp5H+o759abbjs1Pp0P/mUgb2ZUzBY+D4fhCdgUU9P90DEGcbQTndycWqnvORYlzVHjza3JQN7MqKgtfN65TimY44lzn3eHSxlyta3YYjq5e/fumbVr105OHjCfYqK+U2yVfjbF1Hg/S4fbm4F8OPaDlYzgmMP47AzizRKJ5eTOnDkzr/d/+/btZuMG2oL6Hgh8oGJjaTyQ+VGyZSCPgjm9QlJ3drCv6eMnYxg/vkk5oZ3cTz/9ZLZu3ToJ4phu3LhxMp9yIAcz6rtJOfn8H1rj+ZCot5SBvJ7NKP7BZfS6AwXrce8Z9x5jJp8gXuq40m0517Vd23zqtkfARhkXLlyYbCJBPfVALvWhvoVEvtPQGs+XzJzlDORzLEY719TzjRnMcY/T57I/tmMK/7AbeuSPHj2aRZ1bIIfh1Pds82U5w0De3GwM5M2MRrGFzwNleMUnZELPf8zjpndhG9vJ5RjIwZX67qKuNPaJrfE0at3OCgbydryK3nrIj1EwiHeTVmwnl2sgB13qu5vGht4rtsaHrm+X8hnIu1AreJ+m97VxUGkPuoKePi7f1x2wWA8njHvnTPMJ1DGbv5XeUs6BHBSobz0txMoptsZj1UuzHAZyTZqF5IVAXXfwyHqt8dkZxPuJRtrDnfrmivfB8WqZ+6vbP/dAjnpR33Wtm+Z6V9uynKa1w1jFQD4M9+RL9Rnysu+Y5j7jSqMnzlRPQJyaO63fY/4/eBrd3RfLdamEQI66Ud91LZze+ip9TtNoejUIb1H9ERu+7CglUATdMfs4u66B1ieIa/X6uxNIf8/Y+i4lkKNlqe/09Q0LY2s8DyrzrWQgn8+DSw6BEONXI0DXHZxYP9Zx0x30Xot1HL127rBRSYEc1ae+O4gg8i6xNR65eirFMZCrYCw7E01n1/TkMIL4WMdN76Ki2E6utEAO5tR3F+XF2ye2xuPVTK8kBnI9lkXn5DtQSx0EPHHu8y4vg3gdwer1oZ0cBoSxH4STj6bMzMzMrq+2LK+11He67RVa4+nW3N8yBnJ/VqPfsuv41T5DrqInjnuWTO0IhHZyeKq9rgxZb4/81s76tLamvtNqD7FGdOZO5X9O+T1yaqAlATi7pvGr7Y+Z+ARxbM8hV1s2xP82d52bLHfLjXtR3+lpQDTtTtOzdDiL2CMfjn3WJTcFc/Sw//vf/zYGfX78pJ8MXOcmy/1y5d7UdzoaEE2703QsHN4SBvLh2yBbC5ruef/f//3f1MuyCOLoATF1J+A6N1nuniP3FALUt5AYdiqadqfDWpVW6QzkabVHdtY0PYXuHnyyjB4Pg3j/5hae7rR/zswBBKjv4XXgaluWh7csHQsYyNNpi2wt8Rm/Wg4+TNHTYRDXaW6bqz2vkztzAQHqe1gd2Lq254e1Kq3SGcjTao9srfF1dujhMIjrNbPt2Ox5vRKYEwhQ38PpwNa1PT+cRemVzECeXptkaRE+RPHLX/5y6j1xHIQcdlW3eW3HZs/rlsLcqO/hNGDr2p4fzqL0SmYgT69NsrPIZ9x0+wBE74ZJh4DN1Z7XyZ25gAD1PawObF3b88NalVbpDORptUd21jSNm24fePb8zp07s6trigbbTO35FG3N0Sbqe/hWs3Vtzw9vWToWMJCn0xbZWdJ033DhwoVTL7XjyXWmfgRsx2bP98uVe4MA9Z2GDmxd2/NpWJeGFQzkabRDVlbgYbWmd2wxIMw///lPg1Hb7IPPnWcw79f0Lk9Z7pfruPemvtNqf9G0O03LymGtYSAfln92pfs6Ofn4CbbHwC/uQWgvc2CY7jKwOdrz3XMc957Ud3rtb+vank/P0uEsSi6Q4yMN8oUlzPdNdsPb833zHeP+cHK4t21zdOftcdaFkW8w53jrQsx/6vKXZf8cuKUQoL6FRFpT0bQ7TcvKYa1JKpDjc4l2Y92+fbs3HTs/e753xiPLwMfJNY2b7jN+Nb4NzeRPwNa0Pe+fA7cEAeo7XR3Yurbn07U4vmVJBHJ883jr1q2TII7pxo0bJ/MM5PEFUVWi77eafXrUTT163FtnMK9qhep1tmOz56u35toqAtR3FZV01tm6tufTsXB4S5II5AjYaKALFy5MiEhQZyAfXiAIqj4PrKFH45uaHpSDFvhtcj+atmOz5/325lbUd/oasHVtz6dveTwLkwjk6JE/evRottYM5LMoBp0J4eSkQj4fo5AH5mQfTl8nYDs2e/71LbnGJUB9u0TSXLZ1bc+nae0wViURyN2qM5C7ROIvo0eMy9z2gePO9x03vek9XZSHoTGZ6gm4bSLL9XvwHxCgvvPRgWjaneZTg/CWMpCHZ5xdCTGcnEBBoHYPUHcZo2sxVRNwWcly9dZcCwLUd146EE2707xqEdZaBvKwfLPL3Wdcae2x0uFY3YPUXdYuM7uGqTHY5STLNZuPfjX1nZ8ERNPuNL+ahLOYgTwc2+xy9nFyoXrHPsEcD8kxzSfgOjdZnr8Vl0CA+s5TB6Jpd5pnbcJYzUAehmt2uTbdr8b98tD3q/HwUdN9eQ7pOl9arnOT5flbcYn6zlcDoml3mm+N9C1nINdnml2OTU+QI7jGeoKcwbydfFznJsvtcil7a+o77/YVTbvTvGula1klposAABr9SURBVD0DuS7PrHLDu99N73THDOICz3eADtl+zFPXucnymJlI3alvIZH3VDTtTvOula71DOS6PLPJzWdISgRx3LseIsE+fmylmbzr3GS5ec+yt6C+y2lf0bQ7LaeG/WuSRCDHgDAYZ11+8tGUmZmZ2XVdq+o2vix3za+E/XycHEZz8xlyNSQP2Nk0PnvVR1pC2pRa3qJndzqEnRjUCcfssmXLJm8hYIple7CnGHZR3zEoxyvD1bYsx7Mg/ZKSCOT4ypk0Tt20qzOoyy9m01y5csXs3r17to44UcFJC05gYief4Nj08ZPYNjcFc1w5wL31MaYU9A3uOIYlgMsJuAzshPWxtE59l3cUpKLxlMkmEchDAhpaBMePH58EcAneWBaHB0cXM6GH3TRueqrfBve5lz/GYD60vkW/ErRv3LghqyZT0T+Ce+hEfYcmPEz+qWh8mNr7lcpA7sep81ZwYPIxGMkEVxckmGt8c13ynTZFkGsK4uj5okeTamp6+hgH/FD39IdiloKTkytq+Gqhm9ATh43Qe8hEfYekO2zeKWh8WALNpTOQNzMKsoX0YDS+8NZkIJwcLj/XHRBYjx5vykFc6tj0PjDqEvp9d7ElhWldm8a0DSeqsAO3i6qSfJY41Ekr9V1FvZx1KWg8dZoM5AO1kDi30IEcPdSmIN734yexEfoE81Aj0E2rK3qf8qBm6B6o2JGCk0MAhx14FqQqhTxppb6riMdfBz8mVxnxPJBmSkHjmvUJkRcDeQiqDXnC4UGcVZciG3Zt9Td6pj5BvFWmiWwMB153gMt6BPyYSe4HS/kxypay3GmMsqWMpkAtD3pqn7RS33H1Le1dNZWOCXQIPWgmV9uyrFlG7nkxkEdoQTgwebVOnB6mXZ/E9zHZZ1zp2IHOx+4226QUzNGWcDB4JiKmo5Gy3Gkbjn23FU3XBWrpsdf936V86nvBRGcpHMPSMRHtM5B3UXS/fRjI+/Hz2lscme1s0UvRdGy2IXBydlnuPHrppdxHxv1Rt37ucozx2cWJSUCHDTGSW1dZjlG2lNEUyIWNlt6p71dBXNo6hr6lraumuJ2EH9oXNjGQV1EKuy6Otwlbh6m5i9jd6dSdAv4JR28Hdvd1nb5FN90/LimICyufh51COjt5ahuX1pFEa2JfyKmU5U5DlunmLbcUYtwjp77nB3Fp95D6dtvbXpYHHeHHGMhtMnHnGcjj8p4tTYI5zmQ1Ep4493nXOtbHTzTq1CYP33eI2+Tpuy16IHjQRwY9Eefqu3+f7aQsd9onz7b7ipYxrUpy/1T4VG3TtI769hsDoomj5v9oT+heeuAM5Jp02+XFQN6Ol9rWIno44L5p7E5O+IFD7PHZpR3tICZBVewKOZWy3GnIMt28hUHVw5tyq6HPCSv1/Yr4EPp229pelhM4tD+S6EACu71tn3lX27LcJ8/S9u0fRRInIo3uToc2W0SPM9o+CQf3zp07Zy/nuvXEcgrjpvepY5t9fZydJg8ELwQpu7cpbdDG7q7bSlnutGt+XfcDA9ggTl3ykfvj7qBI8n/TlPqeTyi2vueXPreEEzT4LvtVM/FpDORznGLNMZAHJg1HXzUQhrySA0fXNfk4udTGTe9a17b74Z6hG9zsZTwrgHvrfZI8reveG5Zy+uTtu6+U5U5999faDvdIYQOcOzSN3hocOtZV9dR9yqW+6ymF1jfaE21o/2ydywkaArokBnIhEX/KQB6YORwbnBkCtxwU0nuBg7N7cm1MwT3h2JeR29iXwrZNVyr6BnO0I35ukqDqrg+xLGW50xBlNeUJRy7BG/aADTTfRePUdxNt03glro++paNh60p62nK7xO2EMJA3t1moLRjIQ5H9X74QPQQvwRsHBgJ4VweHbNGTzH3c9MDYZ7NvegAQ7YH30dsm6Y3bJ2hyoibOD8tdLyn72iNluVPf/VPcjvr2b5VQ+p5mgfTG8baCaB5TWS8ncFpv5LjaluVpNo7tPwbyzFrc51Ur9ERxWZLpFQGfj620fZpfXrsRp1I37fsMRFMb1pXbtF+q/1Pf7VsmhL6nWVHVW6/SIbbTSFV5Yx3THIHiaZQkghLHlZ6TYti5pvePoROtQXJEc2Fr9Cp3KcudxihbuwzquzvRmPqus5KX1uvIhF/PQB6esUoJ6DHinpfrsO1lnJkz1RNAoLZ5Vc1j1LC+SfLtm4/P/lKWO/XZN6VtqO/+rRFL33WWMpDXkQm/noE8POPeJYxhXOnekDwziDE+Oy6nh76kLtV1A7gsy/85TKlvvVaKoe86a2WEQ61L6lKOaNqdyv+cGsNAnrgKmsaVhrg1epGJY1A1z8fZ4SGiHJLr3GQ5B9thI/Wt31Il6Rt0RNPuVJ9cvjkykCfcdk33vXCpXeu+bsIYgpjm81DVUONXt6mw69xkuU0eQ21LfYcjX4q+QUg07U7D0csvZwbyRNus6UlUBPG2T1onWtXBzCrB2bnOTZYHg+pZMPXtCarHZiXoG9UXTbvTHmiK25WBPLEmxWtjTe+GMojrNRp45zywjuvcZFmPkG5O1Lcuz6bcctc36ieadqdNdR/T/wzkCbU2Djqf0chwD4xJj0DOzs51brKsR0cvJ+pbj2WbnHLWN+opmnanbRiUvi0DeSIt7OPkxjpueowmAv+m8asxmh4uVw6Rmq4auE6uannIe/7U9xCqmSszdX3PWfr6XJWWsY5pjkDxNHIQgc9BxiA+J9qQc03BHLc1hgjmKLNOy77rh7qSQ32HVGy7vFPV97Ra1Ol72j5j+4+BfOAWh4NuGjcdQRzOkCkOAZ9nFIYIin165UP1xqnvOJptU0qq+q6rAwN5HZm59Qzkcyyiz/k4OThgBvHoTWOanqqGc4kdzPv0ymPbihajvuPr1rfEFPVdZzsDeR2ZufUM5HMsos7ByeEybZ1IsR5nzgziUZtlXmFN7zmjjWK/x9+lVz5Eb5z6nielJBdS1HcVqDofWbXtWNcxkA/Q8ugdNQVxnDEziA/QOE6RPs4u5sh6XXrlsXvj1LcjooQXU9N3FSoG8ioq89cxkM/n0WsJgbeph4b/fYJ4L0O4syoBBKY6ZyLr4RCnJQTgH374Ydom3v+16ZVr9sapb+8mymrD1PTtwpNjzJ262415mYFcsfUx0hrEVtcDQs+tKYjH7N0pVr34rPo4O7nMjKssGqlNr7xOi13soL67UMtjn5T07RJzA7gsu9uNeZmBXLH17cFc4Gzt1PRxCAT4pt68nR/n4xPwCaBuDxi9cHkrAW2slXx65a4tfcumvvsSTHv/lPRtk5LA7U7tbcY+z0CupAA4bFtocNoSzJvuQ2Fbjpuu1BCBs0Gbor3stnbnJYDiUrQbcLVO1nycrmZvnPoOLKxEsk9F3zYO9/iSZXubsc8zkCspoCpYw+HbvRgRoD1lEFdqgIjZ2L1suy3teQTwqrbHmwhayT1JsMuXkwmtsqhvLZLp55OKvoWUrWt7Xv7nlN8jV9PANKdqi8+eZxBXwx89o6rett22dfNoc+yrkab1yjV747CV+tZosXzySEHfQqvuWJL/OWUgV9GAz4Mirhhx3xRnvkz5Eujq7DQfaKwKsNq9ceo7X432sTwFfcN+13fKcp+6lbYvL60rtGjTkIciPJnC+TKIK4BPJAsETmlbnylO4rRSVa9cuzdOfWu1Vp75DKlvEKs7pvKkGcZqBvKeXHHWisuldWJz1yOIYx+msghU3Q93295e1jyRs3vl2r1x6rssnXatzZD6to8be75rXUrcj4G8Z6vKu7W2wKbNazvanuZzdyUCTa8XuprQeqcc5tu9cu3eOPWtJJDMsxlS3+6xI8uZI1U1n4G8J862Z6oQoeaTyz3N5+4KBNo6OWgAV3E0E3rlIU4SqW/NVsozr6H1LYHbneZJM4zVDOQ9uOLyqCsu32XNHlmPKnDXngR8htyt04TWO+WoAnrl2r1x6runOArYPQV91x0/BeBVq0KRgfzWrVvm5MmTZv/+/Wb79u1mw4YNZtWqVWbhwoWTKZZ37Ngx+f/EiRMG23dJVe/W1omuar2mI+9iP/fpRwCXnds8H+FqAL3dLon67kKN+7QlMJS+YWcsjbdlkur2RQTyn376yVy+fNns2bPHLF++3GzatMl8+umn5tKlS+b69evmzp075smTJ+bly5eTKZaxHv9jO2yP/bA/8kF+PkmG3nQdtM8yAgAuhWo+9ORjM7fRI4CrKj5tPW0bn/anvvXajDn5E4ilb1g0lMb9aaS9ZdaB/NmzZ5Oe9+LFi82uXbvMxYsXzePHjzsRx37YH/ksWrRoki/yr0ttHwKCM0fgx8GBS6B8cr2ObH7roQVcnbGfHp8WvO3/cP+xLlHfdWS4PiaBUPpGHYbUeEyGocvKMpC/ePHCnDp1anJZ89ChQ+bhw4eqnJDf4cOHJ/mfPn3aoDw3+bxbK71uOHncw2QqnwBO0BCcfR8Sq3qnnPouXye51lBD36h7ChrPtQ2q7M4ukN+8eXNyn3vv3r3m/v37VXVSW4f8Uc7q1asNypU07d1aBG84cdz/Zq9biI13it4MrsJMuw1jX16nvserlRxr3lbfqGMKGs+R9TSbswrk586dm9zLvnr16rQ6qf+H8lasWGHOnj07yRvilcujbq+bwVsdfzEZ4qoMeut4NkL0g6m8jkh9F9PUo6xIk74BJRWNl9ZA2QRyPIG+efNm8+DBg0HaAOWifNiBHjd73YM0Q1GF2r0Z6ruopmVljJl8mlmuRgFIShovrYGyCORbtmwxuBeeQjp48GCQgTdSqBttGIYA9L1v375hCndKpb4dIFxUIYCrUCn5cBxzJaXkAzkc3IEDB5JiDntScbxJgaExrQlQ362RcYfMCFDj4Rss6UB+/Phxs23btvAUOpQAu2AfEwl0JUB9dyXH/XIhQI3HaalkA/n58+fN+vXrzdOnT+OQaFkK7IJ9sJOJBNoSoL7bEuP2uRGgxuO1WJKBHKOwLVmyxFy7di0eiQ4lwT4MRgN7mUjAlwD17UuK2+VKgBqP23JJBvIjR46Yo0ePxiXRsbRjx44Z2MtEAr4EqG9fUtwuVwLUeNyWSy6Qf/vtt2blypXm+fPncUl0LA12wl7YzUQCTQSo7yZC/D93AtR4/BZMLpDjq2RffPFFfBI9SoS9sJuJBJoIUN9NhPh/7gSo8fgtmFQgx8hA69ati09BoUTYzfHUFUAmlgXGycegFhqJ+tagyDw0CWjqG3ZR45qt459XUoEcnxT9+OOP/a1PaEvYDfuZyiIARyfDqfYN6NR3WdoooTaa+gYPanwYVSQVyN9++23zzTffqJG4ffu2mZmZMcuWLZs4Y0yx/OjRI7UyJCPYDfuZyiJgO7q+AV1b3y7pCxcuzJ50YF4zUd+aNNPJS1PfqJWmxvGNcjnmqqZXrlxRBZmzxpMJ5N9//71588031Rrmxo0bs8EbgxKcOXPGrF27dnYdRKKdYD/qwVQOgSpHJ06lTQ9dW98uYZycygkr7IPetRP1rU10+Py09I2aaGscHTFoGX5769atr/3wv3bKVePJBPLPPvvMfPjhh2rtgh4JArgbsDdu3DgRh3aPBYbDftSDqRwC0xxdm4CurW+XMK40wR6Zhgjk1LdLPf9lLX2DhLbGJZCH0HJdy+Wq8WQCOQDGeFodogjVY4H9qAdTOQR8HJ1PQA+pb/TGJYhT3+VoL0ZNtPQNW7U1PkQgz9WHJxPI8VnQr776Krh20UsPFchhvzh1TheMlkXVJfeQ+t69e/fksjoCeshATn2PV9O2P6vSNxy3tsaHCOTQOOqRW0omkL/zzjvBB1W5d+/exOHhXmKIB94wEIIteM6P2/HZDi+Uvl1nFzKQU9/j1rPrz2x9I/Bpa1y0jfvj0DV+uCUKPx4qQeOoR24pmUC+Zs0a8/jxY1V+0kOBAOTeIR6cgEBCJNjvip3LdH5weCH0DQ3DyeHEVJ4FCRnIqW9qucqfSUDX1rjcMqoqE7oXzWv6cmj8jTfe0MwySl7JBPKFCxealy9fqlZazuhsIeBhN+3XFsToFy9eMJAvoLOz9bZ06VKD+5Ah9C1vZtgPboYM5NQ3tW1rG/Oi759//jmIxt3eNzQvDywjmGsn0bh2vqHzSyaQ42zuxx9/DFZfnL0hgMsrOrhXrp3YY6GjE0dnOzjoLIS+cXUJPzuFDOTUN/Vdp+9QGre1LfPw5WKH9i1S9siFcscp7kt89913Hff2383upWuLgPcQ6ejcAC7K1NY3TkrhzNyrSyEDOfVNfdfpGzrX1rgcO1VT9Mahf+3bpLxHXkW7xTo8Kfj111+32KP7pnI2py2CXJ947E6y/D19X8+Z5uBASVvf6Inj6hICt/0TB4cp1ruXJvu0GPXdh16a+2rpO4TGpxETndOHv6KUzKV1vIP45ZdfTms7tf8kkGs6ORiX6zuIamALzKjJ0TUFcEGirW+5RSRarpva98/Flq5T6rsruXT309I3aqit8WnURP/aV1Vz1XgygVx7VCC8W4sHI9wExwan595bdLfrsgwhc2S3LuTS3afO0fkGcKmZtr4lX3ca8tI69e3Szn9ZS98gEUvj8gYSeuXaKVeNJxPItcfpRSBHwMYTjnLpUS7H4GxOuzcOQeU6Tq/2wVBSfq6jaxvAhYW2viVfdxoykFPfLu38l7X0DRLaGoe/xk/8N6byxDqmIV4/y1XjyQRyCEH7yzl2w0svHGdz2pdjYHvOX87J3x2Fq4E4uq4B3LZMU992vva8XHHSvKSO/Klvm3I585r6BhVNjeOKKgK5XEa3O2YhgnjOGk8qkPNbtuU4iFJq8vnnn0/eA8d7sn0T9d2XIPfXJqCpb9hGjWu3kF9+SQXyu3fvmnXr1vlZnthWsBv2M5FAHQHqu44M15dCgBofpiWTCuRAsGPHjihfQdPEjScdYTcTCTQRoL6bCPH/3AlQ4/FbMLlAjhfyV65caZ4/fx6fRocSYSfshd1MJNBEgPpuIsT/cydAjcdvweQCORAcOXLEHDt2LD6NDiUePXp0Ym+HXbnLSAlQ3yNt+BFVmxqP29hJBvInT56YxYsXm2vXrsWl0bI02LdkyRIDe5lIwJcA9e1LitvlSoAaj9tySQZyIDh//rxZv369efr0aVwinqXBrrfeemtip+cu3IwEZglQ37MoOFMoAWo8XsMmG8iBAF8oe//99+PRaFHStm3bJva12IWbksA8AtT3PBxcKJAANR6nUZMO5ECwb98+c+DAgTg0PEuBPbCLiQT6EqC++xLk/qkToMbDt1DygRwItmzZYg4ePBiehkcJsOO9997z2JKbCAGMpIczc4xvj9GZ8MMQutpfLpLycptS37m1GO1tS4Aab0us3fZZBHJUaf/+/Wbz5s3mwYMH7WqotDXKfffddyd2KGU5imwQxGWIRQRyd8hFBvNXMqC+R3E4jLqS1Hi45s8mkAPB2bNnzYoVK8zVq1fDEanIGeWh3HPnzlX8y1XTCODjNPjAgR2wMU6yfPwAPXOmVwSobyqhdALUeJgWziqQA8HNmzfNqlWrzN69e839+/fDUPlfrsgf5aA8lMukRwAfRJDL7Hq55p8T9Z1/G7IG0wlQ49P5dPk3u0COSr548cKcPn3a4ItUhw8fNg8fPuxS99p9kN+hQ4cm+Z86dWpSXu3G/KMTAfTQGcir0VHf1VxCrMXVIXl2A7eAmOIQoMZ1OWcZyAXBs2fPzMmTJ82iRYvMrl27zMWLF83jx4/l71ZT7If9P/jgg8lgNJ988olB/kxhCFy5cmUSyHHPnKmaAPVdzUVzLR7ClBNKTJniEqDGdXgXoVycVV++fNns2bPHLF++3GzatGnyOb1Lly6Z69evmzt37kxGX3v58uVkimWsx//47B62x37YH/mE+NatTnOVkwsCOByn9nezyyE0VxPqe46F5hwexIQGZ2ZmZoO5Zv7My58ANe7PqmrLIgK5W7Fbt26ZEydOTN4/3759u9mwYYNZvXr15GDFFMtYj/fB0aPH9kzxCMj9cVzSZGpPgPpuz6xqDwngEtDZI6+iNMw6arwd9yIDeTsE3LovAfSqz5w5M+9nP6Vu52+/joYn2plIYAgC0B4CNy6tI2GegXyIlmCZGgQYyDUojjwPeU9cnCGmCOxuwuUzee0M98iZSGAoAjKegdxGE+0OZQ/LJYE+BBjI+9Djvt4E7CDO++Le2LhhAALyxoR9sslAHgA0s4xGgIE8GurxFmQHcdyXZCKBIQngqhCez5DeOGxhIB+yRVh2XwIM5H0Jcv9GAvJQEYN4IypuEJiAvPbo3tphIA8MntkHJcBAHhQvM8dldHGSuC9Z9XOdKqmRQCgC6IlXvS0hGg1VLvMlgZAEGMhD0mXek/fExUnWTe17lURGAqEISG8c4/u7b1mINrGez3CEagHmG4oAA3kossyXBEggKQL21SEJ3FVTDtWaVLPRGA8CDOQekLgJCZBA2QQkoJddS9auVAIM5KW2LOtFAiTgTYCB3BsVN0yQAAN5go1Ck0iABOISwOV0XlKPy5yl6RFgINdjyZxIgARIgARIIDoBBvLoyFkgCZAACZAACegRYCDXY8mcSIAESIAESCA6AQby6MhZIAmQAAmQAAnoEWAg12PJnEiABEiABEggOgEG8ujIWSAJkAAJkAAJ6BFgINdjyZxIgARIgARIIDoBBvLoyFkgCZAACZAACegRYCDXY8mcSIAESIAESCA6AQby6MhZIAmQAAmQAAnoEWAg12PJnEiABEiABEggOgEG8ujIWSAJkAAJkAAJ6BFgINdjyZxIgARIgARIIDoBBvLoyFkgCZAACZAACegRYCDXY8mcSIAESIAESCA6AQby6MhZIAmQAAmQAAnoEWAg12PJnEiABEiABEggOgEG8ujIWSAJkAAJkAAJ6BFgINdjyZxIgARIgARIIDoBBvLoyFkgCZAACZAACegRYCDXY8mcSIAESIAESCA6AQby6MhZIAmQAAmQAAnoEWAg12PJnEiABEiABEggOgEG8ujIWSAJkAAJkAAJ6BFgINdjyZxIgARIgARIIDoBBvLoyFkgCZAACZAACegRYCDXY8mcSIAESIAESCA6AQby6MhZIAmQAAmQAAnoEWAg12PJnEiABEiABEggOgEG8ujIWSAJkAAJkAAJ6BFgINdjyZxIgARIgARIIDoBBvLoyFkgCZAACZAACegRYCDXY8mcSIAESIAESCA6AQby6MhZIAmQAAmQAAnoEfh/6xTYrbBYLngAAAAASUVORK5CYII="
    }
   },
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an example graph to try it on:\n",
    "\n",
    "![image.png](attachment:image.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <td>0</td>\n",
       "      <td>X</td>\n",
       "      <td>3</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>4</td>\n",
       "      <td>X</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>1</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>-1</td>\n",
       "      <td>-4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>2</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>0</td>\n",
       "      <td>X</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>-2</td>\n",
       "      <td>X</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>4</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>5</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>-3</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "      <td>X</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   0  1   2  3   4   5\n",
       "0  X  3   X  X   4   X\n",
       "1  X  X   2  3  -1  -4\n",
       "2  X  X   X  X   0   X\n",
       "3  1  X   X  X  -2   X\n",
       "4  X  X   X  X   X   4\n",
       "5  X  X  -3  X   X   X"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "G_example_1 = [['X',3,'X','X',4,'X'],\n",
    "            ['X','X',2,3,-1,-4],\n",
    "            ['X','X','X','X',0,'X'],\n",
    "            [1,'X','X','X',-2,'X'],\n",
    "            ['X','X','X','X','X',4],\n",
    "            ['X','X',-3,'X','X','X']]\n",
    "DataFrame(G_example_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use DataFrame feature of pandas to make the adjacency matrix a little easier to look at."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we run Bellman_Ford on the example starting at 0, it will return two arrays. The first array is the lengths of the shortest paths for vertices 0,1,2,3,4,5 and the second array is the previous pointers so that you can reconstruct the path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0, 3, -4, 6, -4, -1], ['null', 0, 5, 1, 2, 1])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Bellman_Ford(G_example_1,0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exercise 1:\n",
    "\n",
    "What is the length of the shortest path from 0 to 5 in G_example_1?"
   ]
  },
  {
   "attachments": {
    "image.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAe0AAAEXCAYAAACAvRyEAAAgAElEQVR4Ae1dT+gWxxnWHqpCD/5pbTVJW6q3YijGph4MFCIY9aK5eBCxKP4jl5CDghpKDkoEJYdEsCL04MFbGkW9SUO95BCJeMhBlBxEcgkG8Sgy5fnk/f3mG3e/nd1959/uM/Axu/vNzrzzvM++z87+mV1gmIgAESACRIAIEIEiEFhQhJU0kggQASJABIgAETAUbZKACBABIkAEiEAhCFC0C3EUzSQCRIAIEAEiQNEmB4gAESACRIAIFIIARbsQR9FMIkAEiAARIAIUbXKACBABIkAEiEAhCFC0C3EUzSQCRIAIEAEiQNEmB4gAESACRIAIFIIARbsQR9FMIkAEiAARIAIUbXKACBABIkAEiEAhCFC0C3EUzSQCRIAIEAEiQNEmB4gAESACRIAIFIIARbsQR4Uy8+HDh+b48eNmzZo1ZsGCBZPfrl27zO3bt0M1yXqJABEgAkSgIwIU7Y7ADWE3CPayZcsmQn3kyBFz5swZs2XLljnxpnAPwcvsAxEgAkNCgKI9JG+27Mvdu3cnIg3xthNG3hh1Y8TNRASIABEgAvkgQNHOxxfZWIIRNkQbo24mIkAEiAARyAcBinY+vsjGkhs3blC0s/EGDSECRIAIzCNA0Z7HgkvGmJ9++sls2LBhItoQbyYiQASIABHIBwGKdj6+SGYJHkDDD/ey8WAafhcuXEhmDxsmAkSACBCBagQo2tW4jGqrvOolOV7/gohj1M1EBIgAESAC+SBA0c7HF1lYgkvicnkcORMRKBUBPFCJVxnltUbkWHfflii1f7R7nAhQtMfp95m9xghbAt2VK1dmluWfRCBHBORhSlw9wsmnPf8AuM2rSDl6jTb5IEDR9kFphGUkyOEyORMRKA0BPJOBeQbsUTXmJZCTUT6zUZpHaa8gQNEWJJhPISCizeA2BQtXCkdAJg7iHASFO3LE5lO0R+x8eWrchQAjEnkozR6puOW4TgRKQwCcB7cp2qV5jvYKAkWL9q1bt8zJkyfNvn37zLZt28z69evNqlWrzMKFCyc51rdv3z75/8SJEwblmeYRwCgaAQxPi2MEgoCGB3VEsHk/ex6rFEvktz7qwm/e9tHHtkuN5Hh71IoSbTw8cvnyZbN7926zfPlys3HjRvPJJ5+YS5cumevXr5s7d+6Yx48fmxcvXkxyrGM7/kc5lMd+2B/18GEUYyDMcikcYo17fvzKV/sDSWMP8lsDxfo6gK/c08bVJKb4CJDj/TEvQrSfPn06GVEvXrzY7Ny501y8eNE8evSoU++xH/ZHPYsWLZrUi/qZiEAqBMjvOMjL/WyMtpniIkCO6+GdtWg/f/7cnDp1yixdutQcPHjQPHjwQK/nxkzqO3To0KT+06dPG7THRARiIUB+x0LaGHkFDLeCeIUtHu7kuD7W2Yr2zZs3J/el9+zZY+7du6ffc6tG1I92Vq9ebdAuExEIjQD5HRrh+frlVS9cGudl8XlcQi+R42EQzlK0z507N7n3fPXq1TC9rqkV7a1YscKcPXu2pgQ3E4H+CJDf/TH0rUEEG89rULB9Uetfjhzvj2FdDdmJNp4E37Rpk7l//36dzUG3o120DzuYiIA2AuS3NqL19dmCzTch6nHS/occ10Z0ur6sRHvz5s2Te9fTJqZZO3DggIE9TERACwHyWwvJ5npw31rm0KdgN+OlVYIc10Kyvp5sRHvv3r1m//799ZYm+Af2wC4mItAXAfK7L4Lt9sdri/IKI15prPrxcnk7TJtKk+NNCOn8n4Vo41WMrVu36vRIuRbYBfuYiEBXBMjvrsh1309EWyYKqsrxFTAmHQTIcR0cfWpJLtrnz58369atM0+ePPGxN3oZ2AX7YCcTEWiLAPndFjGWLw0Bcjyux5KKNmYvW7Jkibl27VrcXrdsDfZhYhfYy0QEfBEgv32RYrlSESDH43suqWgfPnzYHD16NH6vO7R47NgxA3uZiIAvAuS3L1IsVyoC5Hh8zyUT7W+++casXLnSPHv2LH6vO7QIO2Ev7GYiAk0IkN9NCPH/0hEgx9N4MJlo4+tbn3/+eZped2wV9sJuJiLQhAD53YQQ/y8dAXI8jQeTiPZ3331n1q5dm6bHPVuF3bCfaVgI/POf/zQffvihSqfIbxUYWYkiApr8hlnkuKJzWlaVRLTxmcyPPvqopal5FIfdsJ9pWAggqMlrQX3Fm/weFjeG0BtNfgMPcjwdK5KI9ltvvWW+/vpr1V5j1iOZAQnBF8shZkKC3bCfaVgI2EGtr3iH4LegDU7jwxf4hUjkdwhU09epyW/0RpvjeGcen0yV750jx/rDhw/VwSud49FF+/vvvzdvvPGGqiPgXARafHbvzJkzk8lQxPlY106wH/1gGg4CVUGti3iH4DdQxrSc7oQhodAnv0Mhm65eLX6jB9ocl8+mymALs9fJsYc4HuJTqiVzPLpof/rpp+aDDz5QYy/O0MTZdqU4QxPh1j5bg/3oB9NwEJgV1CSA+Fw21+Y3EMZ0mzghhR2YeUrsCYU++R0K2XT1avEbPdDm+IULFyYnpHactj/2gv+1U8kcjy7aAEvzqXEZfeBszU0S4LSdDvvRD6bhIOAT1EQsZ4m3Nr+BMK4W4QRUpt0UO0KhT36HQjZdvVr8Rg9CcLwKGYnfGHlrp5I5Hl20d+zYYb788ks1H8houqpCuewCYddMsF8CJ/MFo8WiSry1+Q3eYgRiXyIUzmly2q6L/B4vp4VbyKv4DZ6E4LjNP1nGySrsCCHa4Dj6UWKKLtpvv/226gQlcCouHVYluXSu7XRMKmCTm8vjDnJ2cNPmdxWvhW9V/2lsI7/HzWfhl+Q2v8GvGBxHO/KsUojnksBx9KPEFF20X3vtNfPo0SMVrJpEGfdFQDxt0Yb9QmjmDHDCAQQ3TX7XHSTSXt3/fbeT3+S0cMzORbxjcBxXluQqaohPqILjr7/+et9DJcn+0UV74cKF5sWLFyqdbRJtNALSaYv28+fPKdoLGNjsgLZ06VKD+4aa/K47SKTduv/7bie/yW3hmOTC759//jkKx+V+NkbbIZJwPETdoeuMLto4S/vxxx9V+tUk2rgXCNJpizZHIgxqVcEMpNbkd91BIm3X/d93O/lNfgvHbLEWXoXmuDyLhNue9rMc0r5GzpF2CxRxH+Hbb79tsUd9UTgU5OI9bQYZCTKx8qpgBqZq8ruO+dLHuv/7buc9bR5PdfwOzXF51QuXxkNcFpdjg/e0BQmPHE/sffXVVx4l/YrMCmByxoZLLZqp5CcPNXEYUl2+r8TMCmbAQ5vfVRjP4nxV+bbbyO+2iOVfXovf6Gkojotgg98hBRt9KJnj0S+P4x2/L774Qo3luPQNJ1e9py1PH2pPZ1ryO35qwA+soqag1iTWAoc2v6VeOw8t2uS3jfYwlrX4DTRCcNwWbO14XeXBkjkeXbS1Z9OBgxHE3PvWQgJcZtFOIC1nRNNGNW19dUHNV6zFem1+S712Hlq0yW8b7WEsa/EbaGhzHLc55bsRMQQbfSiZ49FFW3veWjhAHI4c7/Thcri8LlA1Au97GJY8b23fvg91fzeotRVrwSUEv3ECCl7LT0Rb1rUDHfkt3hxOrsVvIKLNcZnVEjEbg6+qn/bl8pI5Hl204XTtL8TgTA1CLfMzI6iBCHi6XDuV/oUYbTyGUp8Eta5ibeOgzW9MwytCXZXXPYhp2+S7TH77IlVWOU1+o+eaHBfRruK2bNOM5aVzPIlo81usZR3wY7D2s88+m7xnjfdQ+ybyuy+C3F8bAU1+wzZyXNtD/vUlEe3vvvvOrF271t/KjErCbtjPRATqECC/65Dh9qEgQI6n82QS0UZ3t2/frvq1rxgQ4olD2M1EBJoQIL+bEOL/pSNAjqfxYDLRxsvtK1euNM+ePUvT85atwk7YC7uZiEATAuR3E0L8v3QEyPE0Hkwm2uju4cOHzbFjx9L0vGWrR48endjbcjcWHzEC5PeInT+SrpPj8R2dVLQfP35sFi9ebK5duxa/5y1ahH1LliwxsJeJCPgiQH77IsVypSJAjsf3XFLRRnfPnz9v1q1bZ548eRK/9x4twq4333xzYqdHcRYhAlMIkN9TcHBlgAiQ43Gdmly00V28Y/3ee+/F7blna3/84x/NH/7wB8/SLEYEXkUAJ33Lly9/9Y8MtpDfGTihcBP+8Y9/mN///vfZxvCtW7dONKZwmOfMz0K0Yc3evXvN/v375wzLYeFvf/vb3KQWf/nLX4zGO7w59Is2xEEAfEFAkwkifve738Vp2LMV8tsTKBarRMDl929/+9vsYjg0BdoypJSNaAPUzZs3mwMHDmSB78aNG+eCrQRdCncWrinCCAQ0fA1JuCM5RrY5JPI7By+Ua0Mdv3/zm99kE8OhJe+++265INdYnpVow8Z9+/aZTZs2mfv379eYHHYz2v3Tn/5kfvnLX74ScBF4Mc0lJ1cJ64PSa68LaCLcq1evJr9Ld/KI7W/i95///OfkMfydd96ZaMkQ3ZSdaAPks2fPmhUrVpirV69GxRztod2//vWvlYItQZfCHdUtRTWGgPb3v/99Jn9ee+018rsor9JYQcCH37gimTqGnzt3TkweXJ6laAPlmzdvmlWrVpk9e/aYe/fuBQUe9aMdtId2kex7kSLWdg7h/u9//xvULlZeFgK4AoPL3zZP3GW5xUJ+l+VbWmsmVxh9+Q28UnN8qD7LVrQB+PPnz83p06cnl6QPHTpkHjx4oOoH1Hfw4MFJ/adOnZq0Zzfw4YcfzgzACMgUbhux8S77CDZG4BipSCK/BQnmuSPQhd/oU2qO545rF/uyFm3p0NOnT83JkyfNokWLzM6dO83FixfNo0eP5O9WOfbD/u+///5kYpePP/7YoP66JJ+0c0dM9vq///3vut25fQQIIKDhyovNCXcZJ4C2YNuwkN82GlzODYG+/EZ/UnI8Nzz72lOEaEsn8d3sy5cvm927d0/ee8UTsPhE3KVLl8z169fNnTt3JrOWvXjxYpJjHdvxP8qhPN6Xxf6oB/X5JIiyG4TddXz6jml8COBKSx/BthEjv200uJwDApr8Rn9ScTwHLLVsKEq03U7funXLnDhxYvJu4LZt28z69evNr3/964nA4gldrGM73tXDSB3luyaQ1xVqdx2jcqbxIIATNR/B7oqIzW+Xa7JOfndFl/s1IRCa32jf5njoGN7U31L+L1q0q0DGfUM87BMiUbhDoFpmnT4BTfPqi4i0m2uiR35roll2XbH5baMVMobb7ZS6PCjRtoMO7sOESKjXDZzuOkjHNFwEENBcn9vrGH1rP+dg128va6NMfmsjWl59KfgtKMWI4dJWqfmgRBtiKQEt1GgbjvZ5MIPCXeohMdvupjcKINj/+c9/ZlfS4V/htZt3qKpxF/K7EaLBFkjFbwE0VgyX9krMByPa9hmaBDYEn1Dphx9+mFyGl7aq8pAnDqH6xXqrEcCT3z7v7ocQbFhUxS9sC5XI71DI5llvan4DldgxPE9PNFsV7qhvblu1hH2GJgEutGiC6GhD2qvK8X/dqz6qALCyYAjAf1XziNv+DjXClk7ZbdnL8n+InPwOgWp+debAb6CSIobn541miwYh2lVnaBLYQo62Aa9PYMMsQhi5MJWHgE9Ai+Ff4bObh0aU/A6NcNr6c+F3yhie1gPtWx+EaFedoUlwCz3aFshn2QBbMBILfQIhtjDXQcAnoIFfMU7IhM9urtPT5lrI72aMSiuRE79n8StWDC/Ff8WL9qwzNAlwscTS555nLFtKIWCudkKI28yzHLofwmU3D92uXT/5baNR9nJO/I4Vwx8+fGiOHz9u1qxZM3dLc9euXeb27dtFObN40Z51hiYBLuaZWtPTl7AJJGXKFwGcWDUJNniHkUqsJFx281jtSzvktyBRbp4bv2PEcAj2smXLJmJ95MgRc+bMGbNly5Y58S5JuIsWbZ8zNAlyMUe4PoEt1FPG5YaSPCwHT3ArQ3hTlWPEGVOwgUyVHdiWIpHfKVDXaTM3fseK4Xfv3p2INMTbThh54zjCiLuUlOaoV0LH5wxNgl3M0Ta6xw+NKDk5YjUIIE2CDcGKLdiAQHjs5hHhmWqK/J6Co4iVHPmdOoZjhI1jCqPuUlKxot3mDE0CXczRNgiA0bS0XZdrTnVZCulytBMzmPkIdirb6/iTyh60S36nRL9d2znyO4cYfuPGDYp2Oyp1L93mDE0CXuzRNnrnQ0x+aKQ7DzT29JlnObWPhMNurtH/PnWQ333Qi7NvrvxOHcPxxbENGzZMRBviXUoqcqTtEyjc4CbrsUfbIIKPvbhPyhQfgZTzLLfprfDXzdvUEaos+R0K2f715spvH864XJf1PjEcD6Dhh3vZeDANvwsXLvQHOmINRYp2lzM0cXiK0Tb86fMACPrFFA+BpvuyuFyu/eGPrr0T/rp51/q09yO/tRHtX1/O/E4Vw93jB69/QcQx6i4lFSfafc7QxGF9ztT6OBbt+rxK1KcN7tuMAB4k83nnOKcn/IW7bt7c23glyO94WM9qKXd+h4rhGDHLSFryWa9y4ZK4XB5HXkoqTrT7nKFJwEs12gYpcEChfbGlKsf/KZ5QLoW0fezMPaDV9a2KJ9iWWyK/03qkBH6HiuHyHrZ9rEC8ZyWMsGW/K1euzCqazX/5HfUdobEdZS93rC7obgxsQeGtrRy4+3z4I9WVmFrDM3zla5at5PcsdML9VzK/gYodt+3lcIi9rFkmWWkS+NB2+NZP0fZFKkC5pjNO3FPNUUACQBG8Sp+AhiscMeYR79JZO4jZy13qirUP+R0L6ZdX8JpOSHPmN5CyeW0vh0ZRRLuUB9Io2qEZ0VB/04FG4W4A0ONv35FfroKNLtpBzF726H7SIuR3ePiHwO/QHJd73K43MFOaHE/ubGlu2VzWKdoZeMLnoSg8vMHUHgHfh6MQ+HJOEljcPGebxTbyW5DQz4fCbyDjclvWNVDDKBr14WlxvO4FEccc5NJGKfezJzhpAJJDHQK+m+dgm48NPvM5U7h9kJwvw4A2j0XqJfJb3wND4jfQcWO3rGshB2GWS+GoGw+g8StfWuh2qEcc7OYdqkq2S9N7lehbLu8NJwPJs2EENJ9pSXMfYUt3XV7LuvxfQk5+63lpaPwGMsJpN9dDbRg18fJ4Zn6EKLukddcxyxFTPQK4IjEkwUZPXQ7Iej0Kef5Dfvf3yxD5PSSO9/fw7Boo2rPxSfIvDkoJynU5Ri1MryLgM88yLtWWlup4UFo/YC/53d1rQ+U3EBkSx7t7uHlPinYzRklKMLC1h90noJV6lWJoAY38Jr9dBIbGcbd/WusUbS0kA9SD+1Z1RJbteBeWyRiIsWBSleNyecnPA1T1CdtKTuS3v/eGzm8gMUSO+3vYv2TZR73Vz6E63OeBk7ELd9OTyRDsnOYRt2jrvUh+e0M1uIJj4DecNlSOaxOSoq2NaID6MOmHz3zlAZrOuko8+e3zDnDpgg0nDDmgkd/Vh9mY+D10jld7uNtWinY33KLvhQPYR7hLeYWpL4Dop89sW0MQbGA1ZNFG/8jv6SNibPweA8enPdx9jaLdHbvoe/oENnz6E5fUh5x8AhpwyHla0rb+GbpoAw/y+yUrxshv9HwMHG973FeVp2hXoZL5tjF/iMEnoOX+YYQu9BpTQCO/d9QKGHgwRH7jmBgTx7vEANmHoi1IFJb73Msd2ogbI2eMoOsObgloEPahpbo+D62f0h/ye0ElzyHYQ+Q3/D42jgvX2+YU7baIZVS+6alSHAR4H3YICScgTYKNERoD2hC8/bIP5Pe0cA+Z3/A4Rdvv2KVo++GUbakxzOfs89obRmZDFewxBzTy+6VwD53fY+Z4W3GhaLdFLMPyPoGt1JnAcKVgaPOId6HQmEch5PeHgz4hleNhzBwXDHxyirYPSgWU8ZkWsjThxgxmPoJdgHt6mzj2gEZ+96ZQ9hWMneO+DqJo+yJVQDmfwIZRSwkJJxhNgl1KXzTwZkAb1odGyO9Xjwpy/FVMqrZQtKtQKXibj3BjUpKcEwJa3QGM7RDzkucR74J9HR5d6ip5H/K7ZO/Ntp0cn42P/EvRFiQGlPs8uIUnUXNMTfcvxyjY8BMD2jxbye95LIa0RI77eZOi7YdTcaV83mnOSbjx5LfPu7lDmZa0LaFiBrS7d++aNWvWTE4UsJxjIr9z9Eo/m2JyvJ+lafemaKfFP2jrEMIS5iunYDfTIFZAO3PmzNSo/vbt283GJSpBficCPlCzsTgeyPxo1VK0o0GdpqHcAxvsa/rwxxjmU29iR+iA9tNPP5ktW7ZMBBv5hg0bJss5izYwI7+bmFPO/6E5Xg4Ssy2laM/GZzD/4lJ43UGB7bhXjHuFMZOPYA91nuW2ONf5rm09deUhzmjjwoULkyIi4LmLtvSH/BYkys1Dc7xcZKYtp2hP4zHotaYRbUzhxj1Jn0v3KMcU/kE0jLQfPnw4B3Vpog3Dye859xW5QNH2cxtF2w+nwZTyedgLr9WETBjRj3ke8S7Yxg5oJYo2cCW/u7Arj31iczyPXre3gqLdHrPi90j5IQYKdjf6xA5opYo20CW/u3Es9V6xOZ66v13bp2h3Ra7w/Zreh8YBpD2BCUbwuARfd3BiOwIu7nUzTSNQh9l0Kb21kkUbKJDfelyIVVNsjsfql3Y7FG1tRAuqD6Jcd6DIdq35yinY/Ygh/nBz31rxvjVe53J/dfuXLtroF/ld5908t7vclvU8rU1nFUU7HfZZtOwzLWTfOb595lnGCJupHgEJYG5ev8f0P3gq3N0X63VpCKKNvpHfdR7Ob3sVP2dxNL8exLGo/qiN075aK3R4dyh9AltXUfURbK3RfHcE8t8zNr+HItrwLPmdP79hYWyOl4HKq1ZStF/FZJRbQsznDDGuOxCxfazziHchWB2OXery2WdIoo3+kt8+Xk9bJjbH0/a2e+sU7e7YDW5PzcDW9AQvBHus84h3IU7sgDY00Qbm5HcX5sXbJzbH4/VMtyWKti6exdfmO+lJXUfx5LfPu7IU7DoEq7eHDmiYXMV+SE0+GHLkyJG57dWWlbWV/M7XX6E5nm/P21lG0W6H1yhKd53P2WdaUoywcY+RqR0CoQMani6va0O22zOmtbM+r9Lkd17+EGuEZ24u/zN/iQBFm0yoRACBrWk+Z/tDHj6CjfKclrQS7saNbiCT9cYdWaASAfK7EpakG4XTbp7UqAwbp2hn6JScTGoSboyc//e//zUKPD/80c+rbiCT9X61cm/yOx8OCKfdPB8L87CEop2HH7K2ouke9S9+8YuZl1Yh2BjZMHVHwA1kst69Ru4pCJDfgkTaXDjt5mmtyq91inZ+PsnSoqanwd0DTdYxkqFg93ep4Onm/WtmDUCA/E7PA5fbsp7esrwsoGjn5Y+srfGZz1kONOQYwVCwdVxq42ov69TOWoAA+Z2WBzav7eW0VuXXOkU7P59kbZFvYMPIhYKt50o7iNnLei2wJiBAfqfjgc1rezmdRXm2TNHO0y/ZWoWPMPzqV7+aeQ8bBxynJtV1oR3E7GXdVlgb+Z2OAzav7eV0FuXZMkU7T79kaZXPPOL2wYZRC5MOAjau9rJO7awFCJDfaXlg89peTmtVfq1TtPPzSZYWNc0jbh9k9vKOHTuy7E9pRtmY2sul9SNXe8nv9J6xeW0vp7csLwso2nn5I0trmu7zLVy4cOblcjxBztQPATuI2cv9auXeQID8zoMHNq/t5Tysy8cKinY+vsjOEjxI1vQOKyZX+de//mUw25l9oLnLFO5+7nXxlPV+tY57b/I7L/8Lp908LyvTW0PRTu+DLC3wDWjy4Q+UxyQq7gFnr3OSle6utnG0l7vXOO49ye/8/G/z2l7Oz9K0FiUTbXygQL4khOW+yXayvdy33jHuj4CGe9E2ju6yPe+4YOQr3Jx/XBDzz138Zd2/BpYUBMhvQSKvXDjt5nlZmd6aJKKNTwDajrl9+3ZvJOz67OXeFY+sAp+A1jSPuM98zvi2MZM/Ajan7WX/GlgSCJDf+fLA5rW9nK/FaSyLKtr4Zu+WLVsmgo18w4YNk2WKdhrnu636fmvYZ6TcNFLHvXAKt+uB+nU7iNnL9XvwHxcB8ttFJK91m9f2cl5WprcmqmhDnOGMCxcuTHouAk7RTk8ECKjPw2QYqfimpofYwAV+W9sPTTuI2ct+e7MU+Z0/B2xe28v5Wx7XwqiijZH2w4cP53pI0Z6DIulCiIAmHfL5EIM8zCb7MH8VATuI2cuvluQWFwHy20Ukz3Wb1/ZyntamsyqqaLvdpGi7iMRfx0gXl6rtg8Rd7juPeNN7sGgP00cy1SPg+kTW6/fgP0CA/C6HB8JpNy+nB3EspWjHwTnLVmIENOk4RNk9GN11zErFVI2Ai5WsV5fmViBAfpfFA+G0m5fVi/DWUrTDY5xlCz7zLGvPHY4g6h6Q7rp2m1mC38EoFydZ71DVKHYhv8tzs3DazcvrSViLKdph8c2ydp+AFmrU6yPceICNaRoBN5DJ+nQprgEB8rtMHgin3bzM3oSzmqIdDtssa266v4z726HvL+PBoKb76Jz2dJo+biCT9elSXCO/y+WAcNrNy+1RGMsp2mFwzbLWpie5IaSxnuSmcLejiBvIZL1dLcMuTX6X7V/htJuX3St96yna+phmVyPerW56ZzqmYAtAvpNdSPkx524gk/UxYyJ9J78FibJz4bSbl90rfesp2vqYZlWjz7SNEGzca06RYB8/NNKMvBvIZL15z2GXIL+H41/htJsPp4c6PYkq2phcBfOOy08+GHLkyJG5bV275Tpa1rvWN4T9fAIaZkHzmZY0JB6ws2m+8qoPlIS0Kbe6hc9unpOdOL4x26FMTwxbsXzlypUgZpLfQWBNVqnLbVlPZlCmDUcVbXzNSxxRl9szprXBrK6+NnX0LYvgtGvXrrk+4qQEJygIZrGTjxA2ffgjtrOQotkAABkQSURBVM1Nwo0rArgXPsaUA7+bcBexXrZs2eQbA3JSDttxHGgm8lsTzTzqKoHjOSAVVbRDdji1w48fPz4RaxFqrCN4wS7M/BYzYeTcNI94rt+29rn3PkbhTs1vH/6C++6oGlfRYDuOBa1EfmshmVc9JXA8B8Qo2kpeQHCSD6FIlbhqIMKt8c1wqXdWDkFrEmyMaDFSyTU1PQWMgzvVPfhUmJUa0HCVSWzX+DAQ+Z2KgeHbFZ64efiWy2qBoh3YX5rzqzeZioCGS8gu6e11jGRzFmzpY9P7tuhT6PfJxZYcctuH9nIOtjXZIPb2FW3yuwnpsv8Xnrh52b3St56irY/pVI1yn69vwJqqtGIFI88mwe774Y+KZoNu8hHuUDO3zeoYRo9yv1bzsu+sNt1AJuuz9snhP1xt0rCV/M7Bm8YgjsnVQzy/o5mEJ26u2cYQ6qJoB/Qi7u+BgBDukAkjTh/BDmlDqLoRrN2D2F2HuMdM8vyC2BGjbWnLzWO03acNPIAGm/sEePI7Lr9n+VsGIfCp9rM6LrdlfZY9Y/yPoq3odZyFyutsclkcedcn4n1M85lnObao+djdpkxOwi0jR3nACoElRpIA5uYx2u7ahv1MR9djgPxeMDnpyeEYlkGIcJ+i3fXI6LdfnIjTz0avvd1gJuteOysVklGFtI0cI4xQl8YR0Oy23GWMvody3xf3M93+uesx5iuXgCXiDRtiJLevsh6jbWnjxo0bcyelcnLqPi0uZZHLqMx9QNMuM2uZ/H4p2OLrGPye5Q/cEsIP8Qw2UbRnoRXuvzgRJ5z9czULsd18rkDkBQR1W8QR8DRT0/3eIQm24ObzIFLIwCbzDODyOJJwTewLmUtbbh6yTbduew4CsaMucMvJDfIuifyeFmzBOyS/Z/kJJ16wAXGMoj0LqfD/UbQDYyzCjTNUjYQnv33eZY714Q+NPrWpw/cd3TZ1+paFQOEhHJksRwKp7/59yklbbt6nzlD7imB3uY9NfvvNsRDKd1X1gu/gvZygUbSrUIq3jaIdGGshOIJt3zT2gCb4AYfY85WLH3ESJkkEVNZD5tKWm4dss0vdIti4NC4nN771kN8vkUrB71k+koEHjgEkORZExGft2+Y/l9uy3qaOMZTtrySZoCQOdvPU5gnBcabaJ+FA3rFjx9wlWbefWM9hHvE+fWyzr09g08QDIoSrJbYQiQ/a2N21rLTl5l3rC7GfPKjUVbDJ73mvxOb3fMvTS/IwoX3VRGIaRXsaq1hrFG0lpBGoqmY9k/uAXe/twTwfwc5tHnElWBurwT0+V8jsddzbx73wPknEyH3oStrpU7fvvtKWm/vuH7qc3O+HfTgWENDdnzwL4NpCfruIzK+H5nfTw4Vy5cR++p+iPe+fFEsUbSXUMZJGwIJI43ISfhiZSRCzR2htmsQ93NiXgtvYl0PZphFaX+GGH6ueSRABjYGBtOXmMdr2acMWbddGWa8amZHfzeiG5LcMKsRHyMVP8oaEO+CgaDf7LGQJirYSuiA4yC1CDfJjxAHx7irYGCGWPo+4EryN1TQ9nAd/4H3vtklG2fbJmJyUSaDDetfXmnztkbbc3Hf/HMuR3/5eCcXvWRbIKBtXSITzyGU7Yh3Wtd6Mcbkt67NsHON/FO1Mve7zehPOwHFpkeklAj4fGmn7VL286iIBpC7v+8xCkw/r2m3aL9f/ye/2ngnB71lWVI3Cq3iIchqpqm5sY5pGYDCIDMnhQ5xneZp24daa3u8FT7QmnBHOhevNfM3SlpvPlyhnifzu7quY/K6zkpfH65CJs52iHQdn71YwEsQ9WDc42+s442aqRwCibONVtYzZtvomqbdvPT77S1tu7rNvTmXI7/7eiMXvOksp2nXIxNlO0Y6Ds1crY5hn2QsIhUIx5ivHJfHQl8UFClesZV3+LyEnv/W8FIPfddbKQ4dal8WlHeG0m8v/zF8iQNHOhAlN8yyDyBqjw0y6G8UMn8CGB3xKSG4gk/USbIeN5Le+p4bEb6AjnHZzfeTKrpGinYH/mu5TDXEe8Viw+zzwlGo+5zYYuIFM1tvUkaos+R0O+aHwGwgJp908HHpl1kzRTuy3pidCIdhtn3hO3KXsmh9CYHMDmaxnB7ZjEPntABJgdQj8BizCaTcPAFnRVVK0E7kPr2o1vXtJwdZzDvAueZIaN5DJuh5CujWR37p4NtVWOr/RP+G0mzf1fWz/U7QTeBwHmM8sR7hnxaSHQMmBzQ1ksq6Hjl5N5Lcelm1qKpnf6Kdw2s3bYDCGshTtyF72CWhjnUc8hiuAf9N8zpiFDpccU6SmqwFuQKtaT3mPnvxOwZr5NnPn97ylry5VcRnbmKYRGAwiJTjc54CiYE8TNNRak3Dj1kQK4UabdVz23Z7qCg35HYqt7evNld+zelLH71n7jPE/inYkryMYN80jDsFG4GOKg4DPMwUpBLDPaDvVKJv8jsPZNq3kyu+6PlC065CZ3k7RnsYjyJpPQEOwpWAHgX9mpU1PNyOQxBbuPqPt2LYCXPJ7JsWS/pkjv+sAoWjXITO9naI9jYf6GgIaLrXWERLbcUZMwVaH3rvCpveI4SOt+cp9jeoy2k4xyia/fT2arlyO/K5Coy5GVpUd8zaKdkDvY9TTJNg4E6ZgB3SCZ9U+gS3mjHRdRtuxR9nktye5MiiWG7+rIKFoV6Hy6jaK9quYNG6ByDaNvPC/j2A3NsYC0RCACNUFDtmO4DcrQWx/+OGHWUW8/2sz2tYcZZPf3i4qqmBu/HbBk2PMzd1yY1+naHdgAGYoA7HqRjYYkTUJdsxRW4cujnaXPoFNLhXj6olGajParuNiFzvI7y6olbFPTvx2EXPFWtbdcmNfp2h3YIA9MQoCq52aPowAMW8apdv1cTk+Aj5i6Y5sMbqWtwPgY63kM9p2benbNvndF8G898+J3zZSItJubpfhsjEU7ZYsQHC2SYUALcLddN8IZTmPeEvAExWHT+Ev29fusoglLie74qp1YuYTYDVH2eR3IsJFbjYXftvddo8vWbfLcJmi3ZoDVcKM4G6PToRsdk7Bbg118h3s0bPtS3sZYl3le7wRoJXcEwK7fTlx0GqL/NZCMv96cuG3IGXz2l6W/5m/RIAj7ZZMmBVAbaLZyxTsliBnVLxqFG37tm4ZPse+GmnWaFtzlA1byW8Nj5VTRw78FrTqjiX5n/lLBCjaLZjg8xCHSzzc58QZLVO5CHQNbJoPG1aJqfYom/wul6N9LM+B37DfjZ2y3qdvQ9yXot3Cq03TAgrJJEegpWC3ADjzohBJ8a1PjhM2rVQ12tYeZZPfWt4qs56U/AZidcdUmWiGs5qi7YktzkZxybOOWO52CDb2YRoWAlX3r13f2+uaJ232aFt7lE1+D4unXXuTkt/2cWMvd+3LUPejaHt6Vt5dtck0a1k7qHqayWKBEWh6pc/lhNY72+iWPdrWHmWT34GJU0j1KfntHjuyXgh00cykaHtC3fYMFITTfILY00wWC4hA24AGDuDqjGbCaDvECSH5remlMutKzW8RaTcvE81wVlO0PbDFJU6XSL7rmiMtD1NZJBACPtPS1nFC651tdA2jbe1RNvkdiDQFVZsDv+uOn4JgjGJq0aJ969Ytc/LkSbNv3z6zbds2s379erNq1SqzcOHCSY717du3T/4/ceKEQfkuqerd1TqCVW3XDNpd7Oc+/RDApeM2zzO4HMAotksiv7ugxn3aIpCK37AzFsfbYpJz+aJE+6effjKXL182u3fvNsuXLzcbN240n3zyibl06ZK5fv26uXPnjnn8+LF58eLFJMc6tuN/lEN57If9UQ/q80kyPaUbjH3WEexxOVPzgSQfm1lGDwFcLfHx9awyPv4nv/V8xpr8EYjFb1iUiuP+aORfsgjRfvr06WREvXjxYrNz505z8eJF8+jRo07oYj/sj3oWLVo0qRf116W2D+ggcEPkcSDgMiafIK9Dtrzt4AKuuthPcc8Savs/3C+sS+R3HTLcHhOBUPxGH1JyPCaGMdrKWrSfP39uTp06Nbk0efDgQfPgwQNVTFDfoUOHJvWfPn3aoD03+by7KqNpBHTcc2QaPgI4GYMQ+z7AVfXONvk9fJ6U2kMNfqPvOXC8VB/U2Z2taN+8eXNyX3rPnj3m3r17dfarbEf9aGf16tUG7Uqa9e4qhBoBG/erOZoWxMabY5SCqyuzbqXYl8jJ7/FypcSet+U3+pgDx0vEusnmLEX73Llzk3vPV69ebbJf9X+0t2LFCnP27NlJvSCqXOJ0R9MUalXoB1UZrrZgFI5nGYQ/yOUVQPJ7UO4eXWea+A1AcuH4EJ2TnWjjSfBNmzaZ+/fvJ8Eb7aJ92IGRNEfTSdwwqEbtUQr5PSjXsjPGTD43LFeZAEhOHB+ig7IS7c2bNxvcu84hHThwIMgkFjn0jTakQQD83rt3b5rGnVbJbwcQrqoggKtLOcVwHHNDS9mINoLZ/v37s8IX9uQSZLMChsa0RoD8bg0ZdygMAXI8jsOyEO3jx4+brVu3xulxy1ZgF+xjIgJdESC/uyLH/UpBgByP56nkon3+/Hmzbt068+TJk3i9btES7IJ9sJOJCLRFgPxuixjLl4YAOR7XY0lFG7OXLVmyxFy7di1ur1u2BvswsQvsZSICvgiQ375IsVypCJDj8T2XVLQPHz5sjh49Gr/XHVo8duyYgb1MRMAXAfLbFymWKxUBcjy+55KJ9jfffGNWrlxpnj17Fr/XHVqEnbAXdjMRgSYEyO8mhPh/6QiQ42k8mEy08fWtzz//PE2vO7YKe2E3ExFoQoD8bkKI/5eOADmexoNJRBsz6qxduzZNj3u2Crs5v3hPEDPcHfPGY4IIjUR+a6DIOjQR0OQ37CLHNb3Trq4koo3PZH700UftLM2kNOyG/UzDQgBBTaYc7Sve5PewuDGE3mjyG3iQ4+lYkUS033rrLfP111+r9fr27dvmyJEjZtmyZZPAixzrDx8+VGtDKoLdsJ9pWAjYQa2veGvz20X6woULcycYWNZM5LcmmvnUpclv9EqT4/jGthxzVfmVK1dUgSyd49FF+/vvvzdvvPGGmhNu3LgxJ9R4wf/MmTNmzZo1c9tACO0E+9EPpuEgUBXUJIC0GXlr89tFGCeicnIK+8B37UR+ayOavj4tfqMn2hzHoAtcRtzesmXLKz/8r51K5nh00f7000/NBx98oOYDjDQg1q44b9iwYUIE7ZEIDIf96AfTcBCYFdTaiLc2v12EcQUJ9kgeQrTJbxf18te1+A0ktDkuoh2Cy3WeK5nj0UUbYMV4ahwECDUSgf3oB9NwEPAJaj7iHZLfGGWLYJPfw+FejJ5o8Ru2anM8hWiXHMOjizY+dfnll18G5ylG36FEG/ZLAGe+YLRYVF02D8nvXbt2TS6NQ7xDijb5PV5O2/Gsit8I3NocTyHa4Dj6UWKKLtpvv/128AlK7t69OwluuPcX4mE0TCpgk5vL4w5ydnALxW83sIUUbfJ73Hx245nNb4icNseF27ifDV7jh9uaiOOhEjiOfpSYoov2a6+9Zh49eqSKlYw84Gy514eHGkCGEAn2u8TmOgMdglsIfoPDCGg4CZVnN0KKNvlNLlfFMxFvbY7LbZ+qNsF74bxmLAfHX3/9dc0qo9UVXbQXLlxoXrx4odpBOVOznY4H0bRfFRCjnz9/TtFewMBm823p0qUG9w1D8FvekLAfqgwp2uQ3uW1zG8vC759//jkIx91RNTgvDxNDuLWTcFy73hj1RRdtnKX9+OOPwfqGszKItbwWg3vb2okjEQY1CWp2MAPPQvAbV43ws1NI0Sa/ye86fofiuM1tWUYsFzu0b3NypC0oe+S4j/Dtt996lOxXxB59azuc9/wY1FyxFrZq8xsnoAhc7lWjkKJNfpPfdfwGz7U5LsdOVY5RNvivfauT97Sr0K7Zhif2vvrqq5p/dTfLWZq2w0t+8lAX4eHU5vtKzKxgBjS0+Y0RNq4aQaTtnwQz5NjuXl7s4xnyuw96ee6rxe8QHJ+FmPCcMXwepeiXx/GO3xdffDFvQcAlEW3NgAZzS37HLyDcRVfdFNSaxFo6r81vuc0jXK7L7fvdYkvXnPzuily++2nxGz3U5vgs1IT/2ldLS+Z4dNHWnk0H767ioQU3IYghwLn3At1yXdZBWs6I1gW5fPepC2q+Yi090+a31OvmIS+Pk98u2uWva/EbSMTiuLwJhNG2diqZ49FFW3veWog2xBlPGsrlQ7mkgrM07VE2yFPyvLXa5B9KfW5QayvWgoM2v6VeNw8p2uS3i3b561r8BhLaHEe8xk/iN3J5chx5iFe+SuZ4dNGG07W/EGM7WUbXOEvTvqQC20v/Qkz54SdMDySodRVr2ypNftv12styJUnzsjjqJ79tlIezrMlvoKLJcVwphWjLpXB7EBZCsEvneBLR5rdYhxMMhtKTzz77bPKeNd5D7ZvI774Icn9tBDT5DdvIcW0P+deXRLS/++47s3btWn8rMyoJu2E/ExGoQ4D8rkOG24eCADmezpNJRBvd3b59e5SvfWlCiycOYTcTEWhCgPxuQoj/l44AOZ7Gg8lEGy+3r1y50jx79ixNz1u2CjthL+xmIgJNCJDfTQjx/9IRIMfTeDCZaKO7hw8fNseOHUvT85atHj16dGJvy91YfMQIkN8jdv5Iuk6Ox3d0UtF+/PixWbx4sbl27Vr8nrdoEfYtWbLEwF4mIuCLAPntixTLlYoAOR7fc0lFG909f/68WbdunXny5En83nu0CLvefPPNiZ0exVmECEwhQH5PwcGVASJAjsd1anLRRnfxJa733nsvbs89W9u6devEPs/iLEYEXkGA/H4FEm4YGALkeDyHZiHa6O7evXvN/v374/XcoyXYA7uYiEBfBMjvvghy/9wRIMfjeCgb0UZ3N2/ebA4cOBCn5w2twI533323oRT/thHADHQ448Z875jVCD9MM6v9hR67zZKWye+SvEVbuyBAjndBrd0+WYk2TN+3b5/ZtGmTuX//frueKJVGu++8887EDqUqR1ENBFumIYRou9MSUrhf0oD8HsXhMOpOkuNh3Z+daKO7Z8+eNStWrDBXr14N23undrSHds+dO+f8w9UmBPBhFkzub4sz5g2Wif8x4mZ6iQD5TSYMHQFyPJyHsxRtdPfmzZtm1apVZs+ePebevXvhEDBmUj/aQXtol0kPAXwMQC6V69Vafk3kd/k+ZA9mI0COz8an67/ZijY69Pz5c3P69GmDLy8dOnTIPHjwoGs/K/dDfQcPHpzUf+rUqUl7lQW5sTMCGHlTtKvhI7+rcQmxFVd95FkL3MZhioMAOa6Pc9aiLd19+vSpOXnypFm0aJHZuXOnuXjxonn06JH83SrHftj//fffn0zs8vHHHxvUzxQGgStXrkxEG/e4maoRIL+rcdHcigck5eQROVNcBMhxPbyLYi/Oli9fvmx2795tli9fbjZu3Dj5RNylS5fM9evXzZ07dyazlr148WKSYx3b8T8+JYfy2A/7o54Q32rVc80waoJYI0hqf/d5GOhM94L8nsZDaw0PSYKDR44cmRNurbpZTzsEyPF2eFWVLkq03Q7cunXLnDhxYvJ+97Zt28z69evN6tWrJwcmcqxjO963xkgd5ZniISD3s3FZkqk9AuR3e8yq9hCxFvHmSLsKpTTbyPH2uBct2u27yz36IIDR8pkzZ6Z+9tPidt32K2B4spyJCKRAANyDSOPyOBKWKdopPME2tRCgaGshOYJ65D1sCXzIIeJuwiUwedUL97SZiEAqBGS+ALkVJtxNZQ/bJQJ9EaBo90WQ+08hYAs272NPQcOVyAjImwv2iSVFO7IT2Jw6AhRtdUjHW6Et2LiPyEQEUiKAqz14nkJG2bCFop3SI2xbAwGKtgaKrGOCgDzwQ8EmIVIjIK8aurdnKNqpPcP2+yJA0e6LIPefIIBL4RIQcR+x6ucGUEJHBEIhgBF21VsLwtFQ7bJeIhAaAYp2aIRHUr8t2hIY3dy+tzgSWNjNBAjIKBvz3btvOwgnsZ3PXCRwDpvsjQBFuzeErIAIEIGcEPA5gYR4czrTnLxGW3wRoGj7IsVyRIAIFI+AjLSL7wg7MFoEKNqjdT07TgTGhwBFe3w+H1qPKdpD8yj7QwSIQC0CuCTOy+K18PCPAhCgaBfgJJpIBIgAESACRAAIULTJAyJABIgAESAChSBA0S7EUTSTCBABIkAEiABFmxwgAkSACBABIlAIAhTtQhxFM4kAESACRIAIULTJASJABIgAESAChSBA0S7EUTSTCBABIkAEiABFmxwgAkSACBABIlAIAhTtQhxFM4kAESACRIAIULTJASJABIgAESAChSBA0S7EUTSTCBABIkAEiABFmxwgAkSACBABIlAIAhTtQhxFM4kAESACRIAIULTJASJABIgAESAChSBA0S7EUTSTCBABIkAEiABFmxwgAkSACBABIlAIAhTtQhxFM4kAESACRIAIULTJASJABIgAESAChSBA0S7EUTSTCBABIkAEiABFmxwgAkSACBABIlAIAhTtQhxFM4kAESACRIAI/B/lgxRh9+40JgAAAABJRU5ErkJggg=="
    }
   },
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's change the edge from 2 to 4 to be weighted with -2 rather than a 0. Then what do you think will happen?\n",
    "\n",
    "![image.png](attachment:image.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "G_example_2 = [['X',3,'X','X',4,'X'],\n",
    "            ['X','X',2,3,-1,-4],\n",
    "            ['X','X','X','X',-2,'X'],\n",
    "            [1,'X','X','X',-2,'X'],\n",
    "            ['X','X','X','X','X',4],\n",
    "            ['X','X',-3,'X','X','X']]\n",
    "DataFrame(G_example_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Bellman_Ford(G_example_2,0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Currency Arbitrage\n",
    "\n",
    "A currency arbitrage is a way to make money from a sequence of two or more currency exchanges. Since the values of currency change on a daily basis and there is no central system that manages the values of the worlds currencies, each exchange house must update their own exchange rates. Because of different time zones, subtle market fluctuations and spread of information, some exchange houses will update faster than others and may create an *arbitrage*.\n",
    "\n",
    "An *arbitrage* (in terms of currency exchanges) is a sequence of trades that start and end with the same currency and the ending value is greater than the starting value.\n",
    "\n",
    "Here is an example of a currency arbitrage with two currencies. Suppose that Bank A exchanges 1 dollar for 0.75 euros (0.75 &euro;/\\\\$ ) and Bank B exchanges 1 euro for 1.5 dollars (1.5 \\\\$/&euro;). Then you could bring 1 dollar to Bank A and have it exchanged to 0.75 euros. Then take the 0.75 euros to Bank B and have them exchanged to (0.75)(1.5) = 1.125 dollars. You have made a profit of 0.125 dollars.\n",
    "\n",
    "In this notebook, you will be given the exchange rates between many currencies (labeled 0,1,...). It is your job to find the *arbitrage* by possibly modifiying the algorithms or modifying the input data.\n",
    "\n",
    "Below is the input data ER that tells you the exchange rates between 7 different currencies (currency 0, currency 1, ...)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ER = [[1,\n",
    "  0.88421157,\n",
    "  111.728826,\n",
    "  0.75912408,\n",
    "  1.0048994999999998,\n",
    "  1.3438656,\n",
    "  1.4221577699999999],\n",
    " [1.13068692,\n",
    "  1,\n",
    "  126.34296444,\n",
    "  0.8584141500000001,\n",
    "  1.13638635,\n",
    "  1.51964802,\n",
    "  1.60813917],\n",
    " [0.00889911,\n",
    "  0.00789921,\n",
    "  1,\n",
    "  0.006799319999999999,\n",
    "  0.0089991,\n",
    "  0.0119988,\n",
    "  0.01269873],\n",
    " [1.31706828,\n",
    "  1.16468352,\n",
    "  147.16918161,\n",
    "  1,\n",
    "  1.3236676200000002,\n",
    "  1.77042294,\n",
    "  1.87321266],\n",
    " [0.9949005,\n",
    "  0.87981201,\n",
    "  111.17298159,\n",
    "  0.75532446,\n",
    "  1,\n",
    "  1.33556643,\n",
    "  1.4150584800000001],\n",
    " [0.74382561,\n",
    "  0.6578342100000001,\n",
    "  83.11918725,\n",
    "  0.5647435199999999,\n",
    "  0.74762523,\n",
    "  1,\n",
    "  1.05799419],\n",
    " [0.7030296899999999,\n",
    "  0.62173782,\n",
    "  78.55654356000001,\n",
    "  0.5337466200000001,\n",
    "  0.70652934,\n",
    "  0.9450054900000001,\n",
    "  1]]\n",
    "\n",
    "DataFrame(ER)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exercise 2:\n",
    "\n",
    "Find an arbitrage in the exchange rates given by the matrix ER that includes currency 0.\n",
    "\n",
    "(Write your arbitrage as a cycle for example: \"(0,4,2,5)\" meaning that you first exchange currency 0 for currency 4, then exchange for currency 2, then exchange for currency 5 and then back to currency 0.) \n",
    "\n",
    "(Hint: you may want to make a new matrix that takes the negative log of each cell.)\n",
    "\n",
    "Answer: (0,2,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}