dijkstras_algorithm_p1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''import the required packages/libraries'''\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''create a graph with the nodes and their weights'''\n",
    "distances= {\n",
    "           'S': {'A': 7, 'B': 2, 'C': 3},\n",
    "           'A':{'S': 7, 'B': 3, 'D': 4},\n",
    "           'B':{'S': 2, 'A': 3, 'D': 4, 'H': 1, 'C': 12},\n",
    "           'C':{'S': 3, 'L': 2},\n",
    "           'D':{'A': 4, 'B': 4, 'F': 5},\n",
    "           'E':{'G': 2, 'K': 5} , \n",
    "           'F':{'D': 5, 'H': 3},\n",
    "           'G':{'H': 2, 'I': 10, 'E': 2},\n",
    "           'H':{'B': 1, 'F': 3, 'G': 2},\n",
    "           'I':{'J': 6, 'K': 4, 'L': 4},\n",
    "           'J':{'K': 4, 'L': 4},\n",
    "           'K':{'I': 4, 'J': 4, 'E': 5},\n",
    "           'L':{'C': 2, 'I': 4, 'J': 4}\n",
    "           }\n",
    "\n",
    "'''next create two dictionaries, one to store the predecessor nodes and the other to \n",
    "store and update the weights of the nodes as the algorithm progresses'''\n",
    "city_records= {}\n",
    "dist_records= {}\n",
    "\n",
    "'''duplicate the graph and populate it with infinity values'''\n",
    "for k in distances.keys():\n",
    "    dist_records[k]= float('Inf')\n",
    "    city_records[k]= None\n",
    "        \n",
    "'''create a list to store all visited nodes'''        \n",
    "visited= []\n",
    "\n",
    "'''assign the start and end nodes to two variables'''\n",
    "start= 'S'\n",
    "end= 'E'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''function that selected the unvisited node with the least total distance from the start node'''\n",
    "def pick_node(dist_records):\n",
    "    \n",
    "    dist_records2= copy.deepcopy(dist_records)\n",
    "    for node in visited:\n",
    "        del dist_records2[node]\n",
    "        \n",
    "    return min(dist_records2, key= dist_records2.get)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortest_path(start_node, end_node, records):\n",
    "    \n",
    "    shortest_path= [end_node]\n",
    "    while True:\n",
    "        shortest_path.append(records.get(end_node))\n",
    "        end_node= records.get(end_node)\n",
    "\n",
    "        if end_node == start_node:\n",
    "            break\n",
    "\n",
    "    '''reverse the list to get the nodes from start to end'''        \n",
    "    return shortest_path[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def djikstras_algo(start, end, dist_records, city_records, visited):\n",
    "    '''update the two dictionaries to make sure that the weight of the start node is 0 and \n",
    "    it's predecessor node is itself'''\n",
    "    \n",
    "    dist_records[start]= 0\n",
    "    city_records[start]= start\n",
    "\n",
    "    if start == end:\n",
    "        print('shortest path is {}'.format(0))\n",
    "\n",
    "    while True:    \n",
    "        node= pick_node(dist_records)\n",
    "        for k in distances[node].keys():\n",
    "            if k in visited:\n",
    "                continue\n",
    "\n",
    "            if dist_records[node] + distances[node].get(k) < dist_records[k]:\n",
    "                dist_records[k]= dist_records[node] + distances[node].get(k)\n",
    "                city_records[k]= node\n",
    "\n",
    "        visited.append(node)\n",
    "\n",
    "        if end in visited:\n",
    "            break\n",
    "\n",
    "    print('Shortest path is: ', shortest_path(start_node= start, end_node= end, records= city_records))\n",
    "    print('Shortest distance is: {} miles'.format(dist_records.get(end)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Shortest path is:  ['S', 'B', 'H', 'G', 'E']\n",
      "Shortest distance is: 7 miles\n"
     ]
    }
   ],
   "source": [
    "djikstras_algo(start, end, dist_records, city_records, visited)"
   ]
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}