discrete math.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Algorithms implemented in Python from the book \"Discrete Mathematics\" by Dossey, Otto, Spence and Eynden\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "from sympy import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chapter 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Algorithm for evaluating $x^n$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "81"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def eval(x, n):\n",
    "    P=x\n",
    "    k=1\n",
    "    while k<n:\n",
    "        P*=x\n",
    "        k+=1\n",
    "    return P\n",
    "\n",
    "eval(3, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Polynomial Evaluation Algorithm: computes $P(x)=a_nx^n + a_{n-1}x^{n-1} +...+ a_0$, given the non-negative integer $n$ and real numbers $x$, $a_0$, $a_1$, ..., $a_n$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def P(x, a):\n",
    "    # a is the list of the constants: a0, a1, ..., an\n",
    "    S=a[0]\n",
    "    k=1\n",
    "    n=len(a)-1\n",
    "    while k<=n:\n",
    "        S+=a[k]*x**k\n",
    "        k+=1\n",
    "    return S\n",
    "P(2, [4, 3, -2, 5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Horner's Polynomial Evaluation Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def HP(x, a):\n",
    "    n=len(a)-1\n",
    "    S=a[n]\n",
    "    k=1\n",
    "    while k<=n:\n",
    "        S=x*S+a[n-k]\n",
    "        k+=1\n",
    "    return S\n",
    "HP(2, [4, 3, -2, 5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Next Subset Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'111'"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def NS(a):\n",
    "    \"\"\"a is a string of 0s and 1s corresponding to a subset of n elements\"\"\"\n",
    "    n=len(a)\n",
    "    a=list(a)\n",
    "    k=n-1\n",
    "    while k>=0 and a[k]=='1':\n",
    "        k-=1\n",
    "    if k>=0:\n",
    "        a[k]='1'\n",
    "        for j in range(k+1, n):\n",
    "            a[j]='0'\n",
    "        return ''.join(a)\n",
    "    else: return 'The string contains all 1s'\n",
    "NS('110')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Bubble Sort Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.43, 0.5, 1.2, 3.2, 3.2, 8.44, 9.0]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def BS(a):\n",
    "    \"\"\"A is a list of unsorted real numbers\"\"\"\n",
    "    n=len(a)-1\n",
    "    for j in range(n):\n",
    "        for k in range(n-1, j-1, -1):\n",
    "            if a[k+1]<a[k]:\n",
    "                t=a[k+1]\n",
    "                a[k+1]=a[k]\n",
    "                a[k]=t\n",
    "    return a\n",
    "\n",
    "BS([1.2, 3.2, 9.0, 3.2, 0.5, 0.43, 8.44])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Revised Polynomial Evaluation Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def RP(x, a):\n",
    "    S=a[0]\n",
    "    y=1\n",
    "    k=1\n",
    "    n=len(a)-1\n",
    "    while k<=n:\n",
    "        y=x*y\n",
    "        S+=y*a[k]\n",
    "        k+=1\n",
    "    return S\n",
    "RP(2, [4, 3, -2, 5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ### Chapter 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The Euclidean Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def gcd(m, n):\n",
    "    \"\"\"m and n are both non-negative integers\"\"\"\n",
    "    while n!=0:\n",
    "        m, n = n, m%n\n",
    "    return m\n",
    "\n",
    "gcd(427, 154)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The Extended Euclidean Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, -499, 45)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def exgcd(m, n):\n",
    "    r=[m, n]\n",
    "    x=[1, 0]\n",
    "    y=[0, 1]\n",
    "    i=1\n",
    "    while r[i]!=0:\n",
    "        i+=1\n",
    "        q=r[i-2]//r[i-1]\n",
    "        x+=[x[i-2]-q*x[i-1],]\n",
    "        y+=[y[i-2]-q*y[i-1],]\n",
    "        r+=[r[i-2]%r[i-1],]\n",
    "    return (r[i-1], x[i-1], y[i-1])\n",
    "exgcd(101, 1120)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The Modular Exponentiation Algorithm: Given positive integers P, E and n, this algorithm computes the remainder when $P^E$ is divided by $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "90"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def ME(P, E, n):\n",
    "    r2=1\n",
    "    p=P\n",
    "    e=E\n",
    "    while e!=0:\n",
    "        Q=e//2\n",
    "        R=e%2\n",
    "        r1=p**2%n\n",
    "        if R==1: r2=(r2*p)%n\n",
    "        p=r1\n",
    "        e=Q\n",
    "    return r2\n",
    "\n",
    "ME(582, 621,1189)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Check Matrix Row Decoding Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1 1 0]\n",
      " [0 1 1]\n",
      " [1 0 0]\n",
      " [0 1 0]\n",
      " [0 0 1]]\n",
      "[0 0 0]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([1, 0])"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def CMRD(codeword, generatorMatrix):\n",
    "    A=generatorMatrix\n",
    "    w=codeword\n",
    "    k=len(A)\n",
    "    n=len(A[0])\n",
    "    J=np.copy(A[:, k:])\n",
    "    A_star=np.append(J, np.eye(len(J[0]), dtype=int), axis=0)\n",
    "    print(A_star)\n",
    "    s=(w.dot(A_star))%2\n",
    "    print(s)\n",
    "    if sum(s)==0: return w[:k]\n",
    "    if list(s) in A_star.tolist():\n",
    "        i=np.where(np.all(A_star==s,axis=1))\n",
    "        w[i]=(w[i]+1)%2\n",
    "        return w[:k]\n",
    "    if list(s) not in A_star.tolist(): return \"unknown\"\n",
    "    \n",
    "A=np.array(([1, 0, 0, 1, 0, 1, 0], [0, 1, 0, 1, 1, 0, 1], [0, 0, 1, 0, 1, 1, 1]))\n",
    "w1=np.array([0, 0, 1, 0, 1, 1, 1])\n",
    "w2=np.array([1, 0, 1, 1, 1, 0, 0])\n",
    "w3=np.array([0, 1, 1, 1, 0, 1, 0])\n",
    "w4=np.array([1, 0, 0, 0, 1, 1, 1])\n",
    "w5=np.array([1, 1, 0, 0, 0, 1, 0])\n",
    "#CMRD(w5, A)\n",
    "\n",
    "#ex 3.6, 29\n",
    "B=np.array(([1, 0, 1, 1, 0], [0, 1, 0, 1, 1])) # Generator matrix\n",
    "c=np.array([1, 0, 1, 1, 0]) # received word\n",
    "CMRD(c, B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chapter 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Euler circuit Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': ['U', 'V'], 'b': ['U', 'V'], 'c': ['U', 'A'], 'd': ['A', 'V'], 'e': ['U', 'V']}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'a': ['V', 'U'],\n",
       " 'b': ['U', 'V'],\n",
       " 'e': ['V', 'U'],\n",
       " 'c': ['U', 'A'],\n",
       " 'd': ['A', 'V']}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J']\n",
    "Ed={'a':['A', 'B'], 'c':['B', 'E'], 'f':['E', 'D'], 'b':['D', 'A'], 'd':['E', 'C'], 'e':['C', 'F'], 'g':['F', 'E'], 'h':['E', 'G'], 'k':['H', 'G'], 'm':['H', 'J'], 'l':['J', 'H'], 'j':['H', 'E']}\n",
    "\n",
    "def EulerCircuit(V, Ed): \n",
    "    E1=list(Ed.keys())\n",
    "    E2=[Ed[i] for i in Ed]\n",
    "    U=random.choice(V)  \n",
    "    R=[i for i in E2 if U in i]    \n",
    "    #print(R)\n",
    "\n",
    "    st=random.choice(R)\n",
    "    ind=E2.index(st)\n",
    "    C={}\n",
    "    #print(C)\n",
    "\n",
    "    if st[0]!=U: st=st[::-1]\n",
    "    C[E1[ind]]=st\n",
    "    del E1[ind]\n",
    "    del E2[ind]\n",
    "    #print(E1)\n",
    "    #print(E2)\n",
    "\n",
    "    while st[1]!=U:\n",
    "        u=st[1]\n",
    "        R=[i for i in E2 if u in i]\n",
    "        st=random.choice(R)\n",
    "        ind=E2.index(st)\n",
    "        if st[0]!=u: st=st[::-1]\n",
    "        C[E1[ind]]=st\n",
    "        del E1[ind]\n",
    "        del E2[ind]\n",
    "\n",
    "    while len(E1)!=0 and len(E2)!=0:\n",
    "        E21=sympy.flatten(E2)\n",
    "        E3=list(C.keys())\n",
    "        E4=[C[i] for i in C]\n",
    "        E41=sympy.flatten(E4)\n",
    "        L=[] # store the vertices whose edges are not listed in C\n",
    "        L=list(set([i for i in E41 if E21.count(i)>0]))\n",
    "        #print(L)\n",
    "        u= random.choice(L)\n",
    "    \n",
    "        R=[i for i in E2 if u in i]    \n",
    "        st=random.choice(R)\n",
    "        ind=E2.index(st)\n",
    "        P={}\n",
    "    \n",
    "        if st[0]!=u: st=st[::-1]\n",
    "        P[E1[ind]]=st\n",
    "        del E1[ind]\n",
    "        del E2[ind]\n",
    "    \n",
    "        while st[1]!=u:\n",
    "            u1=st[1]\n",
    "            R=[i for i in E2 if u1 in i]\n",
    "            st=random.choice(R)\n",
    "            ind=E2.index(st)\n",
    "            if st[0]!=u1: st=st[::-1]\n",
    "            P[E1[ind]]=st\n",
    "            del E1[ind]\n",
    "            del E2[ind]\n",
    "    \n",
    "        x=list(P.keys())\n",
    "        y=[P[i] for i in P]\n",
    "        z=[i for i in E4 if i[1]==u]\n",
    "        #print(E3)\n",
    "        #print(E4)\n",
    "        #print(x, y, z)\n",
    "        ra=random.choice(z)\n",
    "        k1=E4.index(ra)\n",
    "        E3[k1+1:k1+1]=x\n",
    "        E4[k1+1:k1+1]=y\n",
    "        C={}\n",
    "        for i in range(len(E3)): C[E3[i]]=E4[i]\n",
    "        #print(P)\n",
    "    \n",
    "    return C\n",
    "\n",
    "#EulerCircuit(V, Ed)\n",
    "\n",
    "Ed={'a':['U', 'V'], 'b':['U', 'V'], 'c':['U', 'A'], 'd':['A', 'V'], 'e':['U', 'V']}\n",
    "V=['A', 'U', 'V']\n",
    "print(Ed)\n",
    "EulerCircuit(V, Ed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Breadth-First Search Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'S': [0, '-'], 'A': [1, 'S'], 'D': [1, 'S'], 'B': [2, 'D'], 'G': [2, 'D'], 'E': [3, 'G'], 'H': [3, 'G'], 'C': [4, 'E'], 'F': [4, 'H'], 'I': [4, 'H'], 'T': [5, 'F']}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'SDGHFT'"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Ed=[['S', 'A'], ['S', 'B'], ['A', 'E'], ['E', 'C'], ['A', 'C'], ['C', 'B'], ['F', 'E'], ['F', 'H'], ['C', 'H'], ['H', 'I'], ['I', 'J'], ['J', 'G'], ['G', 'D'], ['D', 'B']]\n",
    "#V=['S', 'A', 'B', 'E', 'F', 'H', 'I', 'J', 'G', 'D', 'B', 'C']\n",
    "#start='S'\n",
    "#end='I'\n",
    "\n",
    "Ed=[['S', 'A'], ['S', 'D'], ['D', 'B'], ['G', 'D'], ['B', 'G'], ['E', 'C'], ['E', 'F'], ['C', 'F'], ['E', 'G'], ['G', 'H'], ['F', 'H'], ['F', 'T'], ['H', 'I'], ['T', 'I']]\n",
    "V=['S', 'A', 'D', 'B', 'G', 'E', 'C', 'F', 'G', 'H', 'I', 'T']\n",
    "start='S'\n",
    "end='T'\n",
    "\n",
    "def BFSA(Ed, V, start, end):\n",
    "    st=[start]\n",
    "    L={st[0]:[0, '-']}\n",
    "\n",
    "    k=0\n",
    "\n",
    "    while len(V)>1:\n",
    "        k+=1\n",
    "        st1=[]\n",
    "        for s in st:\n",
    "            del V[V.index(s)]\n",
    "            I=[j for j in Ed if (j[0]==s or j[1]==s)]\n",
    "            for i in I:\n",
    "                del Ed[Ed.index(i)]\n",
    "            I1=[i[::-1] if i[1]==s else i for i in I]\n",
    "            I2=[i for i in I1 if (i[0] in st and i[1] not in st) or (i[0] not in st and i[1] in st) ]\n",
    "            for [i, j] in I2:\n",
    "                L[j]=[k, s]\n",
    "                st1+=[j, ]\n",
    "        st=list(set(st1))\n",
    "   \n",
    "    print(L)\n",
    "    \n",
    "    path=end\n",
    "    pr=L[end][1]\n",
    "    while pr!='-':\n",
    "        path+=pr\n",
    "        pr=L[pr][1]\n",
    "        \n",
    "    return path[::-1]\n",
    "\n",
    "BFSA(Ed, V, start, end)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Dijkstra's Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'S': [0, '-'], 'H': [1, 'S'], 'E': [2, 'S'], 'F': [3, 'H'], 'C': [3, 'S'], 'D': [5, 'F'], 'G': [6, 'D'], 'B': [6, 'H'], 'A': [8, 'G']}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'SHFDGA'"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Ed=[['S', 'A', 3], ['S', 'B', 1], ['C', 'A', 2], ['C', 'B', 3], ['D', 'B', 5], ['A', 'B', 1], ['C', 'E', 3], ['D', 'C', 1], ['D','E', 1]]\n",
    "#V=['A', 'S', 'B', 'D', 'C', 'E']\n",
    "#st='S'\n",
    "#end='E'\n",
    "\n",
    "##Ex 4.3, 6\n",
    "#Ed=[['S', 'C', 2], ['S', 'E', 4], ['E', 'C', 1], ['C', 'F', 3], ['C', 'D', 5], ['F', 'E', 1], ['F', 'G', 2], ['D', 'F', 3], ['D', 'G', 1], ['D', 'H',1], ['G', 'H', 3], ['A', 'H', 3], ['E', 'J', 2], ['G', 'J', 3]]\n",
    "#V=['S', 'C', 'D', 'E', 'F', 'G', 'H', 'A', 'J']\n",
    "#st='S'\n",
    "#end='A'\n",
    "\n",
    "##Ex 4.3, 7\n",
    "Ed=[['S', 'C', 3], ['S', 'E', 2], ['S', 'H', 1], ['C', 'E', 1], ['E', 'H', 1], ['F', 'C', 3], ['F', 'H', 2], ['F', 'D', 2], ['C', 'D', 2], ['F', 'B', 3], ['B', 'H', 5], ['G', 'D', 1], ['G', 'B', 1], ['G', 'A', 2], ['A', 'D', 5], ['A', 'B', 4]]\n",
    "V=['S', 'C', 'E', 'H', 'D', 'F', 'G', 'B', 'A']\n",
    "st='S'\n",
    "end='A'\n",
    "\n",
    "def DA(Ed, V, st, end):\n",
    "    \"\"\"Each of the entries in Ed has form: ['vertex1', 'vertex2', weight of the edge joining vertex1 and vertex2]\"\"\"\n",
    "    E1=[]\n",
    "    E2=[]\n",
    "    for i in Ed:\n",
    "        E1+=[[i[0], i[1]], ]\n",
    "        E2+=[i[2], ]\n",
    "    P={st:[0, '-']}\n",
    "    V1=V[:]\n",
    "    del V1[V1.index(st)]\n",
    "    temp={}\n",
    "    I=[]\n",
    "    for i in V1:\n",
    "        if [i, st] in E1:\n",
    "            ind=E1.index([i, st])\n",
    "            temp[i]=[E2[ind], st]\n",
    "            I+=[ind,]\n",
    "        \n",
    "        elif [st, i] in E1:\n",
    "            ind=E1.index([st, i])\n",
    "            temp[i]=[E2[ind], st]\n",
    "            I+=[ind,]\n",
    "        \n",
    "        elif (not [i, st] in E1) or (not [st, i] in E1):\n",
    "            temp[i]=[oo, st]\n",
    "\n",
    "    for ind in sorted(I, reverse=True):\n",
    "        del E1[ind]\n",
    "        del E2[ind]\n",
    "\n",
    "    t1=list(temp.keys())\n",
    "    t2=[temp[i] for i in temp]\n",
    "\n",
    "    while len(t2)!=0:\n",
    "        temp1={}\n",
    "        I=[]\n",
    "        Min=min(t2)\n",
    "        Ind=t2.index(Min)\n",
    "        st_old=st\n",
    "        st=t1[Ind]\n",
    "        label_st=Min\n",
    "        P[st]=label_st\n",
    "        del V1[V1.index(st)]\n",
    "    \n",
    "    \n",
    "        for i in V1:\n",
    "            if [i, st] in E1:\n",
    "                old_label=temp[i]\n",
    "                o1=old_label[0]\n",
    "                o2=old_label[1]\n",
    "                ind=E1.index([i, st])\n",
    "                if o1<=label_st[0]+E2[ind]: temp1[i]=old_label\n",
    "                else:\n",
    "                    Minimum=min([o1, label_st[0]+E2[ind]])\n",
    "                    temp1[i]=[Minimum, st]\n",
    "                    I+=[ind,]\n",
    "        \n",
    "            elif [st, i] in E1:\n",
    "                old_label=temp[i]\n",
    "                o1=old_label[0]\n",
    "                o2=old_label[1]\n",
    "                ind=E1.index([st, i])\n",
    "                if o1<=label_st[0]+E2[ind]: temp1[i]=old_label\n",
    "                else:\n",
    "                    Minimum=min([o1, label_st[0]+E2[ind]])\n",
    "                    temp1[i]=[Minimum, st]\n",
    "                    I+=[ind,]\n",
    "        \n",
    "            elif (not [i, st] in E1) or (not [st, i] in E1):\n",
    "                temp1[i]=temp[i]\n",
    "    \n",
    "    \n",
    "        for ind in sorted(I, reverse=True): \n",
    "            del E1[ind]   \n",
    "            del E2[ind]\n",
    "        temp=temp1\n",
    "    \n",
    "        t1=list(temp.keys())\n",
    "        t2=[temp[i] for i in temp]\n",
    "\n",
    "    path=end\n",
    "    pr=P[end][1]\n",
    "    if P[end][0]==oo: return 'No shortest path exists'\n",
    "    while pr!='-':\n",
    "        path+=pr\n",
    "        pr=P[pr][1]\n",
    "    print(P)        \n",
    "    return path[::-1]\n",
    "        \n",
    "DA(Ed, V, st, end) \n",
    "    \n",
    "    "
   ]
  }
 ],
 "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
}