{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solution Notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: Find the shortest path between two nodes in a graph.\n",
    "\n",
    "* [Constraints](#Constraints)\n",
    "* [Test Cases](#Test-Cases)\n",
    "* [Algorithm](#Algorithm)\n",
    "* [Code](#Code)\n",
    "* [Unit Test](#Unit-Test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constraints\n",
    "\n",
    "* Is this a directional graph?\n",
    "    * Yes\n",
    "* Could the graph have cycles?\n",
    "    * Yes\n",
    "    * Note: If the answer were no, this would be a DAG.  \n",
    "        * DAGs can be solved with a [topological sort](http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/)\n",
    "* Are the edges weighted?\n",
    "    * Yes\n",
    "    * Note: If the edges were not weighted, we could do a BFS\n",
    "* Are the edges all non-negative numbers?\n",
    "    * Yes\n",
    "    * Note: Graphs with negative edges can be done with Bellman-Ford\n",
    "        * Graphs with negative cost cycles do not have a defined shortest path\n",
    "* Do we have to check for non-negative edges?\n",
    "    * No\n",
    "* Can we assume this is a connected graph?\n",
    "    * Yes\n",
    "* Can we assume the inputs are valid?\n",
    "    * No\n",
    "* Can we assume we already have a graph class?\n",
    "    * Yes\n",
    "* Can we assume we already have a priority queue class?\n",
    "    * Yes\n",
    "* Can we assume this fits memory?\n",
    "    * Yes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Cases\n",
    "\n",
    "The constraints state we don't have to check for negative edges, so we test with the general case.\n",
    "\n",
    "<pre>\n",
    "graph.add_edge('a', 'b', weight=5)\n",
    "graph.add_edge('a', 'c', weight=3)\n",
    "graph.add_edge('a', 'e', weight=2)\n",
    "graph.add_edge('b', 'd', weight=2)\n",
    "graph.add_edge('c', 'b', weight=1)\n",
    "graph.add_edge('c', 'd', weight=1)\n",
    "graph.add_edge('d', 'a', weight=1)\n",
    "graph.add_edge('d', 'g', weight=2)\n",
    "graph.add_edge('d', 'h', weight=1)\n",
    "graph.add_edge('e', 'a', weight=1)\n",
    "graph.add_edge('e', 'h', weight=4)\n",
    "graph.add_edge('e', 'i', weight=7)\n",
    "graph.add_edge('f', 'b', weight=3)\n",
    "graph.add_edge('f', 'g', weight=1)\n",
    "graph.add_edge('g', 'c', weight=3)\n",
    "graph.add_edge('g', 'i', weight=2)\n",
    "graph.add_edge('h', 'c', weight=2)\n",
    "graph.add_edge('h', 'f', weight=2)\n",
    "graph.add_edge('h', 'g', weight=2)\n",
    "shortest_path = ShortestPath(graph)\n",
    "result = shortest_path.find_shortest_path('a', 'i')\n",
    "self.assertEqual(result, ['a', 'c', 'd', 'g', 'i'])\n",
    "self.assertEqual(shortest_path.path_weight['i'], 8)\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm\n",
    "\n",
    "Wikipedia's animation:\n",
    "\n",
    "![](https://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif)\n",
    "\n",
    "Initialize the following:\n",
    "\n",
    "* previous = {}  # Key: node key, val: prev node key, shortest path\n",
    "    * Set each node's previous node key to None\n",
    "* path_weight = {}  # Key: node key, val: weight, shortest path\n",
    "    * Set each node's shortest path weight to infinity\n",
    "* remaining = PriorityQueue()  # Queue of node key, path weight\n",
    "    * Add each node's shortest path weight to the priority queue\n",
    "\n",
    "* Set the start node's path_weight to 0 and update the value in remaining\n",
    "* Loop while remaining still has items\n",
    "    * Extract the min node (node with minimum path weight) from remaining\n",
    "    * Loop through each adjacent node in the min node\n",
    "        * Calculate the new weight:\n",
    "            * Adjacent node's edge weight + the min node's path_weight            \n",
    "        * If the newly calculated path is less than the adjacent node's current path_weight:\n",
    "            * Set the node's previous node key leading to the shortest path\n",
    "            * Update the adjacent node's shortest path and update the value in the priority queue\n",
    "* Walk backwards to determine the shortest path:\n",
    "    * Start at the end node, walk the previous dict to get to the start node\n",
    "* Reverse the list and return it\n",
    "\n",
    "### Complexity for array-based priority queue:\n",
    "\n",
    "* Time: O(v^2), where v is the number of vertices\n",
    "* Space: O(v^2)\n",
    "\n",
    "This might be better than the min-heap-based variant if the graph has a lot of edges.\n",
    "\n",
    "O(v^2) is better than O((v + v^2) log v).\n",
    "\n",
    "### Complexity for min-heap-based priority queue:\n",
    "\n",
    "* Time: O((v + e) log v), where v is the number of vertices, e is the number of edges\n",
    "* Space: O((v + e) log v)\n",
    "\n",
    "This might be better than the array-based variant if the graph is sparse."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%run ../../arrays_strings/priority_queue/priority_queue.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "%run ../graph/graph.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "\n",
    "class ShortestPath(object):\n",
    "\n",
    "    def __init__(self, graph):\n",
    "        if graph is None:\n",
    "            raise TypeError('graph cannot be None')\n",
    "        self.graph = graph\n",
    "        self.previous = {}  # Key: node key, val: prev node key, shortest path\n",
    "        self.path_weight = {}  # Key: node key, val: weight, shortest path\n",
    "        self.remaining = PriorityQueue()  # Queue of node key, path weight\n",
    "        for key in self.graph.nodes.keys():\n",
    "            # Set each node's previous node key to None\n",
    "            # Set each node's shortest path weight to infinity\n",
    "            # Add each node's shortest path weight to the priority queue\n",
    "            self.previous[key] = None\n",
    "            self.path_weight[key] = sys.maxsize\n",
    "            self.remaining.insert(\n",
    "                PriorityQueueNode(key, self.path_weight[key]))\n",
    "\n",
    "    def find_shortest_path(self, start_node_key, end_node_key):\n",
    "        if start_node_key is None or end_node_key is None:\n",
    "            raise TypeError('Input node keys cannot be None')\n",
    "        if (start_node_key not in self.graph.nodes or\n",
    "                end_node_key not in self.graph.nodes):\n",
    "            raise ValueError('Invalid start or end node key')\n",
    "        # Set the start node's shortest path weight to 0\n",
    "        # and update the value in the priority queue\n",
    "        self.path_weight[start_node_key] = 0\n",
    "        self.remaining.decrease_key(start_node_key, 0)\n",
    "        while self.remaining:\n",
    "            # Extract the min node (node with minimum path weight)\n",
    "            # from the priority queue\n",
    "            min_node_key = self.remaining.extract_min().obj\n",
    "            min_node = self.graph.nodes[min_node_key]\n",
    "            # Loop through each adjacent node in the min node\n",
    "            for adj_key in min_node.adj_nodes.keys():\n",
    "                # Node's path:\n",
    "                # Adjacent node's edge weight + the min node's\n",
    "                # shortest path weight\n",
    "                new_weight = (min_node.adj_weights[adj_key] +\n",
    "                    self.path_weight[min_node_key])\n",
    "                # Only update if the newly calculated path is\n",
    "                # less than the existing node's shortest path\n",
    "                if self.path_weight[adj_key] > new_weight:\n",
    "                    # Set the node's previous node key leading to the shortest path\n",
    "                    # Update the adjacent node's shortest path and\n",
    "                    # update the value in the priority queue\n",
    "                    self.previous[adj_key] = min_node_key\n",
    "                    self.path_weight[adj_key] = new_weight\n",
    "                    self.remaining.decrease_key(adj_key, new_weight)\n",
    "        # Walk backwards to determine the shortest path:\n",
    "        # Start at the end node, walk the previous dict to get to the start node\n",
    "        result = []\n",
    "        current_node_key = end_node_key\n",
    "        while current_node_key is not None:\n",
    "            result.append(current_node_key)\n",
    "            current_node_key = self.previous[current_node_key]\n",
    "        # Reverse the list\n",
    "        return result[::-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unit Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting test_shortest_path.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile test_shortest_path.py\n",
    "import unittest\n",
    "\n",
    "\n",
    "class TestShortestPath(unittest.TestCase):\n",
    "\n",
    "    def test_shortest_path(self):\n",
    "        graph = Graph()\n",
    "        graph.add_edge('a', 'b', weight=5)\n",
    "        graph.add_edge('a', 'c', weight=3)\n",
    "        graph.add_edge('a', 'e', weight=2)\n",
    "        graph.add_edge('b', 'd', weight=2)\n",
    "        graph.add_edge('c', 'b', weight=1)\n",
    "        graph.add_edge('c', 'd', weight=1)\n",
    "        graph.add_edge('d', 'a', weight=1)\n",
    "        graph.add_edge('d', 'g', weight=2)\n",
    "        graph.add_edge('d', 'h', weight=1)\n",
    "        graph.add_edge('e', 'a', weight=1)\n",
    "        graph.add_edge('e', 'h', weight=4)\n",
    "        graph.add_edge('e', 'i', weight=7)\n",
    "        graph.add_edge('f', 'b', weight=3)\n",
    "        graph.add_edge('f', 'g', weight=1)\n",
    "        graph.add_edge('g', 'c', weight=3)\n",
    "        graph.add_edge('g', 'i', weight=2)\n",
    "        graph.add_edge('h', 'c', weight=2)\n",
    "        graph.add_edge('h', 'f', weight=2)\n",
    "        graph.add_edge('h', 'g', weight=2)\n",
    "        shortest_path = ShortestPath(graph)\n",
    "        result = shortest_path.find_shortest_path('a', 'i')\n",
    "        self.assertEqual(result, ['a', 'c', 'd', 'g', 'i'])\n",
    "        self.assertEqual(shortest_path.path_weight['i'], 8)\n",
    "\n",
    "        print('Success: test_shortest_path')\n",
    "\n",
    "\n",
    "def main():\n",
    "    test = TestShortestPath()\n",
    "    test.test_shortest_path()\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success: test_shortest_path\n"
     ]
    }
   ],
   "source": [
    "%run -i test_shortest_path.py"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}