{
"cells": [
{
"cell_type": "markdown",
"id": "35104402",
"metadata": {},
"source": [
"\n",
""
]
},
{
"cell_type": "markdown",
"id": "db3a73ae",
"metadata": {},
"source": [
"# Shortest Paths\n",
"\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"id": "15dd4aca",
"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",
"id": "1ee5478e",
"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",
"id": "3fb134ac",
"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",
"![https://julia.quantecon.org/_static/figures/graph.png](https://julia.quantecon.org/_static/figures/graph.png)\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",
"![https://julia.quantecon.org/_static/figures/graph4.png](https://julia.quantecon.org/_static/figures/graph4.png)\n",
"\n",
" \n",
"- A, D, F, G at cost 8 \n",
"\n",
"\n",
"![https://julia.quantecon.org/_static/figures/graph3.png](https://julia.quantecon.org/_static/figures/graph3.png)"
]
},
{
"cell_type": "markdown",
"id": "c6820295",
"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",
"![https://julia.quantecon.org/_static/figures/graph2.png](https://julia.quantecon.org/_static/figures/graph2.png)\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{27.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{27.2}\n",
"$$\n",
"\n",
"This is known as the *Bellman equation*, after the mathematician Richard Bellman."
]
},
{
"cell_type": "markdown",
"id": "067fba07",
"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{27.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",
"id": "363eee93",
"metadata": {},
"source": [
"## Exercises\n",
"\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"id": "fe9ad191",
"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": "code",
"execution_count": null,
"id": "539778c9",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"using LinearAlgebra, Statistics"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "54f3ee2c",
"metadata": {
"hide-output": false
},
"outputs": [],
"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",
"id": "6e21a922",
"metadata": {},
"source": [
"The cost from node 68 to node 71 is 1.66 and so on."
]
},
{
"cell_type": "markdown",
"id": "d4e6e250",
"metadata": {},
"source": [
"## Solutions"
]
},
{
"cell_type": "markdown",
"id": "4b10abb7",
"metadata": {},
"source": [
"### Exercise 1"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "233f5c87",
"metadata": {
"hide-output": false
},
"outputs": [],
"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": 1674536744.5665789,
"filename": "short_path.md",
"kernelspec": {
"display_name": "Julia",
"language": "julia",
"name": "julia-1.8"
},
"title": "Shortest Paths"
},
"nbformat": 4,
"nbformat_minor": 5
}