Finding_shortest_path.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Statement \n",
    "\n",
    "This code developes a matrix of more than 28000 rows x 28000 columns to find the distance between two cities. For this I have used a data whihc has longitude, city name, lattitude and state name columns. I have imported the data in python using pandas library. I have used couple of libraries like Pandas, Numpy, Sklearn, seaborn, math to perform basic data analysis on dataset.\n",
    "\n",
    "I have found a matrix which has air distances in between cities in USA."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inporting Libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import seaborn as sns\n",
    "import math\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.neighbors import DistanceMetric\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Importing Data with Pandas pd.read() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "raw_data = pd.read_excel('uscities.xlsx')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "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>city</th>\n",
       "      <th>state_name</th>\n",
       "      <th>lat</th>\n",
       "      <th>lng</th>\n",
       "      <th>population</th>\n",
       "      <th>density</th>\n",
       "      <th>Unnamed: 6</th>\n",
       "      <th>Unnamed: 7</th>\n",
       "      <th>Unnamed: 8</th>\n",
       "      <th>Unnamed: 9</th>\n",
       "      <th>Unnamed: 10</th>\n",
       "      <th>Unnamed: 11</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>New York</td>\n",
       "      <td>New York</td>\n",
       "      <td>40.6943</td>\n",
       "      <td>-73.9249</td>\n",
       "      <td>18713220</td>\n",
       "      <td>10715</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Los Angeles</td>\n",
       "      <td>California</td>\n",
       "      <td>34.1139</td>\n",
       "      <td>-118.4068</td>\n",
       "      <td>12750807</td>\n",
       "      <td>3276</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Chicago</td>\n",
       "      <td>Illinois</td>\n",
       "      <td>41.8373</td>\n",
       "      <td>-87.6862</td>\n",
       "      <td>8604203</td>\n",
       "      <td>4574</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Miami</td>\n",
       "      <td>Florida</td>\n",
       "      <td>25.7839</td>\n",
       "      <td>-80.2102</td>\n",
       "      <td>6445545</td>\n",
       "      <td>5019</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Dallas</td>\n",
       "      <td>Texas</td>\n",
       "      <td>32.7936</td>\n",
       "      <td>-96.7662</td>\n",
       "      <td>5743938</td>\n",
       "      <td>1526</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          city  state_name      lat       lng  population  density  \\\n",
       "0     New York    New York  40.6943  -73.9249    18713220    10715   \n",
       "1  Los Angeles  California  34.1139 -118.4068    12750807     3276   \n",
       "2      Chicago    Illinois  41.8373  -87.6862     8604203     4574   \n",
       "3        Miami     Florida  25.7839  -80.2102     6445545     5019   \n",
       "4       Dallas       Texas  32.7936  -96.7662     5743938     1526   \n",
       "\n",
       "   Unnamed: 6  Unnamed: 7  Unnamed: 8  Unnamed: 9 Unnamed: 10 Unnamed: 11  \n",
       "0         NaN         NaN         NaN         NaN         NaN         NaN  \n",
       "1         NaN         NaN         NaN         NaN         NaN         NaN  \n",
       "2         NaN         NaN         NaN         NaN         NaN         NaN  \n",
       "3         NaN         NaN         NaN         NaN         NaN         NaN  \n",
       "4         NaN         NaN         NaN         NaN         NaN         NaN  "
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "raw_data.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reading data with pd.DataFrame()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "data1 = pd.DataFrame(raw_data.drop(raw_data[['population','density','Unnamed: 6','Unnamed: 7','Unnamed: 8','Unnamed: 9','Unnamed: 10','Unnamed: 11']],axis=1))\n",
    "\n",
    "#data['lat'] = data.lat.astype(float)\n",
    "#data['lng'] = data.lng.astype(float)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reading first 5 lines of dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "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>city</th>\n",
       "      <th>state_name</th>\n",
       "      <th>lat</th>\n",
       "      <th>lng</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>New York</td>\n",
       "      <td>New York</td>\n",
       "      <td>40.6943</td>\n",
       "      <td>-73.9249</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Los Angeles</td>\n",
       "      <td>California</td>\n",
       "      <td>34.1139</td>\n",
       "      <td>-118.4068</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Chicago</td>\n",
       "      <td>Illinois</td>\n",
       "      <td>41.8373</td>\n",
       "      <td>-87.6862</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Miami</td>\n",
       "      <td>Florida</td>\n",
       "      <td>25.7839</td>\n",
       "      <td>-80.2102</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Dallas</td>\n",
       "      <td>Texas</td>\n",
       "      <td>32.7936</td>\n",
       "      <td>-96.7662</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          city  state_name      lat       lng\n",
       "0     New York    New York  40.6943  -73.9249\n",
       "1  Los Angeles  California  34.1139 -118.4068\n",
       "2      Chicago    Illinois  41.8373  -87.6862\n",
       "3        Miami     Florida  25.7839  -80.2102\n",
       "4       Dallas       Texas  32.7936  -96.7662"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data1.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Converting latitude and longitude to radians\n",
    "\n",
    "Used np.radians function to convert the degree values in radian."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "  \n",
    "latitude = np.array(data1['lat'])\n",
    "longitude = np.array(data1['lng']) \n",
    "\n",
    "radian_Values_latitude = np.radians(latitude)\n",
    "radian_Values_longitude = np.radians(longitude)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Used data.insert() function to insert the radian values of latitude in dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "data1.insert(1,'latitudes',radian_Values_latitude)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "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>city</th>\n",
       "      <th>latitudes</th>\n",
       "      <th>state_name</th>\n",
       "      <th>lat</th>\n",
       "      <th>lng</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>New York</td>\n",
       "      <td>0.710250</td>\n",
       "      <td>New York</td>\n",
       "      <td>40.6943</td>\n",
       "      <td>-73.9249</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Los Angeles</td>\n",
       "      <td>0.595400</td>\n",
       "      <td>California</td>\n",
       "      <td>34.1139</td>\n",
       "      <td>-118.4068</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Chicago</td>\n",
       "      <td>0.730199</td>\n",
       "      <td>Illinois</td>\n",
       "      <td>41.8373</td>\n",
       "      <td>-87.6862</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Miami</td>\n",
       "      <td>0.450014</td>\n",
       "      <td>Florida</td>\n",
       "      <td>25.7839</td>\n",
       "      <td>-80.2102</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Dallas</td>\n",
       "      <td>0.572356</td>\n",
       "      <td>Texas</td>\n",
       "      <td>32.7936</td>\n",
       "      <td>-96.7662</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          city  latitudes  state_name      lat       lng\n",
       "0     New York   0.710250    New York  40.6943  -73.9249\n",
       "1  Los Angeles   0.595400  California  34.1139 -118.4068\n",
       "2      Chicago   0.730199    Illinois  41.8373  -87.6862\n",
       "3        Miami   0.450014     Florida  25.7839  -80.2102\n",
       "4       Dallas   0.572356       Texas  32.7936  -96.7662"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data1.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Used data.insert() function to insert the radian values of longitude in dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "data1.insert(2,'longitudes',radian_Values_longitude)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "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>city</th>\n",
       "      <th>latitudes</th>\n",
       "      <th>longitudes</th>\n",
       "      <th>state_name</th>\n",
       "      <th>lat</th>\n",
       "      <th>lng</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>New York</td>\n",
       "      <td>0.710250</td>\n",
       "      <td>-1.290233</td>\n",
       "      <td>New York</td>\n",
       "      <td>40.6943</td>\n",
       "      <td>-73.9249</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Los Angeles</td>\n",
       "      <td>0.595400</td>\n",
       "      <td>-2.066589</td>\n",
       "      <td>California</td>\n",
       "      <td>34.1139</td>\n",
       "      <td>-118.4068</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Chicago</td>\n",
       "      <td>0.730199</td>\n",
       "      <td>-1.530413</td>\n",
       "      <td>Illinois</td>\n",
       "      <td>41.8373</td>\n",
       "      <td>-87.6862</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Miami</td>\n",
       "      <td>0.450014</td>\n",
       "      <td>-1.399932</td>\n",
       "      <td>Florida</td>\n",
       "      <td>25.7839</td>\n",
       "      <td>-80.2102</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Dallas</td>\n",
       "      <td>0.572356</td>\n",
       "      <td>-1.688889</td>\n",
       "      <td>Texas</td>\n",
       "      <td>32.7936</td>\n",
       "      <td>-96.7662</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          city  latitudes  longitudes  state_name      lat       lng\n",
       "0     New York   0.710250   -1.290233    New York  40.6943  -73.9249\n",
       "1  Los Angeles   0.595400   -2.066589  California  34.1139 -118.4068\n",
       "2      Chicago   0.730199   -1.530413    Illinois  41.8373  -87.6862\n",
       "3        Miami   0.450014   -1.399932     Florida  25.7839  -80.2102\n",
       "4       Dallas   0.572356   -1.688889       Texas  32.7936  -96.7662"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data1.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Importing the Haversine distance from Sklearn\n",
    "\n",
    "from sklearn.neighbors import DistanceMetric\n",
    "\n",
    "Starting of the code I have imported the DistanceMetric from skelearn. then imported the haversine distance which calculates the air distance between two points. I have used Haversine distance because, earth is round and we cannot use the Euclidean distance or Manhattan distance to calculate the distance. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "final_data = pd.DataFrame(data1)\n",
    "\n",
    "dist = DistanceMetric.get_metric('haversine')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Used pairwise function to make pair of distance between each city"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "distance_matrix = dist.pairwise(final_data[['latitudes','longitudes']].to_numpy())*3958"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Below shows distance of array for each row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[   0.        , 2456.20161132,  718.11587345, ..., 1169.50272964,\n",
       "        1267.67805258, 1261.67605276],\n",
       "       [2456.20161132,    0.        , 1745.0942964 , ..., 1489.34166064,\n",
       "        1238.71537183, 1237.07696475],\n",
       "       [ 718.11587345, 1745.0942964 ,    0.        , ...,  546.03166846,\n",
       "         628.84049541,  547.45743571],\n",
       "       ...,\n",
       "       [1169.50272964, 1489.34166064,  546.03166846, ...,    0.        ,\n",
       "         789.40132591,  335.62934086],\n",
       "       [1267.67805258, 1238.71537183,  628.84049541, ...,  789.40132591,\n",
       "           0.        ,  487.03458441],\n",
       "       [1261.67605276, 1237.07696475,  547.45743571, ...,  335.62934086,\n",
       "         487.03458441,    0.        ]])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Converted name of city to List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "cities = list(final_data['city'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Used pd.DataFrame to make final Data Frame"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "distance_matrix = pd.DataFrame(distance_matrix, columns = cities, index = cities)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Rows are source city and columns are destination city\n"
     ]
    }
   ],
   "source": [
    "print('\\nRows are source city and columns are destination city')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Final Distance matrix\n",
    "Below the matrix, it is showing the 28338 rows by 28338 columns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "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>New York</th>\n",
       "      <th>Los Angeles</th>\n",
       "      <th>Chicago</th>\n",
       "      <th>Miami</th>\n",
       "      <th>Dallas</th>\n",
       "      <th>Philadelphia</th>\n",
       "      <th>Houston</th>\n",
       "      <th>Atlanta</th>\n",
       "      <th>Washington</th>\n",
       "      <th>Boston</th>\n",
       "      <th>...</th>\n",
       "      <th>Poso Park</th>\n",
       "      <th>White Rock</th>\n",
       "      <th>Warm River</th>\n",
       "      <th>Four Mile Road</th>\n",
       "      <th>Portage Creek</th>\n",
       "      <th>Gross</th>\n",
       "      <th>Lotsee</th>\n",
       "      <th>The Ranch</th>\n",
       "      <th>Shamrock</th>\n",
       "      <th>Monowi</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>New York</th>\n",
       "      <td>0.000000</td>\n",
       "      <td>2456.201611</td>\n",
       "      <td>718.115873</td>\n",
       "      <td>1091.354772</td>\n",
       "      <td>1371.901723</td>\n",
       "      <td>79.375931</td>\n",
       "      <td>1420.383285</td>\n",
       "      <td>749.146798</td>\n",
       "      <td>205.410224</td>\n",
       "      <td>184.870272</td>\n",
       "      <td>...</td>\n",
       "      <td>2422.533395</td>\n",
       "      <td>1189.818241</td>\n",
       "      <td>1905.441172</td>\n",
       "      <td>3300.034585</td>\n",
       "      <td>3665.273352</td>\n",
       "      <td>1273.614794</td>\n",
       "      <td>1242.896880</td>\n",
       "      <td>1169.502730</td>\n",
       "      <td>1267.678053</td>\n",
       "      <td>1261.676053</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Los Angeles</th>\n",
       "      <td>2456.201611</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>1745.094296</td>\n",
       "      <td>2343.078668</td>\n",
       "      <td>1248.269387</td>\n",
       "      <td>2396.098641</td>\n",
       "      <td>1378.731022</td>\n",
       "      <td>1938.738082</td>\n",
       "      <td>2302.024675</td>\n",
       "      <td>2595.614170</td>\n",
       "      <td>...</td>\n",
       "      <td>117.981609</td>\n",
       "      <td>1406.438612</td>\n",
       "      <td>787.893782</td>\n",
       "      <td>2467.392793</td>\n",
       "      <td>2471.368265</td>\n",
       "      <td>1228.960643</td>\n",
       "      <td>1259.172195</td>\n",
       "      <td>1489.341661</td>\n",
       "      <td>1238.715372</td>\n",
       "      <td>1237.076965</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Chicago</th>\n",
       "      <td>718.115873</td>\n",
       "      <td>1745.094296</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>1187.866529</td>\n",
       "      <td>798.465091</td>\n",
       "      <td>666.625279</td>\n",
       "      <td>936.679565</td>\n",
       "      <td>585.424434</td>\n",
       "      <td>596.475696</td>\n",
       "      <td>850.521764</td>\n",
       "      <td>...</td>\n",
       "      <td>1706.860961</td>\n",
       "      <td>524.552352</td>\n",
       "      <td>1200.590555</td>\n",
       "      <td>2828.484624</td>\n",
       "      <td>3132.169624</td>\n",
       "      <td>560.120458</td>\n",
       "      <td>603.351854</td>\n",
       "      <td>546.031668</td>\n",
       "      <td>628.840495</td>\n",
       "      <td>547.457436</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Miami</th>\n",
       "      <td>1091.354772</td>\n",
       "      <td>2343.078668</td>\n",
       "      <td>1187.866529</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>1106.967323</td>\n",
       "      <td>1025.251537</td>\n",
       "      <td>967.078342</td>\n",
       "      <td>606.114819</td>\n",
       "      <td>925.172821</td>\n",
       "      <td>1254.117415</td>\n",
       "      <td>...</td>\n",
       "      <td>2366.150581</td>\n",
       "      <td>1658.652278</td>\n",
       "      <td>2148.412588</td>\n",
       "      <td>3997.447300</td>\n",
       "      <td>4265.099897</td>\n",
       "      <td>1574.411603</td>\n",
       "      <td>1184.374795</td>\n",
       "      <td>1710.803379</td>\n",
       "      <td>1193.688656</td>\n",
       "      <td>1560.089592</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Dallas</th>\n",
       "      <td>1371.901723</td>\n",
       "      <td>1248.269387</td>\n",
       "      <td>798.465091</td>\n",
       "      <td>1106.967323</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>1297.662434</td>\n",
       "      <td>223.080988</td>\n",
       "      <td>715.583415</td>\n",
       "      <td>1180.679405</td>\n",
       "      <td>1544.629485</td>\n",
       "      <td>...</td>\n",
       "      <td>1262.582607</td>\n",
       "      <td>907.161157</td>\n",
       "      <td>1106.686404</td>\n",
       "      <td>3095.393605</td>\n",
       "      <td>3284.950879</td>\n",
       "      <td>708.147674</td>\n",
       "      <td>232.884029</td>\n",
       "      <td>1005.041596</td>\n",
       "      <td>215.640531</td>\n",
       "      <td>698.556605</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Gross</th>\n",
       "      <td>1273.614794</td>\n",
       "      <td>1228.960643</td>\n",
       "      <td>560.120458</td>\n",
       "      <td>1574.411603</td>\n",
       "      <td>708.147674</td>\n",
       "      <td>1225.690996</td>\n",
       "      <td>925.942088</td>\n",
       "      <td>992.480696</td>\n",
       "      <td>1155.569333</td>\n",
       "      <td>1391.317908</td>\n",
       "      <td>...</td>\n",
       "      <td>1175.493627</td>\n",
       "      <td>228.041485</td>\n",
       "      <td>643.016319</td>\n",
       "      <td>2446.759932</td>\n",
       "      <td>2691.538855</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>487.075431</td>\n",
       "      <td>332.970351</td>\n",
       "      <td>497.415005</td>\n",
       "      <td>14.533738</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Lotsee</th>\n",
       "      <td>1242.896880</td>\n",
       "      <td>1259.172195</td>\n",
       "      <td>603.351854</td>\n",
       "      <td>1184.374795</td>\n",
       "      <td>232.884029</td>\n",
       "      <td>1173.959098</td>\n",
       "      <td>441.022333</td>\n",
       "      <td>686.707848</td>\n",
       "      <td>1066.790130</td>\n",
       "      <td>1404.737132</td>\n",
       "      <td>...</td>\n",
       "      <td>1251.238595</td>\n",
       "      <td>676.659233</td>\n",
       "      <td>967.779338</td>\n",
       "      <td>2910.742823</td>\n",
       "      <td>3124.715023</td>\n",
       "      <td>487.075431</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>773.207161</td>\n",
       "      <td>25.658604</td>\n",
       "      <td>476.217543</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>The Ranch</th>\n",
       "      <td>1169.502730</td>\n",
       "      <td>1489.341661</td>\n",
       "      <td>546.031668</td>\n",
       "      <td>1710.803379</td>\n",
       "      <td>1005.041596</td>\n",
       "      <td>1140.237032</td>\n",
       "      <td>1211.326939</td>\n",
       "      <td>1105.248036</td>\n",
       "      <td>1102.613296</td>\n",
       "      <td>1248.522193</td>\n",
       "      <td>...</td>\n",
       "      <td>1419.063330</td>\n",
       "      <td>105.035694</td>\n",
       "      <td>783.813237</td>\n",
       "      <td>2289.289630</td>\n",
       "      <td>2586.150713</td>\n",
       "      <td>332.970351</td>\n",
       "      <td>773.207161</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>789.401326</td>\n",
       "      <td>335.629341</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Shamrock</th>\n",
       "      <td>1267.678053</td>\n",
       "      <td>1238.715372</td>\n",
       "      <td>628.840495</td>\n",
       "      <td>1193.688656</td>\n",
       "      <td>215.640531</td>\n",
       "      <td>1198.510308</td>\n",
       "      <td>428.687017</td>\n",
       "      <td>704.464093</td>\n",
       "      <td>1090.858039</td>\n",
       "      <td>1429.913150</td>\n",
       "      <td>...</td>\n",
       "      <td>1232.363628</td>\n",
       "      <td>691.733903</td>\n",
       "      <td>961.881063</td>\n",
       "      <td>2913.495798</td>\n",
       "      <td>3123.407636</td>\n",
       "      <td>497.415005</td>\n",
       "      <td>25.658604</td>\n",
       "      <td>789.401326</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>487.034584</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Monowi</th>\n",
       "      <td>1261.676053</td>\n",
       "      <td>1237.076965</td>\n",
       "      <td>547.457436</td>\n",
       "      <td>1560.089592</td>\n",
       "      <td>698.556605</td>\n",
       "      <td>1213.340535</td>\n",
       "      <td>915.690550</td>\n",
       "      <td>977.954589</td>\n",
       "      <td>1142.582565</td>\n",
       "      <td>1380.354826</td>\n",
       "      <td>...</td>\n",
       "      <td>1184.647164</td>\n",
       "      <td>230.595923</td>\n",
       "      <td>656.552736</td>\n",
       "      <td>2460.243691</td>\n",
       "      <td>2705.755985</td>\n",
       "      <td>14.533738</td>\n",
       "      <td>476.217543</td>\n",
       "      <td>335.629341</td>\n",
       "      <td>487.034584</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>28338 rows × 28338 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "                New York  Los Angeles      Chicago        Miami       Dallas  \\\n",
       "New York        0.000000  2456.201611   718.115873  1091.354772  1371.901723   \n",
       "Los Angeles  2456.201611     0.000000  1745.094296  2343.078668  1248.269387   \n",
       "Chicago       718.115873  1745.094296     0.000000  1187.866529   798.465091   \n",
       "Miami        1091.354772  2343.078668  1187.866529     0.000000  1106.967323   \n",
       "Dallas       1371.901723  1248.269387   798.465091  1106.967323     0.000000   \n",
       "...                  ...          ...          ...          ...          ...   \n",
       "Gross        1273.614794  1228.960643   560.120458  1574.411603   708.147674   \n",
       "Lotsee       1242.896880  1259.172195   603.351854  1184.374795   232.884029   \n",
       "The Ranch    1169.502730  1489.341661   546.031668  1710.803379  1005.041596   \n",
       "Shamrock     1267.678053  1238.715372   628.840495  1193.688656   215.640531   \n",
       "Monowi       1261.676053  1237.076965   547.457436  1560.089592   698.556605   \n",
       "\n",
       "             Philadelphia      Houston      Atlanta   Washington       Boston  \\\n",
       "New York        79.375931  1420.383285   749.146798   205.410224   184.870272   \n",
       "Los Angeles   2396.098641  1378.731022  1938.738082  2302.024675  2595.614170   \n",
       "Chicago        666.625279   936.679565   585.424434   596.475696   850.521764   \n",
       "Miami         1025.251537   967.078342   606.114819   925.172821  1254.117415   \n",
       "Dallas        1297.662434   223.080988   715.583415  1180.679405  1544.629485   \n",
       "...                   ...          ...          ...          ...          ...   \n",
       "Gross         1225.690996   925.942088   992.480696  1155.569333  1391.317908   \n",
       "Lotsee        1173.959098   441.022333   686.707848  1066.790130  1404.737132   \n",
       "The Ranch     1140.237032  1211.326939  1105.248036  1102.613296  1248.522193   \n",
       "Shamrock      1198.510308   428.687017   704.464093  1090.858039  1429.913150   \n",
       "Monowi        1213.340535   915.690550   977.954589  1142.582565  1380.354826   \n",
       "\n",
       "             ...    Poso Park   White Rock   Warm River  Four Mile Road  \\\n",
       "New York     ...  2422.533395  1189.818241  1905.441172     3300.034585   \n",
       "Los Angeles  ...   117.981609  1406.438612   787.893782     2467.392793   \n",
       "Chicago      ...  1706.860961   524.552352  1200.590555     2828.484624   \n",
       "Miami        ...  2366.150581  1658.652278  2148.412588     3997.447300   \n",
       "Dallas       ...  1262.582607   907.161157  1106.686404     3095.393605   \n",
       "...          ...          ...          ...          ...             ...   \n",
       "Gross        ...  1175.493627   228.041485   643.016319     2446.759932   \n",
       "Lotsee       ...  1251.238595   676.659233   967.779338     2910.742823   \n",
       "The Ranch    ...  1419.063330   105.035694   783.813237     2289.289630   \n",
       "Shamrock     ...  1232.363628   691.733903   961.881063     2913.495798   \n",
       "Monowi       ...  1184.647164   230.595923   656.552736     2460.243691   \n",
       "\n",
       "             Portage Creek        Gross       Lotsee    The Ranch  \\\n",
       "New York       3665.273352  1273.614794  1242.896880  1169.502730   \n",
       "Los Angeles    2471.368265  1228.960643  1259.172195  1489.341661   \n",
       "Chicago        3132.169624   560.120458   603.351854   546.031668   \n",
       "Miami          4265.099897  1574.411603  1184.374795  1710.803379   \n",
       "Dallas         3284.950879   708.147674   232.884029  1005.041596   \n",
       "...                    ...          ...          ...          ...   \n",
       "Gross          2691.538855     0.000000   487.075431   332.970351   \n",
       "Lotsee         3124.715023   487.075431     0.000000   773.207161   \n",
       "The Ranch      2586.150713   332.970351   773.207161     0.000000   \n",
       "Shamrock       3123.407636   497.415005    25.658604   789.401326   \n",
       "Monowi         2705.755985    14.533738   476.217543   335.629341   \n",
       "\n",
       "                Shamrock       Monowi  \n",
       "New York     1267.678053  1261.676053  \n",
       "Los Angeles  1238.715372  1237.076965  \n",
       "Chicago       628.840495   547.457436  \n",
       "Miami        1193.688656  1560.089592  \n",
       "Dallas        215.640531   698.556605  \n",
       "...                  ...          ...  \n",
       "Gross         497.415005    14.533738  \n",
       "Lotsee         25.658604   476.217543  \n",
       "The Ranch     789.401326   335.629341  \n",
       "Shamrock        0.000000   487.034584  \n",
       "Monowi        487.034584     0.000000  \n",
       "\n",
       "[28338 rows x 28338 columns]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Finding the distance between two cities from Data Frame"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "#city1 = input(\"Enter the city 1: \")\n",
    "#city2 = input(\"Enter the city 2: \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Function to find the distance from latitude and longitude"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_air_distance(lat1,lon1,lat2,lon2):\n",
    "    radius_of_earth = 3958.80 #radius of the Earth in miles\n",
    "\n",
    "    #converting in radians \n",
    "\n",
    "    lat1 = math.radians(lat1)\n",
    "    lon1 = math.radians(lon2)\n",
    "    lat1 = math.radians(lat1)\n",
    "    lon2 = math.radians(lon2)\n",
    "    \n",
    "    dlon = lon2 - lon1 #change in coordinates\n",
    "    dlat = lat2 - lat1 #change in coordinates\n",
    "\n",
    "    #Haversine formula\n",
    "    a = math.sin(dlat / 2)**2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlon / 2)**2 \n",
    "\n",
    "    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))\n",
    "    distance = radius_of_earth * c\n",
    "\n",
    "    return(distance)"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}