Bellman-Ford Algorithm Implements using Python

bellman-ford-python.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "class BellmanFord:\n",
    "    def __init__(self, nodes, edges, start):\n",
    "        start.min_cost = 0\n",
    "        \n",
    "        self.nodes = nodes\n",
    "        self.edges = edges\n",
    "        self.start = start\n",
    "        self.has_cycle = False\n",
    "        \n",
    "        self.count_cost()\n",
    "        \n",
    "    def count_cost(self):\n",
    "        for i in range(len(self.nodes) - 1):\n",
    "            for edge in self.edges:\n",
    "                cost = edge.start.min_cost + edge.weight\n",
    "                if edge.target.min_cost > cost:\n",
    "                    edge.target.min_cost = cost\n",
    "                    edge.target.predecessor = edge.start\n",
    "                    \n",
    "        for edge in self.edges:\n",
    "            if self.check_cycle(edge):\n",
    "                self.has_cycle = True\n",
    "             \n",
    "    @staticmethod\n",
    "    def check_cycle(edge):\n",
    "        return (edge.start.min_cost + edge.weight) < edge.target.min_cost\n",
    "    \n",
    "    def get_shortest_path(self, target):\n",
    "        if self.has_cycle:\n",
    "            raise NotImplementedError('Negtive Cycle Detected!')\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": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = ()\n",
    "edges = ()\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",
    "edges = (\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",
    ")"
   ]
  },
  {
   "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 = BellmanFord(graph, edges, A)\n",
    "algorithm.get_shortest_path(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# cycle test\n",
    "\n",
    "edges += (\n",
    "    Edge(1, A, B),\n",
    "    Edge(1, B, C),\n",
    "    Edge(-3, C, A),\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "ename": "NotImplementedError",
     "evalue": "Negtive Cycle Detected!",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNotImplementedError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-6-3e599c50b50b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0malgorithm\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mBellmanFord\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgraph\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0medges\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mA\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0malgorithm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_shortest_path\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mG\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-2-48100972bb97>\u001b[0m in \u001b[0;36mget_shortest_path\u001b[0;34m(self, target)\u001b[0m\n\u001b[1;32m     30\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mget_shortest_path\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtarget\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     31\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mhas_cycle\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 32\u001b[0;31m             \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Negtive Cycle Detected!'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     33\u001b[0m         \u001b[0mnode\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtarget\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     34\u001b[0m         \u001b[0mpath\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNotImplementedError\u001b[0m: Negtive Cycle Detected!"
     ]
    }
   ],
   "source": [
    "algorithm = BellmanFord(graph, edges, A)\n",
    "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
}