{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": { "code_folding": [], "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# setup\n", "from IPython.core.display import display,HTML\n", "display(HTML(''))\n", "display(HTML(open('../rise.css').read()))\n", "\n", "# imports\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import seaborn as sns\n", "%matplotlib inline\n", "sns.set(style=\"whitegrid\", font_scale=1.5, rc={'figure.figsize':(12, 6)})\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# CMPS 2200\n", "# Introduction to Algorithms\n", "\n", "## Shortest Path\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Generalizing DFS and BFS search\n", "\n", "We've now seen two types of search that are conceptually very similar.\n", "\n", "\n", "`dfs_stack`:\n", "\n", "- `node = frontier.pop()`\n", "\n", "\n", "`bfs_serial`:\n", "\n", "- `node = frontier.popleft()`\n", "\n", "Can we generalize these?" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "visiting A\n", "visiting C\n", "visiting B\n", "visiting G\n", "visiting F\n", "visiting D\n", "visiting E\n", "visiting H\n" ] }, { "data": { "text/plain": [ "{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from collections import deque\n", "\n", "def generic_search(graph, source, get_next_node_fn):\n", " def generic_search_helper(visited, frontier):\n", " if len(frontier) == 0:\n", " return visited\n", " else:\n", " ## pick a node\n", " node = get_next_node_fn(frontier)\n", " print('visiting', node)\n", " visited.add(node)\n", " frontier.extend(filter(lambda n: n not in visited, graph[node]))\n", " return generic_search_helper(visited, frontier)\n", " \n", " frontier = deque()\n", " frontier.append(source)\n", " visited = set()\n", " return generic_search_helper(visited, frontier)\n", "\n", "def bfs_fn(frontier):\n", " return frontier.popleft()\n", "\n", "def dfs_fn(frontier):\n", " return frontier.pop()\n", "\n", "graph = {\n", " 'A': {'B', 'C'},\n", " 'B': {'A', 'D', 'E'},\n", " 'C': {'A', 'F', 'G'},\n", " 'D': {'B'},\n", " 'E': {'B', 'H'},\n", " 'F': {'C'},\n", " 'G': {'C'},\n", " 'H': {'E'}\n", " }\n", "\n", "generic_search(graph, 'A', bfs_fn)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "visiting A\n", "visiting B\n", "visiting E\n", "visiting H\n", "visiting D\n", "visiting C\n", "visiting F\n", "visiting G\n" ] }, { "data": { "text/plain": [ "{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "generic_search(graph, 'A', dfs_fn)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Priority First Search\n", "\n", "We can view the `get_next_node_fn` as a way to pick the **highest priority** node to visit at each iteration.\n", "\n", "E.g., consider a Web crawler that prioritizes which pages to visit first\n", "- more intereseting pages\n", "- pages that update more frequently\n", "\n", "\n", "We'll see several algorithms that are instances of priority first search. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Weighted graphs\n", "\n", "Up to now we have focused on unweighted graphs. \n", "\n", "For many problems, we need to associate real-valued **weights** to each edge.\n", "\n", "E.g., consider a graph where nodes are cities and edges represent the distance between them. \n", "\n", "\n", "\n", "The **weight of a path** in the graph is the sum of the weights of the edges along that path.\n", "\n", "The **shortest weighted path** (or just **shortest path**) between **s** and **e** is the one with minimal weight.\n", "\n", "**What is the shortest path from s to e**?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We saw that we can use BFS to get the distance from the source to each node.\n", "\n", "Can we use BFS to solve the shortest path problem for weighted graphs?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "\n", "\n", "BFS will:\n", "- visit b\n", "- visit a\n", "- but, will not visit path from a to b, since it doesn't visit a node more than once\n", "\n", "Thus, BFS will not discover that the shortest path from $s$ to $b$ is $s \\rightarrow a \\rightarrow b$.\n", "\n", "\n", "How could we modify the graph so we can use BFS to find the shortest path?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "\n", "\n", "

\n", "\n", "What is work of creating this graph from the original?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "BFS takes $O(|V|+|E|)$ time, but the number of new edges could be equal to the total weight of all edges, say $W$. (Consider a simple chain.)\n", "\n", "The input size $O(|V| + |E| + \\log W)$, but the work is $O(W)$ in the worst case. Thus reducing shortest paths to BFS requires work that is exponential in input size!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Consider another example:\n", "\n", "\n", "\n", "What is the shortest path from $s$ to $e$?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "> Infinite loop in the cycle $s \\rightarrow a \\rightarrow b \\rightarrow a$, so shortest path is $-\\infty$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "## SSSP: Single-Source Shortest Path\n", "\n", "Given a weighted graph $G=(V,E,w)$ and a source vertex $s$, the single-source shortest path (SSSP) problem is to find a shortest weighted path from $s$ to every other vertex in $V$.\n", "\n", "What would be a brute-force solution to this problem?\n", "\n", "Is there anything we could reuse to improve the brute-force solution?\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Consider this figure:\n", "\n", "\n", "\n", "Suppose that an oracle has told us the shortest paths from $s$ to all vertices except for the vertex $v$, shown in red squares. How can we find the shortest path to $v$?\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Let $\\delta_G(i,j)$ be the weight of shortest path from $i$ to $j$ in graph $G$. Then:\n", "\n", "$$\n", "\\begin{align}\n", "\\delta_G(s,v) = \\min(&\\delta_G(s,a)+3,\\\\\n", "&\\delta_G(s,b)+6,\\\\\n", "&\\delta_G(s,c)+5 )\n", "\\end{align}\n", "$$\n", "\n", "### sub-paths property\n", "> any sub-path of a shortest path is itself a shortest path. \n", "\n", "The sub-paths property makes it possible to construct shortest paths from smaller shortest paths. \n", "\n", "> If a shortest path from Pittsburgh to San Francisco goes through Chicago, then that shortest path includes the shortest path from Pittsburgh to Chicago, and from Chicago to San Francisco." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Dijkstra's property\n", "\n", "For any partitioning of vertices $V$ into $X$ and $Y = V \\setminus X$ with $s \\in X$:\n", "\n", "If $p(v) = \\min_{x \\in X} (\\delta_G(s,x) + w(x,v))$, then\n", "\n", "$$\\min_{y \\in Y} p(y) = \\min_{y \\in Y} \\delta_G(s, y)$$\n", "\n", "> The overall shortest-path weight from $s$ via a vertex in $X$ directly to a neighbor in $Y$ (in the frontier) is as short as any path from $s$ to any vertex in $Y$\n", "\n", "
\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "This property suggest that we can start with shortest paths to a node frontier, then extend them beyond the frontier to get longer, shortest paths.\n", "\n", "But, what order should we visit nodes? Consider this graph again:\n", "\n", "
\n", "\n", "
\n", "\n", "If we visit $b$ before $a$, we will still not discover that the shortest path from $s$ to $b$ is $s \\rightarrow a \\rightarrow b$.\n", "\n", "Instead, we must visit nodes in increasing distance from the source.\n", "\n", "
\n", "\n", "
\n", "Assume we know the shortest paths to $\\{a,b,c,e\\}$. We can then use these to determine whether $u$ or $v$ is closer to $s$.\n", "\n", "The idea of Dijkstra's algorithm is:\n", "- Maintain a visited set of vertices whose distances have already been computed correctly.\n", "- Calculate distances to each node in the frontier.\n", "- Extend the frontier by visiting the closest vertex.\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "> What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in '59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame.\n", "\n", "— Edsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM, 2001" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Dijkstra's Algorithm\n", "\n", "The final algorithm can be viewed as an instance of **priority-first search**, using the path length as the priority criterion.\n", "\n", "1. Initialize frontier to $(s, 0)$\n", "2. While frontier not empty:\n", " - pop from the frontier the minimum node $v$ with distance $d$ from the source.\n", " - set $result(v) = d$ to be the weight of the shortest path from $s$ to $v$\n", " - For each neighbor $x$ of $v$ with edge weight $w$, add $x$ to frontier with distance $d + w$\n", "3. return $result$" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Head value of heap : (10, 'a')\n", "Head value of heap : (20, 'c')\n", "Head value of heap : (30, 'b')\n", "Head value of heap : (400, 'd')\n" ] } ], "source": [ "# Heaps in Python\n", "from heapq import heappush, heappop \n", " \n", "# Creating empty heap \n", "heap = [] \n", " \n", "# Adding items to the heap using heappush function \n", "heappush(heap, (10, 'a')) \n", "heappush(heap, (30, 'b')) \n", "heappush(heap, (20, 'c')) \n", "heappush(heap, (400, 'd')) \n", "print(\"Head value of heap : \"+str(heappop(heap)))\n", "print(\"Head value of heap : \"+str(heappop(heap)))\n", "print(\"Head value of heap : \"+str(heappop(heap)))\n", "print(\"Head value of heap : \"+str(heappop(heap)))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "
\n", " \n", "
" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "visiting s\n", "...distance= 0\n", "visiting a\n", "...distance= 1\n", "visiting b\n", "...distance= 3\n", "visiting c\n", "...distance= 4\n", "visiting c\n", "visiting d\n", "...distance= 7\n", "visiting d\n" ] }, { "data": { "text/plain": [ "{'s': 0, 'a': 1, 'b': 3, 'c': 4, 'd': 7}" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def dijkstra(graph, source):\n", " def dijkstra_helper(visited, frontier):\n", " if len(frontier) == 0:\n", " return visited\n", " else:\n", " # Pick next closest node from heap\n", " distance, node = heappop(frontier)\n", " print('visiting', node)\n", " if node in visited:\n", " # Already visited, so ignore this longer path\n", " return dijkstra_helper(visited, frontier)\n", " else:\n", " # We now know the shortest path from source to node.\n", " # insert into visited dict.\n", " visited[node] = distance\n", " print('...distance=', distance)\n", " # Visit each neighbor of node and insert into heap.\n", " # We may add same node more than once, heap\n", " # will keep shortest distance prioritized.\n", " for neighbor, weight in graph[node]:\n", " heappush(frontier, (distance + weight, neighbor)) \n", " return dijkstra_helper(visited, frontier)\n", " \n", " frontier = []\n", " heappush(frontier, (0, source))\n", " visited = dict() # store the final shortest paths for each node.\n", " return dijkstra_helper(visited, frontier)\n", "\n", "graph = {\n", " 's': {('a', 1), ('c', 5)},\n", " 'a': {('b', 2)}, # 'a': {'b'},\n", " 'b': {('c', 1), ('d', 5)}, \n", " 'c': {('d', 3)},\n", " 'd': {},\n", " 'e': {('d', 0)}\n", " }\n", "dijkstra(graph, 's')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "
\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "
\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "
\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "
\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "
\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "
\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "
\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "
\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Correctness of Dijkstra's Algorithm\n", "\n", "The algorithm maintains an invariant that each visited element $x \\in X$ contains the shortest path from $s$ to $x$.\n", "- That is, `visited[x]` $=\\delta_G(s,x)$\n", "\n", "\n", "- We know this is true after visiting the source, since $\\delta_G(s,x)=$ `visited[x]` $=0$\n", "- Dijkstra's property ensures that each element we remove from the heap also maintains this property" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Work of Dijkstra's Algorithm\n", "\n", "The two key lines are:\n", "\n", "```python\n", "distance, node = heappop(frontier)\n", "```\n", "\n", "and\n", "\n", "\n", "```python\n", "for neighbor, weight in graph[node]:\n", " heappush(frontier, (distance + weight, neighbor))\n", "``` \n", "\n", "What is work and span of `heappop` and `heappush`?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "$O(\\lg n)$ work and span for each, for a heap of size $n$.\n", "\n", "How many times will we call these functions?\n", "\n", "Once per edge, since a node may be added to the heap multiple times for each edge.\n", "\n", "Thus, the total work and span is $O(|E| \\log |E|)$\n", "\n", "\n", "Note that we assume constant time `dict` operations:\n", "- `visited[node] = distance`\n", "- `for neighbor, weight in graph[node]:`\n", "- These result in an additional $O(|V| + |E|)$ work, but are dominated by the above.\n", "\n", "Because this is a serial algorithm, the span is also $O(|E| \\log |E|)$" ] } ], "metadata": { "celltoolbar": "Slideshow", "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" }, "rise": { "autolaunch": true, "controls": false, "enable_chalkboard": true, "scroll": true, "theme": "simple", "transition": "fade" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": true, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": true, "toc_position": {}, "toc_section_display": true, "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 4 }