Dijkstra's Algorithm in Python

Dijkstras Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \"\"\"This class represents a node in a graph.\"\"\"\n",
    "    \n",
    "    def __init__(self, label: str=None):\n",
    "        \"\"\"\n",
    "        Initialize a new node.\n",
    "        \n",
    "        Args:\n",
    "            label: the string identifier for the node\n",
    "        \"\"\"\n",
    "        self.label = label\n",
    "        self.children = []\n",
    "        \n",
    "    def __lt__(self,other):\n",
    "        \"\"\"\n",
    "        Perform the less than operation (self < other).\n",
    "        \n",
    "        Args:\n",
    "            other: the other Node to compare to\n",
    "        \"\"\"\n",
    "        return (self.label < other.label)\n",
    "    \n",
    "    def __gt__(self,other):\n",
    "        \"\"\"\n",
    "        Perform the greater than operation (self > other).\n",
    "        \n",
    "        Args:\n",
    "            other: the other Node to compare to\n",
    "        \"\"\"\n",
    "        return (self.label > other.label)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        \"\"\"Return a string form of this node.\"\"\"\n",
    "        return '{} -> {}'.format(self.label, self.children)\n",
    "    \n",
    "    def add_child(self, node, cost=1):\n",
    "        \"\"\"\n",
    "        Add a child node to this node.\n",
    "        \n",
    "        Args:\n",
    "            node: the node to add to the children\n",
    "            cost: the cost of the edge (default 1)\n",
    "        \"\"\"\n",
    "        edge = Edge(self, node, cost)\n",
    "        self.children.append(edge)            \n",
    "        \n",
    "    \n",
    "class Edge(object):\n",
    "    \"\"\"This class represents an edge in a graph.\"\"\"\n",
    "    \n",
    "    def __init__(self, source: Node, destination: Node, cost: int=1):\n",
    "        \"\"\"\n",
    "        Initialize a new edge.\n",
    "        \n",
    "        Args:\n",
    "            source: the source of the edge\n",
    "            destination: the destination of the edge\n",
    "            cost: the cost of the edge (default 1)\n",
    "        \"\"\"\n",
    "        self.source = source\n",
    "        self.destination = destination\n",
    "        self.cost = cost\n",
    "    \n",
    "    def __repr__(self):\n",
    "        \"\"\"Return a string form of this edge.\"\"\"\n",
    "        return '{}: {}'.format(self.cost, self.destination.label)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph\n",
    "\n",
    "![Graph](graph.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating The Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S = Node('S')\n",
    "A = Node('A')\n",
    "B = Node('B')\n",
    "C = Node('C')\n",
    "D = Node('D')\n",
    "G = Node('G')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S.add_child(A, 1)\n",
    "S.add_child(G, 12)\n",
    "\n",
    "A.add_child(B, 3)\n",
    "A.add_child(C, 1)\n",
    "\n",
    "B.add_child(D, 3)\n",
    "\n",
    "C.add_child(D, 1)\n",
    "C.add_child(G, 2)\n",
    "\n",
    "D.add_child(G, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S -> [1: A, 12: G]\n",
      "A -> [3: B, 1: C]\n",
      "B -> [3: D]\n",
      "C -> [1: D, 2: G]\n",
      "D -> [3: G]\n",
      "G -> []\n"
     ]
    }
   ],
   "source": [
    "_ = [print(node) for node in [S, A, B, C, D, G]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithm\n",
    "\n",
    "```\n",
    "  function Dijkstra(Graph, source):\n",
    "      dist[source] ← 0                                    // Initialization\n",
    "\n",
    "      create vertex set Q\n",
    "\n",
    "      for each vertex v in Graph:           \n",
    "          if v ≠ source\n",
    "              dist[v] ← INFINITY                          // Unknown distance from source to v\n",
    "              prev[v] ← UNDEFINED                         // Predecessor of v\n",
    "\n",
    "         Q.add_with_priority(v, dist[v])\n",
    "\n",
    "\n",
    "     while Q is not empty:                              // The main loop\n",
    "         u ← Q.extract_min()                            // Remove and return best vertex\n",
    "         for each neighbor v of u:                      // only v that is still in Q\n",
    "             alt ← dist[u] + length(u, v) \n",
    "             if alt < dist[v]\n",
    "                 dist[v] ← alt\n",
    "                 prev[v] ← u\n",
    "                 Q.decrease_priority(v, alt)\n",
    "\n",
    "     return dist[], prev[]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from queue import PriorityQueue\n",
    "import numpy as np\n",
    "        \n",
    "def dijkstra(root: Node) -> tuple:\n",
    "    \"\"\"\n",
    "    Return the dijktra search result of the root node. i.e. the \n",
    "    collection of shortest paths from all the nodes in the graph\n",
    "    to the root node.\n",
    "    \n",
    "    Args:\n",
    "        root: the root node to explore\n",
    "        \n",
    "    Returns: a tuple of dictionaries keyed by node.\n",
    "             the first contains distances from root to the key node\n",
    "             the second contains the backtrace of shortest paths\n",
    "    \"\"\"\n",
    "    # create the distance mapping with 0 for intial state\n",
    "    distance = dict()\n",
    "    distance[root] = 0\n",
    "    previous = dict()\n",
    "    # make a priority queue with the initial state\n",
    "    queue = PriorityQueue()\n",
    "    queue.put((0, root))\n",
    "    # while the queue isn't empty\n",
    "    while not queue.empty():\n",
    "        # get the highest priority item\n",
    "        current = queue.get()[1]\n",
    "        # iterate over the edges\n",
    "        for edge in current.children:\n",
    "            # calculate the cost to this child\n",
    "            alt = distance[current] + edge.cost\n",
    "            # if it's a new edge, or a better distance\n",
    "            if edge.destination not in distance or alt < distance[edge.destination]:\n",
    "                # update the path mapping \n",
    "                distance[edge.destination] = alt\n",
    "                previous[edge.destination] = current\n",
    "                # enqueue the child with it's edge cost\n",
    "                queue.put((alt, edge.destination))\n",
    "    # return the mapping of nodes to distances and previous nodes\n",
    "    return distance, previous"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "distance, previous = dijkstra(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{A -> [3: B, 1: C]: 1,\n",
       " B -> [3: D]: 4,\n",
       " C -> [1: D, 2: G]: 2,\n",
       " D -> [3: G]: 3,\n",
       " G -> []: 4,\n",
       " S -> [1: A, 12: G]: 0}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{A -> [3: B, 1: C]: S -> [1: A, 12: G],\n",
       " B -> [3: D]: A -> [3: B, 1: C],\n",
       " C -> [1: D, 2: G]: A -> [3: B, 1: C],\n",
       " D -> [3: G]: C -> [1: D, 2: G],\n",
       " G -> []: C -> [1: D, 2: G]}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "previous"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reference\n",
    "\n",
    "https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode"
   ]
  }
 ],
 "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
}

graph.png