下载文档原格式
最短路问题的求解方法最短路问题是图论中的一个经典问题，它在很多实际应用中都有着重要的作用。
在现实生活中，我们经常需要求解最短路径，比如在地图导航、网络通信、交通运输等领域。
因此，研究最短路问题的求解方法具有重要的理论意义和实际应用价值。
在图论中，最短路问题的求解方法有很多种，其中比较经典的有Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法等。
这些算法各有特点，适用于不同的场景和要求。
下面我们就逐一介绍这些算法的原理和求解方法。
Dijkstra算法是一种用于求解单源最短路径的算法，它采用贪心策略，每次找到当前距离最短的节点进行松弛操作，直到所有节点都被遍历。
Dijkstra算法的时间复杂度为O(V^2)，其中V为节点的个数。
这种算法适用于边权值为正的图，可以求解从单个源点到其他所有点的最短路径。
Bellman-Ford算法是一种用于求解单源最短路径的算法，它可以处理边权值为负的图，并且可以检测负权回路。
Bellman-Ford算法的时间复杂度为O(VE)，其中V为节点的个数，E为边的个数。
这种算法适用于一般情况下的最短路径求解，但是由于其时间复杂度较高，不适用于大规模图的求解。
Floyd-Warshall算法是一种用于求解所有点对最短路径的算法，它可以处理边权值为正或负的图，但是不能检测负权回路。
Floyd-Warshall算法的时间复杂度为O(V^3)，其中V为节点的个数。
这种算法适用于求解图中所有点对之间的最短路径，可以同时求解多个源点到多个目标点的最短路径。
除了上述几种经典的最短路求解算法外，还有一些其他的方法，比如A算法、SPFA算法等。
这些算法在不同的场景和要求下有着各自的优势和局限性，需要根据具体情况进行选择和应用。
在实际应用中，最短路问题的求解方法需要根据具体的场景和要求进行选择，需要综合考虑图的规模、边权值的情况、时间效率等因素。
同时，对于大规模图的求解，还需要考虑算法的优化和并行化问题，以提高求解效率。
Dijkstra算法是一种用于求解最短路径问题的常用算法，适用于带权有向图。
以下是Dijkstra 算法的求解过程：
初始化：将起始节点标记为当前节点，并将起始节点到所有其他节点的距离初始化为无穷大（表示暂时未知）。
将起始节点到自身的距离设置为0，表示起始节点到自身的最短路径长度为0。
遍历所有节点：
选择当前节点的邻接节点中，距离最小且尚未被访问的节点。
更新该邻接节点的最短路径长度。
如果经过当前节点到达该邻接节点的路径比当前记录的最短路径更短，则更新最短路径长度。
继续遍历未访问的节点，直到所有节点都被访问。
重复步骤3，直到所有节点都被访问或者没有可达节点。
最终得到起始节点到其他节点的最短路径长度。
在Dijkstra算法的求解过程中，使用一个距离表（distances）来记录起始节点到各个节点的当前最短路径长度，一个访问表（visited）来标记节点是否已被访问。
同时，使用优先队列（例如最小堆）来选取下一个距离最小且尚未被访问的节点。
具体的实现可以使用迭代或递归的方式，根据实际情况来选择合适的数据结构和算法实现。
在实际编程中，可能还需要考虑处理边的权重、处理节点的邻接关系和路径记录等细节。
Dijkstra算法要求图中的边权重非负，且无法处理负权边的情况。
对于含有负权边的图，可以考虑使用其他算法，如Bellman-Ford算法或SPFA（Shortest Path Faster Algorithm）等。
dijkstra 最短路优化算法
Dijkstra最短路优化算法是一种用于解决单源最短路径问题的
算法，它采用贪心的思想逐步找到从起点到所有其他节点的最短路径。
算法步骤如下：
1. 初始化距离数组dist[]，用于记录从起点到每个顶点的最短
距离。
将起点距离设为0，其他顶点的距离设为无穷大。
2. 创建一个优先队列（最小堆）Q，用于存储待选的顶点。
将
起点加入到Q中。
3. 当Q非空时，重复以下步骤：
- 从Q中取出当前距离最小的顶点u。
- 遍历u的所有邻居节点v，并计算起点到v的距离new_dist。
如果new_dist小于dist[v]，则更新dist[v]。
- 将v加入到Q中。
4. 重复步骤3，直到Q为空。
该算法的优化主要包括：
1. 使用最小堆可以快速获取当前距离最小的顶点。
2. 使用一个visited数组记录已经访问过的顶点，避免重复计算。
3. 使用优先队列存储待选的顶点，可以按照距离大小自动排序，减少不必要的遍历。
Dijkstra算法的时间复杂度为O((V+E)logV)，其中V是顶点数，E是边数。
最短路dijkstra算法详解最短路问题是图论中的一个经典问题，其目标是在给定图中找到从一个起点到其他所有节点的最短路径。
Dijkstra算法是解决最短路问题的一种常用算法，本文将详细介绍Dijkstra算法的原理、实现以及时间复杂度等相关内容。
一、Dijkstra算法的原理Dijkstra算法是一种贪心算法，其基本思想是从起点开始，逐步扩展到其他节点。
具体而言，Dijkstra算法通过维护一个集合S来记录已经找到了最短路径的节点，以及一个数组dist来记录每个节点到起点的距离。
初始时，S集合为空，dist数组中除了起点外所有节点都被初始化为无穷大。
接下来，重复以下步骤直到所有节点都被加入S集合：1. 从dist数组中选择距离起点最近的未加入S集合的节点u；2. 将u加入S集合；3. 更新与u相邻的未加入S集合的节点v的距离：如果从起点出发经过u可以得到更短的路径，则更新v对应位置上dist数组中存储的值。
重复以上步骤直至所有节点都被加入S集合，并且dist数组中存储了每个节点到起点的最短距离。
最后，根据dist数组中存储的信息可以得到起点到任意节点的最短路径。
二、Dijkstra算法的实现在实现Dijkstra算法时，需要使用一个优先队列来维护未加入S集合的节点，并且每次从队列中选择距离起点最近的节点。
由于C++标准库中没有提供优先队列，因此需要手动实现或者使用第三方库。
以下是一个基于STL堆实现的Dijkstra算法代码示例：```c++#include <iostream>#include <vector>#include <queue>using namespace std;const int INF = 0x3f3f3f3f;vector<pair<int, int>> adj[10001];int dist[10001];void dijkstra(int start) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.push(make_pair(0, start));dist[start] = 0;while (!pq.empty()) {int u = pq.top().second;pq.pop();for (auto v : adj[u]) {if (dist[u] + v.second < dist[v.first]) {dist[v.first] = dist[u] + v.second;pq.push(make_pair(dist[v.first], v.first));}}}}int main() {int n, m, start;cin >> n >> m >> start;for (int i = 1; i <= n; i++) {dist[i] = INF;}for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;adj[u].push_back(make_pair(v, w));}dijkstra(start);for (int i = 1; i <= n; i++) {if (dist[i] == INF) {cout << "INF" << endl;} else {cout << dist[i] << endl;}}return 0;}```以上代码中，adj数组用于存储图的邻接表，dist数组用于存储每个节点到起点的最短距离。
最短路的算法--Dijkstra算法在图G中，给定s和t两个顶点。
从s到t可以有多条路径，从这多条路中找出长度最的最短路。
设每条弧的长度均为非负值。
小的路，这样的路称为从s到t的最短路。
设每条弧的长度均为非负值。
下面的算法是由狄杰斯特拉（Dijkstra,1959）提出的，其想法是：设已知图中最接近于顶点s的m个顶点以及从顶点s到这些顶点中每一个顶点的最短路（从s到其本身的最短路是零路，即没有弧的路，其长度为0）。
对顶点s和这m个顶点着色。
然后，最接近于s的个顶点可如下求之：第m+1个顶点可如下求之：对于每一个未着色的顶点y，考虑所有已着色顶点x，把弧（x，y）接在从s到x的最短路后面，这样就得到从s到y的m条不同路。
从这m条路中选出最短的路，它就是从s 到y的最短路。
相应的y点就是最接近于s的第m+1个顶点。
因为所有弧的长度都是非负值，所以从s到最接近于s的第m+1个顶点的最短路必然只使用已着色的顶点作为中间顶点。
的最短路为止。
从m=0开始，将这个过程重复进行下去，直至求得从s到t的最短路为止。
算法：狄杰斯特拉最短路算法第1步开始，所有弧和顶点都未着色。
对每个顶点x指定一个数d(x)，d(x)表示从s到x 的最短路的长度（中间顶点均已着色）。
开始时，令d(s)=0，d(x)=∞（对所有x≠s）。
y表示已着色的最后一个顶点。
对始点s着色，令y=s。
如下：第2步对于每个未着色顶点x，重新定义d(x)如下：d(x)=min{ d(x)，d(y)+a(y，x)} 公式对于所有未着色顶点x，如d(x)=∞，则算法终止。
因为此时从s到任一未着色的顶点都没有路。
否则，对具有d(x)最小值的未着色顶点x进行着色。
同时把弧(y，x)着色（指向顶点x的弧只有一条被着色）。
令y=x。
第3步如果顶点t已着色，则算法终止。
这时已找到一条从s到t的最短路。
如果t未着色，则转第2步。
步。
注意：已着色的弧不能构成一个圈，而是构成一个根在s的树形图，此树形图称为最短路树形图。
最短路的dijkstra算法基本过程
最短路的Dijkstra算法基本过程
Dijkstra算法是用来解决最短路径问题的一种算法，它是由荷兰计算机科学家Edsger W. Dijkstra在1959年发明的，是目前最常用的最短路径算法。
它是以贪心策略为基础的，主要是利用局部最优求全局最优。
基本过程如下：
1. 从起点出发，设计出一个距离变量dist[],初始值为无穷大。
2. 将dist[起点]设置为0。
3. 找出当前最近的顶点u，计算出从起点到u的中间点v的最短路径，并更新dist[v]的值，即dist[v] = min(dist[v], dist[u] + w(u,v))，其中w(u,v)表示从u到v的边的权重。
4. 重复步骤3，直到所有的顶点都被处理完为止。
5. 返回dist[]，表示从起点到其他所有点的最短路径。
迪科斯彻算法总结最短路之~迪科斯彻算法迪科斯彻算法是由荷兰计算机科学家艾滋郝尔·戴克斯拉提出的。
本算法使⽤⼴度优先搜索解决⾮负权有向图的单源最短路径问题。
算法终于得到⼀个最短路径树。
此算法经常使⽤于路由算法或者作为其它图算法⼀个⼦模块。
本算法是⽤来找⼀个点到其它全部点之间的最短路径。
此算法中变量的使⽤：map[][]⼆维数组记录两点之间的权值，⽐如map[i][j]存放i点到j点的权值。
当作为有向图时，给出i,j须要存放的仅仅有⼀个map[][],但普通情况下都是⽤⽆向图，需存两个map[][],即map[i][j]=map[j][i]=权值。
dis[]⼀维数组存放各点到起点的最短距离。
mark[]⼀维数组标记使⽤过的点。
单源最短路：Ⅰ、从⼀个点出发到其它全部点的最短路径的长度Ⅱ、基本操作：松弛操作。
Ⅲ、dis[j] > dis[vir] + map[vir][j]这种边(vir,j)成为紧的，能够对它进⾏松弛操作。
对全部点进⾏松弛操作的代码可參考：for(int j = 1; j <= n; j++){if(dis[j] > dis[vir] + map[vir][j] && !mark[j])dis[j] = dis[vir] + map[vir][j];}Ⅳ、最開始给每个点⼀个⾮常⼤的dis值，从dis[s] = 0；開始，不断给能够松弛的点进⾏松弛操作。
直⾄求出全部点的最短路径。
本算法要求图中不存在负权边。
可证明：具有最⼩的dis[i]的点没有增加最短路时，此后的点⽆法松弛。
所以每次均要寻找近期的点进⾏松弛操作。
详细请參考代码：#include<stdio.h>#define INF 0x3f3f3f3f //定义⼀个较⼤的值。
⽤来初始化int map[1010][1010]; //存放两点间的权值int dis[1010]; //存放各点距起点的距离int mark[1010]; //标记使⽤过的点int n,m; //有n个点，编号为1~n,有m组数据void dijkstra(int s){int vir,min;for(int i=1;i<=n;i++) //初始化标记数组和距离数组{mark[i]=0; //0表⽰未使⽤此点dis[i]=INF;}dis[s]=0;for(int i=1;i<=n;i++){min=INF;for(int j=1;j<=n;j++) //查找权值最⼩的点{if(!mark[j]&&dis[j]<min){min=dis[j];vir=j;}}if(min==INF) break; //若没查找到或已查找完成。
迪科斯彻算法迪科斯彻算法（Dijkstra）是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger Wybe Dijkstra）发明的。
算法解决的是有向图中单个源点到其他顶点的最短路径问题。
举例来说，如果图中的顶点表⽰城市，⽽边上的权重表⽰著城市间开车⾏经的距离，迪科斯彻算法可以⽤来找到两个城市之间的最短路径。
迪科斯彻算法的输⼊包含了⼀个有权重的有向图 G，以及G中的⼀个来源顶点 S。
我们以 V 表⽰ G 中所有顶点的集合。
每⼀个图中的边，都是两个顶点所形成的有序元素对。
(u, v) 表⽰从顶点u 到 v 有路径相连。
我们以 E 所有边的集合，⽽边的权重则由权重函数 w: E → [0, ∞] 定义。
因此，w(u, v) 就是从顶点 u 到顶点 v 的⾮负花费值（cost）。
边的花费可以想像成两个顶点之间的距离。
任两点间路径的花费值，就是该路径上所有边的花费值总和。
已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低花费路径(例如，最短路径)。
这个算法也可以在⼀个图中，找到从⼀个顶点 s 到任何其他顶点的最短路径。
算法描述这个算法是通过为每个顶点 v 保留⽬前为⽌所找到的从s到v的最短路径来⼯作的。
初始时，原点 s 的路径长度值被赋为 0 （d[s] = 0），同时把所有其他顶点的路径长度设为⽆穷⼤，即表⽰我们不知道任何通向这些顶点的路径（对于 V 中所有顶点 v 除 s 外d[v] = ∞）。
当算法结束时，d[v] 中储存的便是从 s 到 v 的最短路径，或者如果路径不存在的话是⽆穷⼤。
Dijkstra 算法的基础操作是边的拓展：如果存在⼀条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展⼀条从 s 到 u 的路径。
这条路径的长度是 d[u] + w(u, v)。
如果这个值⽐⽬前已知的 d[v] 的值要⼩，我们可以⽤新值来替代当前 d[v] 中的值。
最短路问题之Dijkstra算法题⽬： 在上⼀篇博客的基础上，这是另⼀种⽅法求最短路径的问题。
Dijkstra（迪杰斯特拉）算法：找到最短距离已经确定的点，从它出发更新相邻顶点的最短距离。
此后不再关⼼前⾯已经确定的“最短距离已经确定的点”。
Dijkstra算法采⽤的是⼀种贪⼼的策略，声明⼀个数组dis来保存源点到各个顶点的最短距离和⼀个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。
若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为⽆穷⼤。
初始时，集合T只有顶点s。
然后，从dis数组选择最⼩值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加⼊到T中，OK，此时完成⼀个顶点，然后，我们需要看看新加⼊的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否⽐源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
然后，⼜从dis中找出最⼩值，重复上述动作，直到T中包含了图的所有顶点。
代码：1import java.util.HashSet;2import java.util.Set;34public class图的最短路问题_Dijkstra {5public static void main(String[] args) {6int s = 1;7int[] shortestPath = shortestPath(s);89for (int i = 0; i < prev.length; i++) {10 System.out.println((char) ('A' + s) + "到" + (char) ('A' + i) + "的路径");11 System.out.print((char) ('A' + i) + "<-");12int j = prev[i];13while (j != s) {14 System.out.print((char) ('A' + j) + "<-");15 j = prev[j];16 }17 System.out.print((char) ('A' + j));18 System.out.println(":" + shortestPath[i]);19 }20 }2122static int[] prev;2324/**25 * 求起点到各顶点的最短距离26 *27 * @param s 起点28 * @return29*/30private static int[] shortestPath(int s) {31// 顶点个数32int n = graph.length;33// 记录每个点的前驱34 prev = new int[n];35// ⼀定要初始化，源点的前驱是⾃⾝36 prev[s] = s;37// 记录s到各顶点的最短距离38int[] d = new int[n];39 d[s] = 0;// ⾃⼰到⾃⼰的距离为040// 记录已经找到最短距离的顶点41 Set<Integer> T = new HashSet<>();42 T.add(s);4344/*-第⼀步：直接可达的顶点，⽤距离来初始化d,d[s]=0，可直达的把距离记录下来作为待定值-*/45for (int i = 0; i < n; i++) {46if (i != s && graph[s][i] == 0)47 d[i] = Integer.MAX_VALUE;// 不可直达的顶点，先以最⼤整数作为待定值48if (i != s && graph[s][i] > 0) {49 d[i] = graph[s][i]; // 可直达的顶点，以直达距离作为待定值50 prev[i] = s; // 可直达的顶点，其前驱是源点51 }52 }53// Util.print(d);5455while (T.size() < n) {56/*-第⼆步：从待定的距离表中找到最⼩值，这个值可以作为确定值，为什么？-*/57int min = minIndex(d, T);58 T.add(min);59if (T.size() == n)60break;61/*-第三步，看这个新确定的顶点的出度，看看从源点出发是经过这个顶点到其邻居近还是直达更近,如果更近就要更新-*/ 62// 扫描index的邻居63for (int neighbor = 0; neighbor < n; neighbor++) {64int cost = graph[min][neighbor];65// 更新66if (cost > 0 && d[neighbor] > d[min] + cost) {67 d[neighbor] = d[min] + cost;68 prev[neighbor] = min; // 更新最短路后，要更新i这个点的前驱69 }70 }71 }72return d;73 }7475/**76 * 从未确定的点⾥⾯找⼀个最⼩的77 *78 * @param d79 * @param t 已确定了最短距离的顶点集80 * @return81*/82private static int minIndex(int[] d, Set<Integer> t) {83int index = -1;84int min = Integer.MAX_VALUE;85for (int i = 0; i < d.length; i++) {86if (!t.contains(i) && d[i] < min) {87 min = d[i];88 index = i;89 }90 }91return index;92 }9394static int[][] graph = {95 { 0, 2, 5, 0, 0, 0, 0 },96 { 2, 0, 4, 6, 10, 0, 0 },97 { 5, 4, 0, 2, 0, 0, 0 },98 { 0, 6, 2, 0, 0, 1, 0 },99 { 0, 10, 0, 0, 0, 3, 5 },100 { 0, 0, 0, 1, 3, 0, 9 },101 { 0, 0, 0, 0, 5, 9, 0 }102 };103 }结果： 例题，POJ-1502。
最短路问题的求解方法最短路问题是图论中的一个经典问题，它在现实生活中有着广泛的应用。
在很多实际情况下，我们需要找到两个节点之间的最短路径，以便在最短时间内到达目的地或者以最小的成本进行运输。
因此，求解最短路问题具有重要的意义。
在图论中，最短路问题可以分为单源最短路和多源最短路两种情况。
单源最短路指的是从图中的一个固定节点出发，到达其他所有节点的最短路径；而多源最短路则是求解图中任意两个节点之间的最短路径。
针对这两种情况，我们可以采用不同的算法来求解最短路问题。
其中，最著名的算法包括Dijkstra算法和Floyd-Warshall算法。
Dijkstra算法适用于单源最短路问题，它采用贪心策略，逐步确定从源节点到其他节点的最短路径。
而Floyd-Warshall算法则适用于多源最短路问题，它通过动态规划的方式，计算图中任意两个节点之间的最短路径。
除了这两种经典算法外，还有一些其他方法可以用来求解最短路问题，比如Bellman-Ford算法和SPFA算法。
这些算法各有特点，适用于不同的场景，可以根据具体情况选择合适的算法来解决最短路问题。
在实际应用中，最短路问题常常涉及到大规模的图和复杂的网络结构，因此算法的效率和性能也是非常重要的考量因素。
为了提高算法的求解速度，可以采用一些优化手段，比如使用堆优化的Dijkstra算法、矩阵快速幂优化的Floyd-Warshall算法等。
总之，最短路问题是图论中的一个重要问题，它在实际生活中有着广泛的应用。
通过合理选择算法和优化方法，我们可以高效地求解最短路问题，为实际应用提供有力的支持。
希望本文能够为读者对最短路问题的求解方法有所启发，也希望在未来的实际应用中能够发挥一定的作用。
迪克斯特拉（Dijkstra）算法两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。
以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。
对G 的每一边e ，赋以一个实数)(e w —直通铁路的长度，称为e 的权，得到赋权图G 。
G 的子图的权是指子图的各边的权和。
问题就是求赋权图G 中指定的两个顶点00,v u 间的具最小权的轨。
这条轨叫做00,v u 间的最短路，它的权叫做00,v u 间的距离，亦记作),(00v u d 。
求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。
为避免重复并保留每一步的计算信息，采用了标号算法。
下面是该算法。
(i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。
(ii) 对每个i S v ∈（i i S V S \=），用)}()(),({min uv w u l v l iS u +∈ 代替)(v l 。
计算)}({min v l iS v ∈，把达到这个最小值的一个顶点记为1+i u ，令}{11++=i i i u S S 。
(iii). 若1||-=V i ，停止；若1||-<="" 标号，v="" 的最后一次的标号)(v="" 的距离由v="" 算法结束时，从0u="" 给出。
在v="" 进入i="" ，用1+i="" ，转(ii)。
="">的标号)(v l 叫P 标号。
算法就是不断修改各项点的T 标号，直至获得P 标号。
最短通路——迪克斯特拉算法迪克斯特拉算法初探——图解算法迪克斯特拉算法的⼤致思想是这样：求出起始顶点到各个后继顶点的最短通路，直到所求顶点为⽌。
由于直接从抽象的代码分析⽐较复杂（笔者很菜零零碎碎花了好⼏天才搞懂），我们可从实际的例⼦来感受该算法的思想，这样也符合由⼀般到抽象的认知过程（突然哲学）⾸先来看⼀个直观的例⼦吧（看图说话）标号是核⼼（L(v)实际上就是点v到a的某条通路的长度（为什么不说是最短路长度呢 ? 这个我后⾯会提到））1.⾸先初始化标记即：把a标号为0；其余点标号为⽆穷；2.再定义⼀个空集S。
step 1:看看图中发⽣了什么变化？1.我们将标号最⼩的a（L（a）=0）纳⼊集合S中(图中⽤圈圈出）；即 S={a}2.更新所有不属于S的顶点的标记具体就是对不在集合S中的点v，其标号为min{ L(a)+w(a,v), L(v) } L(b)=4; L(c)=2;显然我们只能更新那些与a相邻的元素的标记。
# a-v之间如果不连通则w(a,v)=∞step 2：这下上次的标号就派上⽤场了呢：我们把不在S中的顶点标号最⼩的顶点纳⼊到集合S中，即 c 得到 S={a,c};对所有不属于S的顶点v，更新它们的标号具体做法 L(v)= min{ L(c)+w(c,v), L(v) } L( b)=3;L(d)=10;L(e)=12;注意：已经更新过的元素也可能会再次改变~b就是如此标号再次改变说明存在更短的路径step 3:这次L(b)为最⼩标号所以把b添加到集合S中 S={a,c,b} # ⾄此 b加⼊到集合S中，所求的标号L（b）才是最短路的长度！更新标号（以新加⼊S的顶点b为基准）： L(v)= min{ L(b)+w(b,v), L(v) } L(d)=8;⼤家发现没有，这个算法的简化之处在于，寻找新的点不需要求S中所有点和不在S中所有点的标号，也就是说，只需要更新所有与新加⼊点相邻的点的标号，这⼀点需要慢慢体会，我就是卡在这⼉出不去！step 4:S={a,c,b,d} ; L(e)=10 L(f)=14step 5:S={a,c,b,d,e}; L(f)=13;step 6 :S={a,c,b,d,e}; L(f)=13 ⾄此该算法结束下⾯上点理论知识应该就可以接受了吧：迪克斯特拉算法如下进⾏：求出a到第⼀个顶点的最短通路的长度，从a到第⼆个顶点的最短通路的长度，依次类推，直到求除从a到z的最短通路的长度为⽌。
