Chapter_25_All-Pairs_Shortest_Paths/exercises_25.1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 25.1 Shortest paths and matrix multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.1-1\n",
    "\n",
    "> Run SLOW-ALL-PAIRS-SHORTEST-PATHS on the weighted, directed graph of Figure 25.2, showing the matrices that result for each iteration of the loop. Then do the same for FASTER-ALL-PAIRS-SHORTEST-PATHS."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initial:\n",
    "\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & \\infty & \\infty & \\infty & -1 & \\infty\\\\\n",
    "1 & 0 & \\infty & 2 & \\infty & \\infty\\\\\n",
    "\\infty & 2 & 0 & \\infty & \\infty & -8\\\\\n",
    "-4 & \\infty & \\infty & 0 & 3 & \\infty\\\\\n",
    "\\infty & 7 & \\infty & \\infty & 0 & \\infty\\\\\n",
    "\\infty & 5 & 10 & \\infty & \\infty & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$\n",
    "Slow:\n",
    "\n",
    "$m=2$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & 6 & \\infty & \\infty & -1 & \\infty\\\\\n",
    "-2 & 0 & \\infty & 2 & 0 & \\infty\\\\\n",
    "3 & -3 & 0 & 4 & \\infty & -8\\\\\n",
    "-4 & 10 & \\infty & 0 & -5 & \\infty\\\\\n",
    "8 & 7 & \\infty & 9 & 0 & \\infty\\\\\n",
    "6 & 5 & 10 & 7 & \\infty & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$\n",
    "\n",
    "$m=3$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & 6 & \\infty & 8 & -1 & \\infty\\\\\n",
    "-2 & 0 & \\infty & 2 & -3 & \\infty\\\\\n",
    "-2 & -3 & 0 & -1 & 2 & -8\\\\\n",
    "-4 & 2 & \\infty & 0 & -5 & \\infty\\\\\n",
    "5 & 7 & \\infty & 9 & 0 & \\infty\\\\\n",
    "3 & 5 & 10 & 7 & 5 & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$\n",
    "\n",
    "$m=4$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & 6 & \\infty & 8 & -1 & \\infty\\\\\n",
    "-2 & 0 & \\infty & 2 & -3 & \\infty\\\\\n",
    "-5 & -3 & 0 & -1 & -3 & -8\\\\\n",
    "-4 & 2 & \\infty & 0 & -5 & \\infty\\\\\n",
    "5 & 7 & \\infty & 9 & 0 & \\infty\\\\\n",
    "3 & 5 & 10 & 7 & 2 & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$\n",
    "\n",
    "$m=5$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & 6 & \\infty & 8 & -1 & \\infty\\\\\n",
    "-2 & 0 & \\infty & 2 & -3 & \\infty\\\\\n",
    "-5 & -3 & 0 & -1 & -6 & -8\\\\\n",
    "-4 & 2 & \\infty & 0 & -5 & \\infty\\\\\n",
    "5 & 7 & \\infty & 9 & 0 & \\infty\\\\\n",
    "3 & 5 & 10 & 7 & 2 & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$\n",
    "Fast:\n",
    "\n",
    "$m=2$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & 6 & \\infty & \\infty & -1 & \\infty\\\\\n",
    "-2 & 0 & \\infty & 2 & 0 & \\infty\\\\\n",
    "3 & -3 & 0 & 4 & \\infty & -8\\\\\n",
    "-4 & 10 & \\infty & 0 & -5 & \\infty\\\\\n",
    "8 & 7 & \\infty & 9 & 0 & \\infty\\\\\n",
    "6 & 5 & 10 & 7 & \\infty & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$\n",
    "\n",
    "$m=4$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & 6 & \\infty & 8 & -1 & \\infty\\\\\n",
    "-2 & 0 & \\infty & 2 & -3 & \\infty\\\\\n",
    "-5 & -3 & 0 & -1 & -3 & -8\\\\\n",
    "-4 & 2 & \\infty & 0 & -5 & \\infty\\\\\n",
    "5 & 7 & \\infty & 9 & 0 & \\infty\\\\\n",
    "3 & 5 & 10 & 7 & 2 & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$\n",
    "\n",
    "$m=8$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & 6 & \\infty & 8 & -1 & \\infty\\\\\n",
    "-2 & 0 & \\infty & 2 & -3 & \\infty\\\\\n",
    "-5 & -3 & 0 & -1 & -6 & -8\\\\\n",
    "-4 & 2 & \\infty & 0 & -5 & \\infty\\\\\n",
    "5 & 7 & \\infty & 9 & 0 & \\infty\\\\\n",
    "3 & 5 & 10 & 7 & 2 & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.1-2\n",
    "\n",
    "> Why do we require that $w_{ii}=0$ for all $1 \\le i \\le n$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To simplify (25.2)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.1-3\n",
    "\n",
    "> What does the matrix\n",
    "\n",
    "> $$\n",
    "L^{(0)} = \\left ( \\begin{matrix}\n",
    "0 & \\infty & \\infty & \\cdots & \\infty \\\\\n",
    "\\infty & 0 & \\infty & \\cdots & \\infty \\\\\n",
    "\\infty & \\infty & 0 & \\cdots & \\infty \\\\\n",
    "\\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "\\infty & \\infty & \\infty & \\cdots & 0 \\\\\n",
    "\\end{matrix} \\right )\n",
    "$$\n",
    "\n",
    "> used in the shortest-paths algorithms correspond to in regular matrix multiplication?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.1-4\n",
    "\n",
    "> Show that matrix multiplication defined by EXTEND-SHORTEST-PATHS is associative."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.1-5\n",
    "\n",
    "> Show how to express the single-source shortest-paths problem as a product of matrices and a vector. Describe how evaluating this product corresponds to a Bellman-Ford-like algorithm (see Section 24.1)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A vector filled with 0 except that the source is 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.1-6\n",
    "\n",
    "> Suppose we also wish to compute the vertices on shortest paths in the algorithms of this section. Show how to compute the predecessor matrix $\\prod$ from the completed matrix $L$ of shortest-path weights in $O(n^3)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $l_{ik} + w_{kj} = l_{ij}$, then $\\pi_{ij} = k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.1-7\n",
    "\n",
    "> We can also compute the vertices on shortest paths as we compute the shortestpath weights. Define $\\pi_{ij}^{(m)}$ as the predecessor of vertex $j$ on any minimum-weight path from $i$ to $j$ that contains at most $m$ edges. Modify the EXTEND-SHORTESTPATHS and SLOW-ALL-PAIRS-SHORTEST-PATHS procedures to compute the matrices$\\prod^{(1)}, \\prod^{(2)}, \\dots, \\prod^{(n-1)}$ as the matrices $L^{(1)}, L^{(2)}, \\dots, L^{(n-1)}$ are computed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $l_{ik}^{(m-1)} + w_{kj} < l_{ij}^{(m)}$, then $\\pi_{ij}^{(m)} = k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.1-8\n",
    "\n",
    "> The FASTER-ALL-PAIRS-SHORTEST-PATHS procedure, as written, requires us to store $\\lceil \\lg (n - 1) \\rceil$ matrices, each with $n^2$ elements, for a total space requirement of $\\Theta(n^2 \\lg n)$. Modify the procedure to require only $\\Theta(n^2)$ space by using only two $n \\times n$ matrices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fast_all_pairs_shortest_paths(w):\n",
    "    n = len(w)\n",
    "    m = 1\n",
    "    while m < n - 1:\n",
    "        w = extend_shortest_paths(w, w)\n",
    "        m *= 2\n",
    "    return w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.1-9\n",
    "\n",
    "> Modify FASTER-ALL-PAIRS-SHORTEST-PATHS so that it can determine whether\n",
    "the graph contains a negative-weight cycle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $l_{ii} < 0$, then there is a negative-weight cycle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.1-10\n",
    "\n",
    "> Give an efficient algorithm to find the length (number of edges) of a minimum-length negative-weight cycle in a graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $l_{ii}^{(m)} < 0$ and $l_{ii}^{(m-1)} = 0$, then the minimum-length is $m$."
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}