拉普拉斯变换解线性微分方程（第六章图-第四节4）

最短路径shortestpath)：主要有以下两类最短路径问题

单源最短路径问题：一个顶点到其他顶点的最短路径

• 迪杰斯特拉算法(dijkstra)（带权图、无权图）-本节讲解
• BFS算法(无权图)–点击跳转

各顶点间最短路径问题：也就是每一对顶点间最短路径

• 弗洛伊德算法-点击跳转

最短路径在通信、交通等领域有重要应用

BFS算法只适用于无权图单源最短路径，对于有权图来说则不适用，比如下面“G港”到“R城”相对于用BFS算法找出的10来说还有一条更短的7

迪杰斯特拉算法：该算法和普利姆算法有些地方比较相似。该算法在剩余顶点中选出一个顶点，通往这个顶点的路径在通往所有顶点的路径中长度是最短的

迪杰斯特拉(dijkstra)算法不便于用语言完整描述，可以跟随下面的例子体会一下这个过程。其中会涉及三个数组

• dist[]：数组存储了当前起点到其余顶点最短路径的长度path[]：数组存储了起点到其余顶点的最短路径（通过查询该数组，可获得路径信息）final[]：数组中标记为1表示被选入最短路径

开始时，各数组初始化如下，其中v_{0}v0有到v_{1}v1的直接路径10、v_{0}v0​有到v_{4}v4​的直接路径5

• 因此path[1]=0，表示v_{0}v0​有到v_{1}v1​直接路径，其路径长度为dist[1]=10
• 因此path[4]=0，表示v_{0}v0​有到v_{4}v4​直接路径，其路径长度为dist[4]=5
• final[0]=true表示此时v_{0}v0​已经被选入最短路径了
• 由于目前v_{0}v0​到v_{2}v2​没有路径，因此dist[2]=\infin∞

接着，循环遍历所有顶点，找到还没有确定的最短路径、且dist最小的顶点v_{i}vi​，然后final[ii]=true

• 因此选择v_{4}v4​

在没有加入v_{4}v4​时，那么v_{0}v0​由于没有路径所以无法到达其中某些顶点，但是当v_{4}v4​加入之后情况有所改变，比如之前v_{0}v0​到v_{3}v3​是没有路径的，但是v_{4}v4​加入后，就有一个路径:v_{0}v0​->v_{4}v4​->v_{3}v3​

所以我们需要对比，若final值为false，更新对应的dist和path信息

• 对于v_{1}v1​：之前v_{0}v0​->v_{1}v1​为10，但是现在:v_{0}v0​->v_{4}v4​->v_{1}v1​路径之和为8，这是一条更短的路径，因此将dist[1]改为8，将path[1]改为4
• 对于v_{2}v2​：之前v_{0}v0​->v_{2}v2​为\infin∞，但是现在:v_{0}v0​->v_{4}v4​->v_{2}v2​路径之和为14，这是一条更短的路径，因此将dist[2]改为14，将path[2]改为4
• 对于v_{3}v3​：之前v_{0}v0​->v_{3}v3​为\infin∞，但是现在:v_{0}v0​->v_{4}v4​->v_{3}v3​路径之和为7，这是一条更短的路径，因此将dist[3]改为7，将path[3]改为4

上面结束了第一轮，总的来说两个步骤：

• 先在dist数组中找到一个最小的值，通往这个顶点的路径在通往其它顶点的路径中长度是最短的。换句话说如果你不能保证它是最小的，那就别提后面的了
• 接着由于该顶点的假如，使得前后情况有所变化，之前A到C没有路径，但是B加入之后，存在了一个路径A->B->C，所以我们要判断刚并入路径中的顶点是否会产生一些潜在的路径

第2轮

第3轮

第4轮，算法结束

王道视频课并没有介绍迪杰斯特拉(dijkstra)算法的代码实现，但是我认为了解其代码是十分有必要的。上述描述过程看完之后大家可能有这样的感觉就是：“也就那样嘛”，但这只是纸上谈兵

总的来说迪杰斯特拉算法和普利姆算法其实还是挺相似的。普利姆算法第一个小for循环是在找权值最小的边并纳入其中，迪杰斯特拉算法第一个小for循环也是在剩余顶点中选出一个顶点，通往这个顶点的路径在通往所有顶点的路径中长度是最短的。普利姆算法第二个小for循环是在更新lowcost数组，是指如果剩余的结点距离树的距离小于之前状况就更新，而迪杰斯特拉算法第二个for循环用于判断刚并入路径中的顶点的加入导致是否会出现通往其余顶点更短的路径（他在判断时，是以新加入的那个结点为起点从未被并入的结点中逐个比较

//带权图 typedef struct { int no; char info; }VertexType; typedef struct { float edges[maxSize][maxSize]; int n, e; VertexType vex[maxSize]; }MGraph; void Dijkstra(MGraph g, int v, int dist[], int path[]) /* dist[]数组存储了当前起点到其余顶点最短路径的长度 path[]数组存储了起点到其余顶点的最短路径（通过查询该数组，可获得路径信息） final[]数组中标记为1表示被选入最短路径 */ { int final[maxSize];//初始化final数组 int min, i, h, u; for (i = 0; i < g.n; i) { dist[i] = g.edges[v][i];//初始化dist数组，根据edges数组的信息，录入根结点到其余结点距离信息 final[i] = 0;//开始时所有结点均为被并入，故设为0 if (g.edges[v][i] < INF) /* 举例 如果path[0][3]不是无穷大(置于无穷大会大于这个很大的数) 那么path[3]=0，表示3这个节点之前是0，0-3是一个最短路径 */ path[i] = v; else path[i] = -1;//如果path[3]=-1，表示之前没有元素 } final[v] = 1;//根节点被并入 path[v] = -1;//根节点前没有结点 ///////////////迪杰斯特拉算法核心////////////// for (i = 0; i < g.n-1; i) { min = INF; for (int j = 0; j < g.n; j) /* 此for循环每次从剩余结点中选出一个一个结点，通过往这个 顶点的路径在通往所有剩余顶点的路径中是最短的 */ { if (final[j] == 0 && dist[j] < min) { u = j; min = dist[j]; } } final[u] = 1; for (int j = 0; j < g.n; j) /* 此for循环以刚并入的结点作为中间点，对所有通往剩余顶点的路径进行监测 */ { if (final[j] == 0 && dist[u] g.edges[u][j] < dist[j]) { /* 如果顶点u的加入会出现通往顶点j的更短的路径，那么就更新信息 */ dist[j] = dist[u] g.edges[u][j]; path[j] = u; } } } }

为了使大家能够更好地掌握这个算法，我截取了天勤视频课中关于这一部分的代码视频演示，希望大家可以跟随视频演示走一遍这个代码的流程（代码和天勤视频课一致）

Dijkstra算法代码流程图演示

考研数据结构中不太可能让你写迪杰斯特拉(dijkstra)算法的代码，如果真要考察，最有可能的形式就是给出一个图，让你描述迪杰斯特拉(dijkstra)算法求解最小生成树的过程

而这个算法又不太好用语言描述（可以说是越写越乱），所以我推荐的方法是采用表格法，思路不乱而且特别容易描述

如下

表格如下