Chapter_25_All-Pairs_Shortest_Paths/exercises_25.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 25.2 The Floyd-Warshall algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.2-1\n",
    "\n",
    "> Run the Floyd-Warshall algorithm on the weighted, directed graph of Figure 25.2. Show the matrix $D^{(k)}$ that results for each iteration of the outer loop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$k=1$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & \\infty & \\infty & \\infty & -1 & \\infty\\\\\n",
    "1 & 0 & \\infty & 2 & 0 & \\infty\\\\\n",
    "\\infty & 2 & 0 & \\infty & \\infty & -8\\\\\n",
    "-4 & \\infty & \\infty & 0 & -5 & \\infty\\\\\n",
    "\\infty & 7 & \\infty & \\infty & 0 & \\infty\\\\\n",
    "\\infty & 5 & 10 & \\infty & \\infty & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$\n",
    "\n",
    "$k=2$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & \\infty & \\infty & \\infty & -1 & \\infty\\\\\n",
    "1 & 0 & \\infty & 2 & 0 & \\infty\\\\\n",
    "3 & 2 & 0 & 4 & 2 & -8\\\\\n",
    "-4 & \\infty & \\infty & 0 & -5 & \\infty\\\\\n",
    "8 & 7 & \\infty & 9 & 0 & \\infty\\\\\n",
    "6 & 5 & 10 & 7 & 5 & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$\n",
    "\n",
    "$k=3$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & \\infty & \\infty & \\infty & -1 & \\infty\\\\\n",
    "1 & 0 & \\infty & 2 & 0 & \\infty\\\\\n",
    "3 & 2 & 0 & 4 & 2 & -8\\\\\n",
    "-4 & \\infty & \\infty & 0 & -5 & \\infty\\\\\n",
    "8 & 7 & \\infty & 9 & 0 & \\infty\\\\\n",
    "6 & 5 & 10 & 7 & 5 & 0\\\\\n",
    "\\end{matrix} \\right \\}\n",
    "$$\n",
    "\n",
    "$k=4$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & \\infty & \\infty & \\infty & -1 & \\infty\\\\\n",
    "-2 & 0 & \\infty & 2 & -3 & \\infty\\\\\n",
    "0 & 2 & 0 & 4 & -1 & -8\\\\\n",
    "-4 & \\infty & \\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",
    "$k=5$:\n",
    "$$\n",
    "\\left \\{ \\begin{matrix}\n",
    "0 & 6 & \\infty & 8 & -1 & \\infty\\\\\n",
    "-2 & 0 & \\infty & 2 & -3 & \\infty\\\\\n",
    "0 & 2 & 0 & 4 & -1 & -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",
    "$k=6$:\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.2-2\n",
    "\n",
    "> Show how to compute the transitive closure using the technique of Section 25.1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.2-3\n",
    "\n",
    "> Modify the FLOYD-WARSHALL procedure to compute the $\\prod^{(k)}$ matrices according to equations (25.6) and (25.7). Prove rigorously that for all $i \\in V$, the predecessor subgraph $G_{\\pi, i}$ is a shortest-paths tree with root $i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.2-4\n",
    "\n",
    "> As it appears above, the Floyd-Warshall algorithm requires $\\Theta(n^3)$ space, since we compute $d_{ij}^{(k)}$ for $i, j, k = 1, 2, \\dots, n$. Show that the following procedure, which simply drops all the superscripts, is correct, and thus only $\\Theta(n^2)$ space is required."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.2-5\n",
    "\n",
    "> Suppose that we modify the way in which equation (25.7) handles equality:\n",
    "\n",
    "> $$\n",
    "\\pi_{ij}^{(k)} = \\left \\{ \n",
    "\\begin{array}{ll}\n",
    "\\pi_{ij}^{(k-1)} & ~\\text{if}~ d_{ij}^{(k-1)} < d_{ik}^{(k-1)} + d_{kj}^{(k-1)}, \\\\\n",
    "\\pi_{kj}^{(k-1)} & ~\\text{if}~ d_{ij}^{(k-1)} \\ge d_{ik}^{(k-1)} + d_{kj}^{(k-1)}.\n",
    "\\end{array}\n",
    "\\right .\n",
    "$$\n",
    "\n",
    "> Is this alternative definition of the predecessor matrix $\\prod$ correct?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.2-6\n",
    "\n",
    "> How can we use the output of the Floyd-Warshall algorithm to detect the presence of a negative-weight cycle?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $D^{(n+1)} \\ne D^{(n)}$, then the graph contains negative-weight cycle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.2-7\n",
    "\n",
    "> Another way to reconstruct shortest paths in the Floyd-Warshall algorithm uses values $\\phi_{ij}^{(k)}$ for $i, j, k = 1, 2, \\dots, n$, where $\\phi_{ij}^{(k)}$ is the highest-numbered intermediate vertex of a shortest path from $i$ to $j$ in which all intermediate vertices are in the set $\\{1, 2, \\dots, k \\}$. Give a recursive formulation for $\\phi_{ij}^{(k)}$, modify the FLOYD-WARSHALL procedure to compute the $\\phi_{ij}^{(k)}$ values, and rewrite the PRINT-ALLPAIRS- SHORTEST-PATH procedure to take the matrix $\\Phi = (\\phi_{ij}^{(n)})$ as an input. How is the matrix $\\Phi$ like the $s$ table in the matrix-chain multiplication problem of Section 15.2?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.2-8\n",
    "\n",
    "> Give an $O(VE)$-time algorithm for computing the transitive closure of a directed\n",
    "graph $G = (V, E)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DFS from each vertex."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 25.2-9\n",
    "\n",
    "> Suppose that we can compute the transitive closure of a directed acyclic graph in $f(|V|, |E|)$ time, where $f$ is a monotonically increasing function of $|V|$ and $|E|$. Show that the time to compute the transitive closure $G^* = (V, E^*)$ of a general directed graph $G = (V, E)$ is then $f(|V|, |E|) + O(V + E^*)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All the pairs of vertices in one SCC are connected, and the SCCs forms a directed acyclic graph."
   ]
  }
 ],
 "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
}