算法图解/chap07-狄克斯特拉算法Dijkstra’s-algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第7章 狄克斯特拉算法（Dijkstra’s algorithm）\n",
    "\n",
    "## 7.1 使用狄克斯特拉算法\n",
    "\n",
    "狄克斯特拉算法包含4个步骤。\n",
    "- (1) 找出“最便宜”的节点，即可在最短时间内到达的节点。\n",
    "- (2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。\n",
    "- (3) 重复这个过程，直到对图中的每个节点都这样做了。\n",
    "- (4) 计算最终路径。\n",
    "\n",
    "## 7.2 术语\n",
    "\n",
    "狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重（weight）。\n",
    "\n",
    "带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/8yNcKRSelznPmki.png)\n",
    "\n",
    "要计算非加权图中的最短路径，可使用**广度优先搜索**。要计算加权图中的最短路径，可使用**狄克斯特拉算法**。图还可能有环，意味着你可从一个节点出发，走一圈后又回到这个节点。每绕环一次，总权重都增加。因此，绕环的路径不可能是最短的路径。\n",
    "\n",
    "无向图意味着两个节点彼此指向对方，其实就是环！\n",
    "\n",
    "在无向图中，每条边都是一个环。狄克斯特拉算法只适用于**有向无环图（directed acyclicgraph，DAG）**。\n",
    "\n",
    "\n",
    "## 7.3 换钢琴\n",
    "\n",
    "这个图中的节点是大家愿意拿出来交换的东西，边的权重是交换时需要额外加多少钱。拿海报换吉他需要额外加30美元，拿黑胶唱片换吉他需要额外加15美元。Rama需要确定采用哪种路径将乐谱换成钢琴时需要支付的额外费用最少。\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/eT9ov3yuagpKfBP.png)\n",
    "\n",
    "动手之前，你需要做些准备工作：创建一个表格，在其中列出每个节点的开销。这里的开销指的是达到节点需要额外支付多少钱。\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/bZ8eSDQVpxs7IC5.png)\n",
    "\n",
    "在执行狄克斯特拉算法的过程中，你将不断更新这个表。为计算最终路径，还需在这个表中添加表示父节点的列。\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/vBx1zX52gJdIqRs.png)\n",
    "\n",
    "**第一步：找出最便宜的节点。**在这里，换海报最便宜，不需要支付额外的费用。还有更便宜的换海报的途径吗？这一点非常重要，你一定要想一想。Rama能够通过一系列交换得到海报，还能额外得到钱吗？想清楚后接着往下读。答案是不能，因为海报是Rama能够到达的最便宜的节点，没法再便宜了。\n",
    "\n",
    "狄克斯特拉算法背后的关键理念：找出图中最便宜的节点，并确保没有到该节点的便宜的路径！\n",
    "\n",
    "**第二步：计算前往该节点的各个邻居的开销。**\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/z7dQjI29fLxctMa.png)\n",
    "\n",
    "**再次执行第一步**：下一个最便宜的节点是黑胶唱片——需要额外支付5美元。\n",
    "\n",
    "**再次执行第二步**：更新黑胶唱片的各个邻居的开销。\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/nT17dwOJ2GFvLqu.png)\n",
    "\n",
    "你更新了架子鼓和吉他的开销！这意味着经“黑胶唱片”前往“架子鼓”和“吉他”的开销更低，因此你将这些乐器的父节点改为黑胶唱片。\n",
    "\n",
    "下一个最便宜的是吉他，因此更新其邻居的开销。\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/VNE4nP31kqGFz6K.png)\n",
    "\n",
    "最后，对最后一个节点——架子鼓，做同样的处理。\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/QLaB4k57TVxAweK.png)\n",
    "\n",
    "如果用架子鼓换钢琴，Rama需要额外支付的费用更少。因此，采用最便宜的交换路径时，Rama需要额外支付35美元。\n",
    "\n",
    "**确定最终的路径:**\n",
    "\n",
    "钢琴的父节点为架子鼓、架子鼓的父节点为黑胶唱片、黑胶唱片的父节点为乐谱（即起点）。\n",
    "\n",
    "最终路径如下：\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/QKYAtLu4ijvIVkn.png)\n",
    "\n",
    "本章前面使用的都是术语最短路径的字面意思：计算两点或两人之间的最短路径。但希望这个示例让你明白：最短路径指的并不一定是物理距离，也可能是让某种度量指标最小。在这个示例中，最短路径指的是Rama想要额外支付的费用最少。这都要归功于狄克斯特拉！\n",
    "\n",
    "## 7.4 负权边\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/LEinclohOPkba3C.png)\n",
    "\n",
    "第二种方式的开销少2美元，他应采取这种方式。然而，如果你对这个图运行狄克斯特拉算法，Rama将选择错误的路径——更长的那条路径。如果有负权边，就不能使用狄克斯特拉算法。因为负权边会导致这种算法不管用。\n",
    "\n",
    "换得架子鼓的开销为35美元。你知道有一种交换方式只需33美元，但狄克斯特拉算法没有找到。\n",
    "\n",
    "这是因为狄克斯特拉算法这样假设：**对于处理过的海报节点，没有前往该节点的更短路径**。这种假设仅在没有负权边时才成立。因此，**不能将狄克斯特拉算法用于包含负权边的图**。\n",
    "\n",
    "在包含负权边的图中，要找出最短路径，可使用另一种算法——**贝尔曼-福德算法（Bellman-Fordalgorithm）**。本书不介绍这种算法，你可以在网上找到其详尽的说明。\n",
    "\n",
    "## 7.5 实现\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/69h3YwnzCNI1AmO.png)\n",
    "\n",
    "要编写解决这个问题的代码，需要三个散列表。\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/SdBOYWMT1FUKc7l.png)\n",
    "\n",
    "随着算法的进行，你将不断更新散列表costs和parents。首先，需要实现这个图，为此可像第6章那样使用一个散列表。\n",
    "\n",
    "但这里需要同时存储邻居和前往邻居的开销。例如，起点有两个邻居——A和B。使用另一个散列表表示权重："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = {}\n",
    "graph[\"start\"] = {}\n",
    "graph[\"start\"][\"a\"] = 6\n",
    "graph[\"start\"][\"b\"] = 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因此 graph[\"start\"] 是一个散列表。要获取起点的所有邻居，可像下面这样做。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dict_keys(['a', 'b'])\n"
     ]
    }
   ],
   "source": [
    "print(graph[\"start\"].keys())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "获取边的权重："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "print(graph[\"start\"][\"a\"])\n",
    "print(graph[\"start\"][\"b\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "添加其他节点及其邻居"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph[\"a\"] = {}\n",
    "graph[\"a\"][\"fin\"] = 1\n",
    "\n",
    "graph[\"b\"] = {}\n",
    "graph[\"b\"][\"a\"] = 3\n",
    "graph[\"b\"][\"fin\"] = 5\n",
    "\n",
    "graph[\"fin\"] = {} #终点没有任何邻居"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': {'fin': 1},\n",
       " 'b': {'a': 3, 'fin': 5},\n",
       " 'fin': {},\n",
       " 'start': {'a': 6, 'b': 2}}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**创建散列表来存储每个节点的开销**，节点的开销指的是从起点出发前往该节点需要多长时间。\n",
    "\n",
    "你知道的，从起点到节点B需要2分钟，从起点到节点A需要6分钟（但你可能会找到所需时间更短的路径）。你不知道到终点需要多长时间。对于还不知道的开销，你将其设置为无穷大。在Python中能够表示无穷大吗？你可以这样做："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "infinity = float(\"inf\")\n",
    "\n",
    "costs = {}\n",
    "costs[\"a\"] = 6\n",
    "costs[\"b\"] = 2\n",
    "costs[\"fin\"] = infinity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**存储父节点的散列表**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "parents = {}\n",
    "parents[\"a\"] = \"start\"\n",
    "parents[\"b\"] = \"start\"\n",
    "parents[\"fin\"] = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最后，你需要一个数组，用于记录处理过的节点，因为对于同一个节点，你不用处理多次。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "processed = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "准备工作做好了，下面来看看算法:\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/I8BFtcYuAoExC6S.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_lowest_cost_node(costs,processed):\n",
    "    lowest_cost = float(\"inf\")\n",
    "    lowest_cost_node = None\n",
    "    for node in costs:\n",
    "        cost = costs[node]\n",
    "        if cost < lowest_cost and node not in processed:\n",
    "            lowest_cost = cost\n",
    "            lowest_cost_node = node\n",
    "    return lowest_cost_node\n",
    "\n",
    "node = find_lowest_cost_node(costs,processed) #在未处理的节点中找出开销最小的节点\n",
    "while node is not None: #这个 while 循环在所有节点都被处理过后结束\n",
    "    cost = costs[node]\n",
    "    neighbors = graph[node]\n",
    "    for n in neighbors.keys(): #遍历当前节点的所有邻居\n",
    "        new_cost = cost + neighbors[n]\n",
    "        if costs[n] > new_cost: #如果经当前节点前往该邻居更近，\n",
    "            costs[n] = new_cost #就更新该邻居的开销\n",
    "            parents[n] = node #同时将该邻居的父节点设置为当前节点\n",
    "    processed.append(node) #将当前节点标记为处理过\n",
    "    node = find_lowest_cost_node(costs,processed) #找出接下来要处理的节点，并循环"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最短路径值与最短路径："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "costs[\"fin\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fin\n",
      "a\n",
      "b\n",
      "start\n"
     ]
    }
   ],
   "source": [
    "a = \"fin\"\n",
    "while a != \"start\":\n",
    "    print(a)\n",
    "    a = parents[a]\n",
    "print(\"start\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 'b', 'b': 'start', 'fin': 'a'}\n",
      "{'a': 5, 'b': 2, 'fin': 6}\n"
     ]
    }
   ],
   "source": [
    "print(parents)\n",
    "print(costs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 整合代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 构建图散列表graph，一共四个节点：start a b fin\n",
    "graph = {}\n",
    "graph[\"start\"] = {}\n",
    "graph[\"start\"][\"a\"] = 6\n",
    "graph[\"start\"][\"b\"] = 2\n",
    "graph[\"a\"] = {}\n",
    "graph[\"a\"][\"fin\"] = 1\n",
    "graph[\"b\"] = {}\n",
    "graph[\"b\"][\"a\"] = 3\n",
    "graph[\"b\"][\"fin\"] = 5\n",
    "graph[\"fin\"] = {} #终点没有任何邻居\n",
    "\n",
    "# 构建节点开销散列表costs\n",
    "infinity = float(\"inf\")\n",
    "costs = {}\n",
    "costs[\"a\"] = 6\n",
    "costs[\"b\"] = 2\n",
    "costs[\"fin\"] = infinity\n",
    "\n",
    "#构建父节点散列表parents\n",
    "parents = {}\n",
    "parents[\"a\"] = \"start\"\n",
    "parents[\"b\"] = \"start\"\n",
    "parents[\"fin\"] = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最短路径 6\n",
      "最短路径为：\n",
      "fin\n",
      "a\n",
      "b\n",
      "start\n"
     ]
    }
   ],
   "source": [
    "#在未处理的节点中找出开销最小的节点\n",
    "def find_lowest_cost_node(costs,processed):\n",
    "    lowest_cost = float(\"inf\")\n",
    "    lowest_cost_node = None\n",
    "    for node in costs:\n",
    "        cost = costs[node]\n",
    "        if cost < lowest_cost and node not in processed:\n",
    "            lowest_cost = cost\n",
    "            lowest_cost_node = node\n",
    "    return lowest_cost_node\n",
    "\n",
    "def dijkstra_algo(graph,costs,parents):\n",
    "    \n",
    "    #用于保存处理过的节点\n",
    "    processed = []\n",
    "    \n",
    "    node = find_lowest_cost_node(costs,processed) \n",
    "    while node is not None: #这个 while 循环在所有节点都被处理过后结束\n",
    "        cost = costs[node]\n",
    "        neighbors = graph[node]\n",
    "        for n in neighbors.keys(): #遍历当前节点的所有邻居\n",
    "            new_cost = cost + neighbors[n]\n",
    "            if costs[n] > new_cost: #如果经当前节点前往该邻居更近，\n",
    "                costs[n] = new_cost #就更新该邻居的开销\n",
    "                parents[n] = node #同时将该邻居的父节点设置为当前节点\n",
    "        processed.append(node) #将当前节点标记为处理过\n",
    "        node = find_lowest_cost_node(costs,processed) #找出接下来要处理的节点，并循环\n",
    "    return costs,parents\n",
    "\n",
    "# 输出最短路径值和路径\n",
    "def print_shortest_path(costs,parents,start_node,final_node):\n",
    "    print(\"最短路径：\",costs[final_node])\n",
    "    print(\"最短路径为：\")\n",
    "    curr_node = final_node\n",
    "    while curr_node != start_node:\n",
    "        print(curr_node)\n",
    "        curr_node = parents[curr_node]\n",
    "    print(start_node)\n",
    "\n",
    "costs,parents = dijkstra_algo(graph,costs,parents)\n",
    "print_shortest_path(costs,parents,'start','fin')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7.6 小结\n",
    "\n",
    "- 广度优先搜索用于在非加权图中查找最短路径。\n",
    "- 狄克斯特拉算法用于在加权图中查找最短路径。\n",
    "- 仅当权重为正时狄克斯特拉算法才管用。\n",
    "- 如果图中包含负权边，请使用贝尔曼-福德算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**练习**\n",
    "\n",
    "在下面的各个图中，从起点到终点的最短路径的总权重分别是多少？\n",
    "\n",
    "![](https://i.loli.net/2019/08/10/DawKcm1xYPek64N.png)\n",
    "\n",
    "**A题:** 记中间四个节点为a,b,c,d\n",
    "\n",
    "![](https://i.loli.net/2019/08/11/C9sBfWXPD4E8Sto.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = {}\n",
    "graph['start']  = {}\n",
    "graph['start']['a'] = 5\n",
    "graph['start']['b'] = 2\n",
    "graph['a'] = {}\n",
    "graph['a']['c'] = 4\n",
    "graph['a']['d'] = 2\n",
    "graph['b'] = {}\n",
    "graph['b']['a'] = 8\n",
    "graph['b']['d'] = 7\n",
    "graph['c'] = {}\n",
    "graph['c']['d'] = 6\n",
    "graph['c']['fin'] = 3\n",
    "graph['d'] = {}\n",
    "graph['d']['fin'] = 1\n",
    "graph['fin'] = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': {'c': 4, 'd': 2},\n",
       " 'b': {'a': 8, 'd': 7},\n",
       " 'c': {'d': 6, 'fin': 3},\n",
       " 'd': {'fin': 1},\n",
       " 'fin': {},\n",
       " 'start': {'a': 5, 'b': 2}}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "infinity = float(\"inf\")\n",
    "costs = {}\n",
    "costs['a'] = 5\n",
    "costs['b'] = 2\n",
    "costs['c'] = infinity\n",
    "costs['d'] = infinity\n",
    "costs['fin'] = infinity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "parents = {}\n",
    "parents['a'] = 'start'\n",
    "parents['b'] = 'start'\n",
    "parents['c'] = None\n",
    "parents['d'] = None\n",
    "parents['fin'] = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最短路径 8\n",
      "最短路径为：\n",
      "fin\n",
      "d\n",
      "a\n",
      "start\n"
     ]
    }
   ],
   "source": [
    "costs,parents = dijkstra_algo(graph,costs,parents)\n",
    "print_shortest_path(costs,parents,'start','fin')"
   ]
  }
 ],
 "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}