ShortestPath_Djikstra.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Statetment:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./data/ProblemStatement.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "+ Leveraging a modified version of the Djikstra's shortest path algorithm to solve for this to accomodate for the Grid positions and the finding the adjacent cells in a matrix. \n",
    "+ The methodology is described in the methodology tab of this excel sheet. [ShortestPath](./data/ShortestPath.xslx)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import itertools as it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Function to get the adjacent node co-ordinates from the grid given the current node an the grid shape\n",
    "def get_adjacent_node_coord(tpl_curr_node, tpl_grid_shape):\n",
    "    ls_adjacent_node_coords = []\n",
    "    \n",
    "    if tpl_curr_node[0] + 1 < tpl_grid_shape[0]:\n",
    "        ls_adjacent_node_coords.append((tpl_curr_node[0] + 1, tpl_curr_node[1]))\n",
    "        \n",
    "    if tpl_curr_node[1] + 1 < tpl_grid_shape[1]:\n",
    "        ls_adjacent_node_coords.append((tpl_curr_node[0], tpl_curr_node[1] + 1)) \n",
    "        \n",
    "    if (tpl_curr_node[0] + 1 < tpl_grid_shape[0]) and (tpl_curr_node[1] + 1 < tpl_grid_shape[1]):\n",
    "        ls_adjacent_node_coords.append((tpl_curr_node[0] + 1, tpl_curr_node[1] + 1))\n",
    "        \n",
    "    return ls_adjacent_node_coords\n",
    "        \n",
    "def ShortestPath_DjikstraMod(ls_grid):\n",
    "    #Initializing all the values and vectors\n",
    "    print '*' * 25    \n",
    "    print 'Create Grid Layouts'\n",
    "    df_grid = pd.DataFrame(ls_grid)\n",
    "#     print df_grid\n",
    "\n",
    "    #Shape of the grids\n",
    "    d_num_nodes = df_grid.shape[0] * df_grid.shape[1]\n",
    "    ls_xrange = range(0,df_grid.shape[0])\n",
    "    ls_yrange = range(0,df_grid.shape[1])\n",
    "\n",
    "    print 'Create the Node Layout'\n",
    "    df_nodes = pd.DataFrame(np.array(range(0,d_num_nodes)).reshape(df_grid.shape[0],df_grid.shape[1]))\n",
    "#     print df_nodes\n",
    "\n",
    "    print 'Create Node to Grid Coordinates'\n",
    "    dict_node_to_coordinates = dict(zip(range(0,d_num_nodes),list(it.product(ls_xrange, ls_yrange))))\n",
    "#     print dict_node_to_coordinates\n",
    "\n",
    "    print 'Create Grid Coordinates to Node'\n",
    "    dict_coordinates_to_node = dict(zip(list(it.product(ls_xrange, ls_yrange)),range(0,d_num_nodes)))\n",
    "#     print dict_coordinates_to_node\n",
    "\n",
    "    print 'Initializing the Results Matrix'\n",
    "    df_out = pd.DataFrame(index=range(0,d_num_nodes),columns=['distance','prevnode'])\n",
    "    #Set the initial distance to zero for the source node\n",
    "    print 'Setting Source & Node Distances'\n",
    "    d_source_node = 0\n",
    "    df_out.loc[d_source_node,'distance'] = 0\n",
    "    df_out.fillna(float(\"inf\"), inplace=True)\n",
    "#     print df_out\n",
    "\n",
    "    d_edge_weight = 1\n",
    "    print 'Set the Unit Edge Weight', d_edge_weight\n",
    "\n",
    "    ls_visited_nodes = []\n",
    "    ls_unvisited_nodes = range(0,d_num_nodes)\n",
    "    print 'Create list of Unvisited Nodes'\n",
    "#     print ls_unvisited_nodes\n",
    "\n",
    "    print 'Calculate Shortest path across Grid/Nodes'\n",
    "    print 'Using modified Djikstra'\n",
    "    for node in ls_unvisited_nodes:    \n",
    "        #Move Node to Visited Node List\n",
    "        ls_visited_nodes.append(node)    \n",
    "\n",
    "        #Get Node Co-ordinate and find value at the Co-ordinate\n",
    "        node_x_coord = dict_node_to_coordinates[node][0]\n",
    "        node_y_coord = dict_node_to_coordinates[node][1]\n",
    "\n",
    "        #If the value at the co-ordinate is 'X', then the node is blocked\n",
    "        if df_grid.iloc[node_x_coord, node_y_coord] == 'X':\n",
    "            continue\n",
    "\n",
    "#         print 'Current Node Coordinates:', dict_node_to_coordinates[node], df_grid.iloc[node_x_coord, node_y_coord]\n",
    "\n",
    "        #If the value at the co-ordinate is 'X', then the node is the objective\n",
    "        if df_grid.iloc[node_x_coord, node_y_coord] == 'O':\n",
    "            break        \n",
    "\n",
    "        #Get Adjacent Nodes using the x, y co-ordinates of the current node\n",
    "        ls_adjacent_node_coords = get_adjacent_node_coord(dict_node_to_coordinates[node], df_grid.shape)\n",
    "#         print 'Adjacent Node Coordinates:', ls_adjacent_node_coords\n",
    "\n",
    "#         For each adjacent node neighbor\n",
    "#         If neighbor is not blocked i.e. is not 'X'\n",
    "#             Calculate the distance of the neighbor from the SOURCE Node\n",
    "#             If the distance from the source node is < the known distance\n",
    "#                 Update the distance to calculated distance\n",
    "#                 Update the previous node to the current node\n",
    "\n",
    "        for adj_node_coords in ls_adjacent_node_coords:\n",
    "            adj_node = dict_coordinates_to_node[adj_node_coords]\n",
    "\n",
    "            if df_grid.iloc[adj_node_coords[0],adj_node_coords[1]] == 'X':\n",
    "                continue\n",
    "\n",
    "            if (df_out.iloc[node]['distance'] + d_edge_weight) < df_out.iloc[adj_node]['distance']:\n",
    "                df_out.loc[adj_node,'distance'] = (df_out.iloc[node]['distance'] + d_edge_weight)\n",
    "                df_out.loc[adj_node,'prevnode'] = node\n",
    "    print '*'*25\n",
    "    return df_out, df_nodes, df_grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Grid: 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given the following test Grid, the cells in the grid can be thought of as nodes. So\n",
    "\n",
    "+ A 3 X 3 grid can be thought of as having a 8 nodes."
   ]
  },
  {
   "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",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>S</td>\n",
       "      <td>None</td>\n",
       "      <td>None</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>None</td>\n",
       "      <td>X</td>\n",
       "      <td>None</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>None</td>\n",
       "      <td>None</td>\n",
       "      <td>O</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      0     1     2\n",
       "0     S  None  None\n",
       "1  None     X  None\n",
       "2  None  None     O"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Testing with Grid Layout 1\n",
    "ls_grid =[['S',None,None],\n",
    "          [None,'X',None],\n",
    "          [None,None,'O']]\n",
    "\n",
    "df_out = pd.DataFrame(ls_grid)\n",
    "df_nodes = pd.DataFrame(np.array(range(0,df_out.shape[0]*df_out.shape[1])).reshape(df_out.shape[0],df_out.shape[1]))\n",
    "df_out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "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",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>6</td>\n",
       "      <td>7</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   0  1  2\n",
       "0  0  1  2\n",
       "1  3  4  5\n",
       "2  6  7  8"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ The objective 'O' is at node 8 and source 'S' is at node 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*************************\n",
      "Create Grid Layouts\n",
      "Create the Node Layout\n",
      "Create Node to Grid Coordinates\n",
      "Create Grid Coordinates to Node\n",
      "Initializing the Results Matrix\n",
      "Setting Source & Node Distances\n",
      "Set the Unit Edge Weight 1\n",
      "Create list of Unvisited Nodes\n",
      "Calculate Shortest path across Grid/Nodes\n",
      "Using modified Djikstra\n",
      "*************************\n"
     ]
    }
   ],
   "source": [
    "df_out, df_nodes, df_grid = ShortestPath_DjikstraMod(ls_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "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>distance</th>\n",
       "      <th>prevnode</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0.000000</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1.000000</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2.000000</td>\n",
       "      <td>1.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1.000000</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>2.000000</td>\n",
       "      <td>1.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>2.000000</td>\n",
       "      <td>3.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>2.000000</td>\n",
       "      <td>3.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>3.000000</td>\n",
       "      <td>5.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   distance  prevnode\n",
       "0  0.000000       inf\n",
       "1  1.000000  0.000000\n",
       "2  2.000000  1.000000\n",
       "3  1.000000  0.000000\n",
       "4       inf       inf\n",
       "5  2.000000  1.000000\n",
       "6  2.000000  3.000000\n",
       "7  2.000000  3.000000\n",
       "8  3.000000  5.000000"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Above output can be read as follows.\n",
    "+ To get to the objective 'O' at node 8, we can see that the minimum distance that needs to be travelled is 3. \n",
    "+ The minimum route that needs to be followed can be seen from 'prevnode' column.\n",
    "    + So to reach 'O' at node 8 from 'S' at node 0, we need to traverse through the following nodes 8 <= 5 <= 1 <= 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Grid: 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's take another examples. Given the below test Grid, the cells in the grid can be thought of as nodes. So\n",
    "\n",
    "+ A 4 X 4 grid can be thought of as having a 16 nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "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",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>S</td>\n",
       "      <td>None</td>\n",
       "      <td>None</td>\n",
       "      <td>None</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>None</td>\n",
       "      <td>X</td>\n",
       "      <td>None</td>\n",
       "      <td>None</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>X</td>\n",
       "      <td>None</td>\n",
       "      <td>None</td>\n",
       "      <td>None</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>None</td>\n",
       "      <td>None</td>\n",
       "      <td>None</td>\n",
       "      <td>O</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      0     1     2     3\n",
       "0     S  None  None  None\n",
       "1  None     X  None  None\n",
       "2     X  None  None  None\n",
       "3  None  None  None     O"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Testing with Grid Layout 2\n",
    "ls_grid =[['S',None,None,None],\n",
    "          [None,'X',None,None],\n",
    "          ['X',None,None,None],\n",
    "          [None,None,None,'O']]\n",
    "\n",
    "df_out = pd.DataFrame(ls_grid)\n",
    "df_nodes = pd.DataFrame(np.array(range(0,df_out.shape[0]*df_out.shape[1])).reshape(df_out.shape[0],df_out.shape[1]))\n",
    "df_out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "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",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>4</td>\n",
       "      <td>5</td>\n",
       "      <td>6</td>\n",
       "      <td>7</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>8</td>\n",
       "      <td>9</td>\n",
       "      <td>10</td>\n",
       "      <td>11</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>12</td>\n",
       "      <td>13</td>\n",
       "      <td>14</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    0   1   2   3\n",
       "0   0   1   2   3\n",
       "1   4   5   6   7\n",
       "2   8   9  10  11\n",
       "3  12  13  14  15"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*************************\n",
      "Create Grid Layouts\n",
      "Create the Node Layout\n",
      "Create Node to Grid Coordinates\n",
      "Create Grid Coordinates to Node\n",
      "Initializing the Results Matrix\n",
      "Setting Source & Node Distances\n",
      "Set the Unit Edge Weight 1\n",
      "Create list of Unvisited Nodes\n",
      "Calculate Shortest path across Grid/Nodes\n",
      "Using modified Djikstra\n",
      "*************************\n"
     ]
    }
   ],
   "source": [
    "df_out, df_nodes, df_grid = ShortestPath_DjikstraMod(ls_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "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>distance</th>\n",
       "      <th>prevnode</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0.000000</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1.000000</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2.000000</td>\n",
       "      <td>1.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3.000000</td>\n",
       "      <td>2.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1.000000</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>2.000000</td>\n",
       "      <td>1.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>3.000000</td>\n",
       "      <td>2.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>2.000000</td>\n",
       "      <td>4.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>3.000000</td>\n",
       "      <td>6.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>3.000000</td>\n",
       "      <td>6.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>3.000000</td>\n",
       "      <td>9.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>3.000000</td>\n",
       "      <td>9.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>4.000000</td>\n",
       "      <td>10.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    distance   prevnode\n",
       "0   0.000000        inf\n",
       "1   1.000000   0.000000\n",
       "2   2.000000   1.000000\n",
       "3   3.000000   2.000000\n",
       "4   1.000000   0.000000\n",
       "5        inf        inf\n",
       "6   2.000000   1.000000\n",
       "7   3.000000   2.000000\n",
       "8        inf        inf\n",
       "9   2.000000   4.000000\n",
       "10  3.000000   6.000000\n",
       "11  3.000000   6.000000\n",
       "12       inf        inf\n",
       "13  3.000000   9.000000\n",
       "14  3.000000   9.000000\n",
       "15  4.000000  10.000000"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Above output can be read as follows.\n",
    "+ To get to the objective 'O' at node 15, we can see that the minimum distance that needs to be travelled is 10.\n",
    "+ The minimum route that needs to be followed can be seen from 'prevnode' column.\n",
    "    + So to reach 'O' at node 15 from 'S' at node 0, we need to traverse through the following nodes 15 <= 10 <= 6 <= 1 <= 0"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}