Dijkstra algorithm implements using Python

dijkstra-python.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "import heapq\n",
    "\n",
    "class Edge:\n",
    "    def __init__(self, weight, start, target):\n",
    "        self.weight = weight\n",
    "        self.start = start\n",
    "        self.target = target\n",
    "        \n",
    "        if self not in start.edges:\n",
    "            start.edges.append(self)\n",
    "            \n",
    "    def __repr__(self):\n",
    "        return 'Edge(weight={0}, start={1}, target={2})'.format(\n",
    "            self.weight,\n",
    "            self.start,\n",
    "            self.target\n",
    "        )\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, name):\n",
    "        self.name = name\n",
    "        self.visted = False\n",
    "        self.predecessor = None\n",
    "        self.edges = []  # Edges\n",
    "        self.min_cost = sys.maxsize\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return 'Node(name={})'.format(self.name)\n",
    "        \n",
    "    def __cmp__(self, other):\n",
    "        return self.cmp(self.min_cost, other.min_cost)\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        return self.min_cost < other.min_cost\n",
    "    \n",
    "class Dijkstra:\n",
    "    def __init__(self, start):\n",
    "        self.heap = []\n",
    "        start.min_cost = 0\n",
    "        heapq.heappush(self.heap, start)\n",
    "        \n",
    "        self.count_cost()\n",
    "        \n",
    "    def count_cost(self):           \n",
    "        while self.heap:\n",
    "            node = heapq.heappop(self.heap)\n",
    "            \n",
    "            for edge in node.edges:\n",
    "                cost = edge.start.min_cost + edge.weight\n",
    "                \n",
    "                if cost < edge.target.min_cost:\n",
    "                    edge.target.predecessor = edge.start\n",
    "                    edge.target.min_cost = cost\n",
    "                    \n",
    "                    heapq.heappush(self.heap, edge.target)\n",
    "                    \n",
    "    def get_shortest_path(self, target):\n",
    "        node = target\n",
    "        path = []\n",
    "        while node is not None:\n",
    "            path.append(node)\n",
    "            node = node.predecessor\n",
    "            \n",
    "        return list(reversed(path))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![image](https://storage.googleapis.com/ssivart/super9-blog/dijkstra.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[Edge(weight=5, start=Node(name=A), target=Node(name=B)), Edge(weight=8, start=Node(name=A), target=Node(name=H)), Edge(weight=9, start=Node(name=A), target=Node(name=E))]\n"
     ]
    }
   ],
   "source": [
    "graph = ()\n",
    "\n",
    "# construct A,B,C,D,E,F,G,H Nodes\n",
    "node_str = 'ABCDEFGH'\n",
    "for s in node_str:\n",
    "    node = Node(s)\n",
    "    locals()[s] = node\n",
    "    graph += (node, )\n",
    "    \n",
    "# lined nodes\n",
    "Edge(5, A, B)\n",
    "Edge(8, A, H)\n",
    "Edge(9, A, E)\n",
    "Edge(12, B, C)\n",
    "Edge(15, B, D)\n",
    "Edge(4, B, H)\n",
    "Edge(3, C, D)\n",
    "Edge(11, C, G)\n",
    "Edge(9, D, G)\n",
    "Edge(5, E, H)\n",
    "Edge(4, E, F)\n",
    "Edge(20, E, G)\n",
    "Edge(1, F, C)\n",
    "Edge(13, F, G)\n",
    "Edge(7, H, C)\n",
    "Edge(6, H, F)\n",
    "\n",
    "print(A.edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "algorithm = Dijkstra(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Node(name=A), Node(name=E), Node(name=F), Node(name=C), Node(name=G)]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "algorithm.get_shortest_path(G)"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}