1 模型概览
1.1 学科分属
基本学科归属： 运筹学
背景知识： 邻接矩阵、贪心算法、广度优先搜索、动态规划、多目标规划
1.2 历史发展
Dijkstra算法是由荷兰计算机科学家Dijkstra于1959年提出的，因此又叫狄克斯特拉算法，是目前公认的求解无负权值最短路径的最好算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。Dijkstra算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
在一台新的叫 ARMAC 的计算机发布之前，Dijkstra 需要想出一个可以让不懂数学的媒体和公众理解的问题，以便向他们展示。有一天他和未婚妻在阿姆斯特丹购物，他们停下来在一家咖啡店的阳台上喝咖啡休息，他开始思考这个问题。他觉得可以让计算机演示如何计算荷兰两个城市间的最短路径，这样问题和答案都容易被人理解。于是他在 20 分钟内想出了高效计算最短路径的方法。Dijkstra 自己也没有想到这个 20 分钟的发明会成为他最著名的成就之一，并且会被以他的名字命名为 Dijkstra 算法。
Dijkstra 后来在采访中说，他的最短路径算法之所以能如此简洁，是因为当时在咖啡店里没有纸和笔，这强迫他在思考时避免复杂度，尽可能追求简单。在他的访谈和文章中，经常能发现一个主题，就是资源的匮乏往往最能激发创造性。
2 模型介绍
2.1 模型机理
Dijkstra算法适用于加权图的单源最短路径问题，其采用贪婪算法。
在 Dijkstra 算法中，首先需要保存一个顶点集 S。S 中的顶点是已经找到了最短路径的顶点。开始时，顶点集合 S 为空。这样，图中的顶点被分为两个部分，一部分属于顶点集 S，另一部分属于顶点集 V - S。在顶点集 S 中的顶点是已经确定了由源点到本顶点的最短路径的顶点。接下来，反复执行以下循环，直至顶点集 S 包含所有的顶点为止：在 V - S 中寻找路径最短的结点并把它加入 S；对于在顶点集 V - S 中的每个顶点，考察新加入顶点集 S 中的结点是否有边到达自己。如果存在,则检查这条路径是否比原来已知的路径要短。如果是，则更新源点到此结点的距离和路径；然后，从 S 中寻找一个路径最短的结点，从源点到这个结点已经不可能有更好的路径了，把它加入顶点集 S，那么S中的顶点数便增加了一个。按照这种方式，一直执行到 V 中所有的顶点都并入顶点集 S 为止。
演示见：
1、app”算法动画图解“
适用范围
可以用于有向图，但不能处理负权重
修复
Bellman‐Ford（贝尔曼‐福特）算法
贝尔曼‐福特算法不再将节点区分为是否已访问的状态，因为贝尔曼‐福特模型是利用循环来进行更新权重的，且每循环一次，贝尔曼福特算法都会更新所有的节点的信息。
贝尔曼‐福特算法不支持含有负权回路的图。
负权回路
如果存在一个环（从某个点出发又回到自己的路径），而且这个环上所有权值之和是负数，那这就是一个负权环，也叫负权回路。
存在负权回路的图是不能求两点间最短路的，因为只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。
含有负权重的无向图都是负权回路。
贝尔曼‐福特算法实际上处理的是具有负权重的有向图。（且该有向图也不能含有负权回路）
MATLAB代码
功能：返回图G中start节点到end节点的最短路径
输入参数：
（1）G ‐ 输入图（graph 对象 | digraph 对象）
（2）start 起始的节点
（3）end 目标的节点
（4）[,‘Method’,algorithm]是可选的参数，表示计算最短路径的算法。一般我们不用手动设置，默认使用的是“auto”, 具体可设置的参数见下一页课件。
输出参数：
（1）P – 最短路径经过的节点
（2）d – 最短距离
可选的算法：
