dijkstra

dijkstra.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "({'v': 9, 'x': 5, 'u': 8, 'y': 7, 's': 0}, {'x': 's', 'v': 'u', 'y': 'x', 'u': 'x'})\n",
      "['s', 'x', 'u', 'v']\n"
     ]
    }
   ],
   "source": [
    "from heapq import heappush, heappop\n",
    "\n",
    "def updateheap(heap,d,v):\n",
    "    for i in range(len(heap)):\n",
    "        if heap[i][1] == v:\n",
    "           heap[i][0] = d\n",
    "           fix_minheap(heap,i) # heap=heapify(heap) ineficient      \n",
    "           break    \n",
    "\n",
    "def fix_minheap(heap, i):\n",
    "    if i == 0: return  \n",
    "    p = int(i/2) #parent  \n",
    "    if p >= 0 and heap[p][0] > heap[i][0]:\n",
    "        heap[i], heap[p] = heap[p], heap[i]\n",
    "        fix_minheap(heap,p)   \n",
    "            \n",
    "def Dijkstra(G,start):\n",
    "    \n",
    "    D = {} # dictionary of final distances\n",
    "    for v in G:\n",
    "        D[v] = float('inf')\n",
    "    D[start] = 0\n",
    "    \n",
    "    P = {} # dictionary of predecessors\n",
    "    \n",
    "    Q=[] #  priority queue est.dist. of non-final vert.\n",
    "    for v in G:\n",
    "       item = []\n",
    "       item.append(D[v])\n",
    "       item.append(v)\n",
    "       heappush(Q,item)\n",
    "    \n",
    "    \n",
    "    #S = []\n",
    "    while Q:\n",
    "        u = heappop(Q)[1]\n",
    "        #S.append(u)\n",
    "        for v in G[u]:\n",
    "            newDuv = D[u] + G[u][v]\n",
    "            if newDuv < D[v]:\n",
    "                P[v] = u\n",
    "                D[v] = newDuv\n",
    "                updateheap(Q,D[v],v)\n",
    "    return D,P\n",
    "\n",
    "# From  http://www.ics.uci.edu/~eppstein/161/python/dijkstra.py\n",
    "# David Eppstein, UC Irvine, 4 April 2002\n",
    "def shortestPath(G,start,end):\n",
    "    \"\"\"\n",
    "    Find a single shortest path from the given start vertex to the given end vertex.\n",
    "    The input has the same conventions as Dijkstra().\n",
    "    The output is a list of the vertices in order along the shortest path.\n",
    "     \"\"\"\n",
    "\n",
    "    D,P = Dijkstra(G,start)\n",
    "    Path = []\n",
    "    while 1:\n",
    "        Path.append(end)\n",
    "        if end == start: break\n",
    "        end = P[end]\n",
    "    Path.reverse()\n",
    "    return Path\n",
    "\n",
    "# example, CLR p.528\n",
    "G = {'s': {'u':10, 'x':5},\n",
    "    'u': {'v':1, 'x':2},\n",
    "    'v': {'y':4},\n",
    "    'x':{'u':3,'v':9,'y':2},\n",
    "    'y':{'s':7,'v':6}}\n",
    "\n",
    "print(Dijkstra(G,'s'))\n",
    "print(shortestPath(G,'s','v'))"
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}