dijkstra shortest path.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dijkstra's Algorithm\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "Dijkstra's Algorithm is a famous algorithm named after its inventor, a Turin Award laureate. The structure is somewhat similar to Breadth First Search. A profound understanding of BFS is definitely beneficial to the study of Dijkstra's Algorithm. In the previous chapter, we have tested BFS and DFS in unweighted DCG. This time, we use weighted DCG. Each weight denotes the distance from one vertex to another. Dijkstra's Algorithm will help us find the shortest path from point A to point B with the minimum weights.\n",
    "\n",
    "Details of BFS are in the following link\n",
    "\n",
    "https://github.com/je-suis-tm/graph-theory/blob/master/BFS%20DFS%20on%20DCG.ipynb\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "os.chdir('K:/ecole/github')\n",
    "\n",
    "#graph adt\n",
    "#check the below link for more details\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/graph.py\n",
    "import graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create graph adt\n",
    "ADT=graph.graph()\n",
    "\n",
    "ADT.append(1,2,1)\n",
    "ADT.append(1,3,2)\n",
    "ADT.append(2,4,2)\n",
    "ADT.append(2,5,2)\n",
    "ADT.append(3,5,1)\n",
    "ADT.append(4,2,2)\n",
    "ADT.append(4,6,3)\n",
    "ADT.append(5,2,2)\n",
    "ADT.append(5,6,1)\n",
    "ADT.append(6,3,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/WDCG.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#dijkstra requires a lot of space to execute\n",
    "#well, its better than the time complexity\n",
    "def dijkstra(ADT,start,end):\n",
    "    \"\"\"Dijkstra's Algorithm\"\"\"\n",
    "    \n",
    "    #all weights in dcg must be positive \n",
    "    #otherwise we have to use bellman ford instead\n",
    "    # https://github.com/je-suis-tm/graph-theory/blob/master/bellman_ford%20forex%20arbitrage.ipynb\n",
    "    neg_check=[j for i in ADT.reveal() for j in ADT.reveal()[i].values()]\n",
    "    assert min(neg_check)>=0,\"negative weights are not allowed, please use Bellman-Ford\"\n",
    "    \n",
    "    #queue in dijkstra is similar to the queue in bfs\n",
    "    #except when we pop items from queue\n",
    "    #we pop the item with the minimum weight\n",
    "    #thats why queue is a dict here rather than a list\n",
    "    #ideally we should use priority queue\n",
    "    queue={}\n",
    "    queue[start]=0\n",
    "    \n",
    "    #distance is also a dictionary\n",
    "    #it keeps track of distance from starting vertex to any vertex\n",
    "    #before we start any iteration\n",
    "    #we initialize all distances from start to any vertices to infinity\n",
    "    #we set the distance[start] to zero\n",
    "    distance={}\n",
    "    for i in ADT.vertex():\n",
    "        distance[i]=float('inf')\n",
    "    distance[start]=0\n",
    "        \n",
    "    #pred is a dict as well\n",
    "    #it keeps track of how we get to the current vertex\n",
    "    #each time we update distance, we update the predecessor vertex\n",
    "    #in the end, we can obtain the detailed path from start to end\n",
    "    pred={}\n",
    "        \n",
    "    #for each iteration, we select a vertex with the minimum weight\n",
    "    #we attempt to find the shortest path from the start to the current vertex\n",
    "    #eventually we get the optimal result which is the shortest path\n",
    "    #the logic is simple, similar to dynamic programming\n",
    "    #if the path from start to end is optimal\n",
    "    #the path from start to any vertex along the path \n",
    "    #should be the optimal as well\n",
    "    #details about dynamic programming are in the following link\n",
    "    # https://github.com/je-suis-tm/recursion-and-dynamic-programming/blob/master/knapsack.jl\n",
    "    while queue:\n",
    "        \n",
    "        #vertex with the minimum weight in queue\n",
    "        current=min(queue,key=queue.get)\n",
    "        queue.pop(current)\n",
    "        \n",
    "        for j in ADT.edge(current):\n",
    "            \n",
    "            #check if the current vertex can construct the optimal path\n",
    "            if distance[current]+ADT.weight(current,j)<distance[j]:\n",
    "                distance[j]=distance[current]+ADT.weight(current,j)\n",
    "                pred[j]=current\n",
    "            \n",
    "            #add child vertex to the queue\n",
    "            if ADT.go(j)==0 and j not in queue:\n",
    "                queue[j]=distance[j]\n",
    "        \n",
    "        #each vertex is visited only once\n",
    "        ADT.visit(current)\n",
    "        \n",
    "        #traversal ends when the target is met\n",
    "        if current==end:\n",
    "            break\n",
    "    \n",
    "    #create the shortest path by backtracking\n",
    "    #trace the predecessor vertex from end to start\n",
    "    previous=end\n",
    "    path=[]\n",
    "    while pred:\n",
    "        path.insert(0, previous)\n",
    "        if previous==start:\n",
    "            break\n",
    "        previous=pred[previous]\n",
    "    \n",
    "    #note that if we cant go from start to end\n",
    "    #we may get inf for distance[end]\n",
    "    #additionally, the path may not include start position\n",
    "    return distance[end],path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "minimum steps:4, path:[1, 2, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "print('minimum steps:%d, path:%s'%dijkstra(ADT,1,6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/dijkstra.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}