{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "
\n", " \n", " \"QuantEcon\"\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Shortest Paths\n", "\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Contents\n", "\n", "- [Shortest Paths](#Shortest-Paths) \n", " - [Overview](#Overview) \n", " - [Outline of the Problem](#Outline-of-the-Problem) \n", " - [Finding Least-Cost Paths](#Finding-Least-Cost-Paths) \n", " - [Solving for $ J $](#Solving-for-$-J-$) \n", " - [Exercises](#Exercises) \n", " - [Solutions](#Solutions) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Overview\n", "\n", "The shortest path problem is a [classic problem](https://en.wikipedia.org/wiki/Shortest_path) in mathematics and computer science with applications in\n", "\n", "- Economics (sequential decision making, analysis of social networks, etc.) \n", "- Operations research and transportation \n", "- Robotics and artificial intelligence \n", "- Telecommunication network design and routing \n", "- etc., etc. \n", "\n", "\n", "Variations of the methods we discuss in this lecture are used millions of times every day, in applications such as\n", "\n", "- Google Maps \n", "- routing packets on the internet \n", "\n", "\n", "For us, the shortest path problem also provides a nice introduction to the logic of **dynamic programming**.\n", "\n", "Dynamic programming is an extremely powerful optimization technique that we apply in many lectures on this site." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Outline of the Problem\n", "\n", "The shortest path problem is one of finding how to traverse a [graph](https://en.wikipedia.org/wiki/Graph_%28mathematics%29) from one specified node to another at minimum cost.\n", "\n", "Consider the following graph\n", "\n", "\n", "\n", " \n", "We wish to travel from node (vertex) A to node G at minimum cost.\n", "\n", "- Arrows (edges) indicate the movements we can take. \n", "- Numbers on edges indicate the cost of traveling that edge. \n", "\n", "\n", "Possible interpretations of the graph include\n", "\n", "- Minimum cost for supplier to reach a destination. \n", "- Routing of packets on the internet (minimize time). \n", "- Etc., etc. \n", "\n", "\n", "For this simple graph, a quick scan of the edges shows that the optimal paths are\n", "\n", "- A, C, F, G at cost 8 \n", "\n", "\n", "\n", "\n", " \n", "- A, D, F, G at cost 8 \n", "\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Finding Least-Cost Paths\n", "\n", "For large graphs we need a systematic solution.\n", "\n", "Let $ J(v) $ denote the minimum cost-to-go from node $ v $, understood as the total cost from $ v $ if we take the best route.\n", "\n", "Suppose that we know $ J(v) $ for each node $ v $, as shown below for the graph from the preceding example\n", "\n", "\n", "\n", " \n", "Note that $ J(G) = 0 $.\n", "\n", "The best path can now be found as follows\n", "\n", "- Start at A. \n", "- From node v, move to any node that solves \n", "\n", "\n", "\n", "\n", "$$\n", "\\min_{w \\in F_v} \\{ c(v, w) + J(w) \\} \\tag{1}\n", "$$\n", "\n", "where\n", "\n", "- $ F_v $ is the set of nodes that can be reached from $ v $ in one step \n", "- $ c(v, w) $ is the cost of traveling from $ v $ to $ w $ \n", "\n", "\n", "Hence, if we know the function $ J $, then finding the best path is almost trivial.\n", "\n", "But how to find $ J $?\n", "\n", "Some thought will convince you that, for every node $ v $,\n", "the function $ J $ satisfies\n", "\n", "\n", "\n", "$$\n", "J(v) = \\min_{w \\in F_v} \\{ c(v, w) + J(w) \\} \\tag{2}\n", "$$\n", "\n", "This is known as the *Bellman equation*, after the mathematician Richard Bellman." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Solving for $ J $\n", "\n", "The standard algorithm for finding $ J $ is to start with\n", "\n", "\n", "\n", "$$\n", "J_0(v) = M \\text{ if } v \\not= \\text{ destination, else } J_0(v) = 0 \\tag{3}\n", "$$\n", "\n", "where $ M $ is some large number.\n", "\n", "Now we use the following algorithm\n", "\n", "1. Set $ n = 0 $. \n", "1. Set $ J_{n+1} (v) = \\min_{w \\in F_v} \\{ c(v, w) + J_n(w) \\} $ for all $ v $. \n", "1. If $ J_{n+1} $ and $ J_n $ are not equal then increment $ n $, go to 2. \n", "\n", "\n", "In general, this sequence converges to $ J $—the proof is omitted." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercises\n", "\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 1\n", "\n", "Use the algorithm given above to find the optimal path (and its cost) for the\n", "following graph." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Setup" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "hide-output": true }, "outputs": [], "source": [ "using InstantiateFromURL\n", "# optionally add arguments to force installation: instantiate = true, precompile = true\n", "github_project(\"QuantEcon/quantecon-notebooks-julia\", version = \"0.8.0\")" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "hide-output": false }, "outputs": [], "source": [ "using LinearAlgebra, Statistics" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "hide-output": false }, "outputs": [ { "data": { "text/plain": [ "Dict{Int64,Array{Tuple{Int64,Float64},1}} with 100 entries:\n", " 68 => [(71, 1.66), (70, 3.35), (94, 232.1)]\n", " 2 => [(45, 1561.45), (31, 166.8), (66, 54.18)]\n", " 89 => [(99, 82.12), (97, 36.97)]\n", " 11 => [(20, 65.08), (18, 37.55), (94, 4961.32)]\n", " 39 => [(41, 1.34), (40, 0.95), (50, 39.88)]\n", " 46 => [(67, 65.48), (57, 27.5), (52, 22.68)]\n", " 85 => [(89, 4.9), (87, 2.66), (97, 94.51)]\n", " 25 => [(35, 45.55), (32, 36.58), (70, 1343.63)]\n", " 55 => [(64, 60.8), (57, 2.13), (84, 86.09)]\n", " 42 => [(72, 437.49), (47, 10.08), (59, 141.86)]\n", " 29 => [(33, 12.61), (32, 4.22), (64, 635.52)]\n", " 58 => [(65, 34.32), (64, 29.85), (83, 556.7)]\n", " 66 => [(73, 37.53), (68, 2.66), (98, 395.63)]\n", " 59 => [(71, 0.67), (60, 0.72), (90, 820.66)]\n", " 8 => [(12, 3.18), (11, 7.45), (69, 577.91)]\n", " 74 => [(78, 8.08), (76, 0.52), (81, 1.07)]\n", " 95 => [(99, 0.27), (98, 6.17)]\n", " 57 => [(60, 7.01), (58, 0.46), (86, 701.09)]\n", " 20 => [(33, 145.8), (24, 9.81), (98, 3523.33)]\n", " 90 => [(99, 50.99), (94, 10.47), (96, 23.53)]\n", " 14 => [(24, 38.65), (16, 2.7), (67, 1878.96)]\n", " 31 => [(44, 125.88), (36, 20.44), (98, 3350.98)]\n", " 78 => [(81, 2.59), (98, 355.9)]\n", " 70 => [(73, 8.37), (72, 1.5), (76, 27.18)]\n", " 33 => [(47, 111.54), (41, 3.23), (81, 1854.73)]\n", " ⋮ => ⋮" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph = Dict(zip(0:99, [[(14, 72.21), (8, 11.11), (1, 0.04)],[(13, 64.94), (6, 20.59), (46, 1247.25)],[(45, 1561.45), (31, 166.8), (66, 54.18)],[(11, 42.43), (6, 2.06), (20, 133.65)],[(7, 1.02), (5, 0.73), (75, 3706.67)],[(11, 34.54),(7, 3.33),(45, 1382.97)],[(10, 13.1), (9, 0.72), (31, 63.17)],[(10, 5.85), (9, 3.15), (50, 478.14)], [(12, 3.18), (11, 7.45), (69, 577.91)],[(20, 16.53), (13, 4.42), (70, 2454.28)],[(16, 25.16), (12, 1.87), (89, 5352.79)],[(20, 65.08), (18, 37.55), (94, 4961.32)],[(28, 170.04), (24, 34.32), (84, 3914.62)],[(40, 475.33), (38, 236.33), (60, 2135.95)],[(24, 38.65), (16, 2.7),(67, 1878.96)],[(18, 2.57),(17, 1.01),(91, 3597.11)],[(38, 278.71),(19, 3.49),(36, 392.92)],[(23, 26.45), (22, 24.78), (76, 783.29)],[(28, 55.84), (23, 16.23), (91, 3363.17)],[(28, 70.54), (20, 0.24), (26, 20.09)],[(33, 145.8), (24, 9.81),(98, 3523.33)],[(31, 27.06),(28, 36.65),(56, 626.04)], [(40, 124.22), (39, 136.32), (72, 1447.22)],[(33, 22.37), (26, 2.66), (52, 336.73)],[(28, 14.25), (26, 1.8), (66, 875.19)],[(35, 45.55),(32, 36.58),(70, 1343.63)],[(42, 122.0),(27, 0.01), (47, 135.78)],[(43, 246.24), (35, 48.1),(65, 480.55)],[(36, 15.52), (34, 21.79), (82, 2538.18)],[(33, 12.61), (32, 4.22),(64, 635.52)], [(35, 13.95), (33, 5.61), (98, 2616.03)],[(44, 125.88),(36, 20.44), (98, 3350.98)],[(35, 1.46), (34, 3.33), (97, 2613.92)], [(47, 111.54), (41, 3.23), (81, 1854.73)],[(48, 129.45), (42, 51.52), (73, 1075.38)],[(50, 78.81), (41, 2.09), (52, 17.57)], [(57, 260.46), (54, 101.08), (71, 1171.6)],[(46, 80.49),(38, 0.36), (75, 269.97)],[(42, 8.78), (40, 1.79), (93, 2767.85)],[(41, 1.34), (40, 0.95), (50, 39.88)],[(54, 53.46), (47, 28.57), (75, 548.68)], [(54, 162.24), (46, 0.28), (53, 18.23)],[(72, 437.49), (47, 10.08), (59, 141.86)],[(60, 116.23), (54, 95.06), (98, 2984.83)], [(47, 2.14), (46, 1.56), (91, 807.39)],[(49, 15.51), (47, 3.68), (58, 79.93)],[(67, 65.48), (57, 27.5), (52, 22.68)],[(61, 172.64), (56, 49.31), (50, 2.82)],[(60, 66.44), (59, 34.52), (99, 2564.12)], [(56, 10.89), (50, 0.51), (78, 53.79)],[(55, 20.1), (53, 1.38), (85, 251.76)],[(60, 73.79),(59, 23.67),(98, 2110.67)], [(66, 123.03), (64, 102.41), (94, 1471.8)],[(67, 88.35),(56, 4.33), (72, 22.85)],[(73, 238.61), (59, 24.3), (88, 967.59)],[(64, 60.8), (57, 2.13), (84, 86.09)],[(61, 11.06), (57, 0.02), (76, 197.03)], [(60, 7.01), (58, 0.46), (86, 701.09)],[(65, 34.32), (64, 29.85), (83, 556.7)],[(71, 0.67), (60, 0.72), (90, 820.66)],[(67, 1.63), (65, 4.76), (76, 48.03)],[(64, 4.88), (63, 0.95), (98, 1057.59)], [(76, 38.43), (64, 2.94), (91, 132.23)],[(75, 56.34), (72, 70.08), (66, 4.43)],[(76, 11.98), (65, 0.3), (80, 47.73)],[(73, 33.23), (66, 0.64), (94, 594.93)],[(73, 37.53), (68, 2.66), (98, 395.63)], [(70, 0.98), (68, 0.09), (82, 153.53)],[(71, 1.66), (70, 3.35), (94, 232.1)],[(73, 8.99), (70, 0.06), (99, 247.8)],[(73, 8.37), (72, 1.5), (76, 27.18)],[(91, 284.64), (74, 8.86), (89, 104.5)], [(92, 133.06), (84, 102.77), (76, 15.32)],[(90, 243.0), (76, 1.4), (83, 52.22)],[(78, 8.08), (76, 0.52), (81, 1.07)],[(77, 1.19), (76, 0.81), (92, 68.53)],[(78, 2.36), (77, 0.45), (85, 13.18)], [(86, 64.32), (78, 0.98), (80, 8.94)],[(81, 2.59), (98, 355.9)],[(91, 22.35), (85, 1.45), (81, 0.09)],[(98, 264.34), (88, 28.78), (92, 121.87)],[(92, 99.89), (89, 39.52), (94, 99.78)],[(93, 11.99), (88, 28.05), (91, 47.44)],[(88, 5.78), (86, 8.75), (94, 114.95)], [(98, 121.05), (94, 30.41), (89, 19.14)],[(89, 4.9), (87, 2.66), (97, 94.51)],[(97, 85.09)],[(92, 21.23), (91, 11.14), (88, 0.21)], [(98, 6.12), (91, 6.83), (93, 1.31)],[(99, 82.12), (97, 36.97)], [(99, 50.99), (94, 10.47), (96, 23.53)],[(97, 22.17)],[(99, 34.68), (97, 11.24), (96, 10.83)],[(99, 32.77), (97, 6.71), (94, 0.19)], [(96, 2.03), (98, 5.91)],[(99, 0.27), (98, 6.17)],[(99, 5.87), (97, 0.43), (98, 3.32)],[(98, 0.3)],[(99, 0.33)],[(99, 0.0)]]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The cost from node 68 to node 71 is 1.66 and so on." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Solutions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 1" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "hide-output": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "node 0\n", "node 8\n", "node 11\n", "node 18\n", "node 23\n", "node 33\n", "node 41\n", "node 53\n", "node 56\n", "node 57\n", "node 60\n", "node 67\n", "node 70\n", "node 73\n", "node 76\n", "node 85\n", "node 87\n", "node 88\n", "node 93\n", "node 94\n", "node 96\n", "node 97\n", "node 98\n", "node 99\n", "Cost: 160.55\n" ] } ], "source": [ "function update_J!(J, graph)\n", " next_J = Dict()\n", " for node in keys(graph)\n", " if node == 99\n", " next_J[node] = 0\n", " else\n", " next_J[node] = minimum(cost + J[dest] for (dest, cost) in graph[node])\n", " end\n", " end\n", " return next_J\n", "end\n", "\n", "function print_best_path(J, graph)\n", " sum_costs = 0.0\n", " current_location, destination = extrema(keys(graph))\n", " while current_location != destination\n", " println(\"node $current_location\")\n", " running_min = 1e10\n", " minimizer_dest = Inf\n", " minimizer_cost = 1e10\n", " for (dest, cost) in graph[current_location]\n", " cost_of_path = cost + J[dest]\n", " if cost_of_path < running_min\n", " running_min = cost_of_path\n", " minimizer_cost = cost\n", " minimizer_dest = dest\n", " end\n", " end\n", "\n", " current_location = minimizer_dest\n", " sum_costs += minimizer_cost\n", " end\n", "\n", " sum_costs = round(sum_costs, digits = 2)\n", "\n", " println(\"node $destination\\nCost: $sum_costs\")\n", "end\n", "\n", "J = Dict((node => Inf) for node in keys(graph))\n", "\n", "while true\n", " next_J = update_J!(J, graph)\n", " if next_J == J\n", " break\n", " else\n", " J = next_J\n", " end\n", "end\n", "\n", "print_best_path(J, graph)" ] } ], "metadata": { "date": 1591310617.4229577, "download_nb": 1, "download_nb_path": "https://julia.quantecon.org/", "filename": "short_path.rst", "filename_with_path": "dynamic_programming/short_path", "kernelspec": { "display_name": "Julia 1.4.2", "language": "julia", "name": "julia-1.4" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.4.2" }, "title": "Shortest Paths" }, "nbformat": 4, "nbformat_minor": 2 }