ipython_nbs/search/dijkstra-algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sebastian Raschka \n",
      "last updated: 2017-08-09 \n",
      "\n",
      "CPython 3.6.1\n",
      "IPython 6.1.0\n"
     ]
    }
   ],
   "source": [
    "%load_ext watermark\n",
    "%watermark -a 'Sebastian Raschka' -u -d -v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dijkstra's Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dijkstra's algorithm is an algorithm that finds the shortest path in a directed or undirected graph. In contrast to [Breadth-First Search](breadth-first-search.ipynb), Dijkstra's algorithm works with **weighted graphs** -- that is, graphs that have different costs or length assigned to its edges. However, note that Dijkstra's algorithm does *not* work if the graph contains negative weights (in this case, different algorithms need to be used, for example, the Bellman-Ford algorithm). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A great and concise explanation of Dijkstra's algorithm was written on Wikipedia:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "> \n",
    "Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step.\n",
    "1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.\n",
    "2. Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.\n",
    "3. For the current node, consider all of its neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.\n",
    "4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.\n",
    "5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.\n",
    "6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new \"current node\", and go back to step 3.  \n",
    ">\n",
    "[Source: Wikipedia, https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In addition, a great way to study Dijkstra's algorithm is to work through an example by hand, before we implement it in Python:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/dijkstra-algorithm/dijkstra-1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/dijkstra-algorithm/dijkstra-2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/dijkstra-algorithm/dijkstra-3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/dijkstra-algorithm/dijkstra-3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/dijkstra-algorithm/dijkstra-4.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/dijkstra-algorithm/dijkstra-5.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/dijkstra-algorithm/dijkstra-6.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/dijkstra-algorithm/dijkstra-7.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/dijkstra-algorithm/dijkstra-8.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/dijkstra-algorithm/dijkstra-9.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before we implement Dijkstra's algorithm, let's convert the graph from the example above into a data structure that we could use. When we are woking with graphs, hash tables are naturally a good choice (aka Python dictionaries). Since we do not only need to sort information about which nodes are connected to each other but also have to keep track of the costs of the connections, let's use a nested dictionary that we call `graph`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = {'A': {'B': 14, 'C': 9, 'D': 7},\n",
    "         'B': {'A': 14, 'C': 2, 'F': 9},\n",
    "         'C': {'A':  9, 'B': 2, 'D': 7, 'E': 11},\n",
    "         'D': {'A':  7, 'C':10, 'E':15},\n",
    "         'E': {'C': 11, 'D':15, 'F': 6},\n",
    "         'F': {'B':  9, 'E': 6}\n",
    "        }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, to get the cost of the edge connecting C and B, we can use the dictionary as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph['C']['B']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# equivalently:\n",
    "graph['B']['C']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "float('inf') > 99"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Costs: {'A': 0, 'B': 11, 'C': 9, 'D': 7, 'E': 20, 'F': 20}\n",
      "Parent Nodes: {'B': 'C', 'C': 'A', 'D': 'A', 'E': 'C', 'F': 'B'}\n"
     ]
    }
   ],
   "source": [
    "def dijkstra(graph, start, destination):\n",
    "\n",
    "    # initialize costs of starting node and its neighbors\n",
    "    costs = {node: float('inf') for node in graph.keys()}\n",
    "    costs[start] = 0\n",
    "    # and use parent_nodes to keep track of the chain of\n",
    "    # nodes that make up the shortest path\n",
    "    parent_nodes = {}\n",
    "    for neighbor in graph[start].keys():\n",
    "        costs[neighbor] = graph[start][neighbor]\n",
    "        parent_nodes[neighbor] = start\n",
    "    \n",
    "    nodes_checked = set()\n",
    "    while not len(nodes_checked) == len(graph.keys()):\n",
    "        \n",
    "        # get lowest cost node\n",
    "        min_cost, min_cost_node = float('inf'), None\n",
    "        for node in costs:\n",
    "            curr_cost = costs[node]\n",
    "            if curr_cost < min_cost and node not in nodes_checked:\n",
    "                min_cost, min_cost_node = curr_cost, node\n",
    "                \n",
    "        # check if we can reach any of the lowest cost node's\n",
    "        # neigbors by going through the lowest cose node\n",
    "        for neighbor in graph[min_cost_node].keys():\n",
    "            new_cost = min_cost + graph[min_cost_node][neighbor]\n",
    "            if new_cost < costs[neighbor]:\n",
    "                costs[neighbor] = new_cost\n",
    "                parent_nodes[neighbor] = min_cost_node\n",
    "                \n",
    "        # early stopping if we visited the destination\n",
    "            if neighbor == destination:\n",
    "                break\n",
    "        if neighbor == destination:\n",
    "                break\n",
    "    \n",
    "        # add the node to the checked nodes\n",
    "        nodes_checked.add(min_cost_node)\n",
    "            \n",
    "    return costs, parent_nodes\n",
    "\n",
    "\n",
    "costs, parent_nodes = dijkstra(graph, start='A', destination='F')\n",
    "\n",
    "print('Costs:', costs)\n",
    "print('Parent Nodes:', parent_nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, after running the algorithm, the `costs` dictionary provides us with the minimum cost to reach particular nodes in the graph starting at node A. For instance, the shortest path between A and F is 20.\n",
    "\n",
    "The `parent_nodes` dictionary maps each node along the path to its parent. For instance, to see the shortest path from A to F, we can simply backtrack starting from F:\n",
    "\n",
    "`'F': 'B' -> 'B': 'C' -> 'C': 'A'`\n",
    "\n",
    "Thus, the shortest path (with cost 20) is \n",
    "\n",
    "`A -> C -> B -> F`. "
   ]
  }
 ],
 "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
}