第十一章 最短路问题

最短路问题的求解方法最短路问题是图论中的一个经典问题，它在很多实际应用中都有着重要的作用。

在现实生活中，我们经常需要求解最短路径，比如在地图导航、网络通信、交通运输等领域。

因此，研究最短路问题的求解方法具有重要的理论意义和实际应用价值。

在图论中，最短路问题的求解方法有很多种，其中比较经典的有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算法等。

这些算法在不同的场景和要求下有着各自的优势和局限性，需要根据具体情况进行选择和应用。

在实际应用中，最短路问题的求解方法需要根据具体的场景和要求进行选择，需要综合考虑图的规模、边权值的情况、时间效率等因素。

同时，对于大规模图的求解，还需要考虑算法的优化和并行化问题，以提高求解效率。

最短路问题基本内容：（1）问题的提法——寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数最小的通路。

（注意：在有向图中，通路——开的初等链中所有的弧应是首尾相连的。

）（2）应用背景——管道铺设、线路安排、厂区布局、设备更新等。

D氏标号法（Dijkstra）（1）求解思路——从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。

（3）选用符号的意义：①P 标号（Permanent固定/永久性标号），从始点到该标号点的最短路权。

1、一辆送货车从配送中心所在地V1 给V6，V7 两地客户实现共同配送。

已知车辆自身成本消耗0.2 元/ 公里。

各站点间的距离（单位：公里）数如下图所示。

在V6，V7两地的线路间有一收费站，每次每台车辆通过均收费15 元。

问题：（1）用标号法求出送货车的最优送货路线（2）此次送货,车辆总的花费是多少解：把收费站的收费折算成路线后，如下图：用用标号法解出各站点距V1的最短路径用标号法解出最短路线：V1－V2－V4－V5－V6－V7按上述路线的走法花费最少，TC=95×0.2＋15=34 元若避开收费站走：V1－V2－V4－V5－V6－V5－V7TC=（85＋20＋45）×0.2＝30 元因此，最优送货路线：V1－V2－V4－V5－V6－V5－V7；此次送货，车辆总的花费是30 元。

2、下图为某地区的交通运输道路示意图。

其中V1为配送中心位置，V8为要货客户位置，现V8客户向配送中心提出了4吨订货要求，并且要越快越好。

配送中心物流计划人员已做出了用一台4吨东风卡车配送的计划安排。

但要以最快的速度将货物送达，就必须确定最短的配送路线，而该计划人员不知如何确定。

（1）请您帮该物流计划人员优化出最佳的送货路线？（2）已知车辆的平均行驶速度为50公里/小时，如早晨8：00发车，货物什么时间可以送达客户？解：用T 标号法求解得最短路线为：V1－Ｖ２－Ｖ３－Ｖ６－Ｖ７－Ｖ８。

实验名称：第十一章最短路问题一、实验内容与要求掌握Dijkstra算法和Floyd算法，并运用这两种算法求一些最短路径的问题。

二、实验软件MATLAB7.0三、实验内容1、在一个城市交通系统中取出一段如图所示，其入口为顶点v1，出口为顶点v8，每条弧段旁的数字表示通过该路段所需时间，每次转弯需要附加时间为3，求v1到v8的最短时间路径。

63V4 2 V7 4 V8程序：function y=bijiaodaxiao(f1,f2,f3,f4)v12=1;v23=3;v24=2;v35=1;v47=2;v57=2;v56=6;v68=3;v78=4;turn=3; f1=v12+v23+v35+v56+turn+v68;f2=v12+v23+v35+turn+v57+turn+v78;f3=v12+turn+v24+turn+v47+v78;f4=v12+turn+v24+v47+turn+v57+turn+v56+turn+v68; min=f1;if f2<minmin=f2;endif f3<minmin=f3;endif f4<minmin=f4;endminf1f2f3f4实验结果：v1到v8的最短时间路径为15，路径为1-2-4-7-8.2、求如图所示中每一结点到其他结点的最短路。

V110 V3V59 V6function[D,R]=floyd(a)n=size(a,1);D=afor i=1:nfor j=1:nR(i,j)=j;endendRfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendkDRend程序：>> a=[0 3 10 inf inf inf inf inf;3 0 inf 5 inf inf inf inf;10 inf 0 6 inf inf inf inf;inf 5 6 0 4 inf 10 inf ;inf inf inf 4 0 9 5 inf ;inf inf inf inf 9 0 3 4;inf inf inf 10 5 3 0 6;inf inf inf inf inf 4 6 0;];[D,R]=floyd(a)实验结果：D =0 3 10 Inf Inf Inf Inf Inf3 0 Inf 5 Inf Inf Inf Inf10 Inf 0 6 Inf Inf Inf InfInf 5 6 0 4 Inf 10 InfInf Inf Inf 4 0 9 5 InfInf Inf Inf Inf 9 0 3 4Inf Inf Inf 10 5 3 0 6Inf Inf Inf Inf Inf 4 6 0R =1 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8k =1D =0 3 10 Inf Inf Inf Inf Inf3 0 13 5 Inf Inf Inf Inf10 13 0 6 Inf Inf Inf InfInf 5 6 0 4 Inf 10 InfInf Inf Inf 4 0 9 5 InfInf Inf Inf Inf 9 0 3 4Inf Inf Inf 10 5 3 0 6Inf Inf Inf Inf Inf 4 6 0R =1 2 3 4 5 6 7 81 2 1 4 5 6 7 81 1 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8 k =2D =0 3 10 8 Inf Inf Inf Inf3 0 13 5 Inf Inf Inf Inf10 13 0 6 Inf Inf Inf Inf8 5 6 0 4 Inf 10 InfInf Inf Inf 4 0 9 5 InfInf Inf Inf Inf 9 0 3 4Inf Inf Inf 10 5 3 0 6Inf Inf Inf Inf Inf 4 6 0R =1 2 3 2 5 6 7 81 2 1 4 5 6 7 81 1 3 4 5 6 7 82 234567 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8 k =3D =0 3 10 8 Inf Inf Inf Inf3 0 13 5 Inf Inf Inf Inf10 13 0 6 Inf Inf Inf Inf8 5 6 0 4 Inf 10 InfInf Inf Inf 4 0 9 5 InfInf Inf Inf Inf 9 0 3 4Inf Inf Inf 10 5 3 0 6Inf Inf Inf Inf Inf 4 6 0R =1 2 3 2 5 6 7 81 2 1 4 5 6 7 81 1 3 4 5 6 7 82 234567 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8k =4D =0 3 10 8 12 Inf 18 Inf3 0 11 5 9 Inf 15 Inf10 11 0 6 10 Inf 16 Inf8 5 6 0 4 Inf 10 Inf12 9 10 4 0 9 5 InfInf Inf Inf Inf 9 0 3 418 15 16 10 5 3 0 6Inf Inf Inf Inf Inf 4 6 0R =1 2 3 2 2 6 2 81 2 4 4 4 6 4 81 4 3 4 4 6 4 82 234567 84 4 4 4567 81 2 3 4 5 6 7 84 4 4 4567 81 2 3 4 5 6 7 8 k =5D =0 3 10 8 12 21 17 Inf3 0 11 5 9 18 14 Inf10 11 0 6 10 19 15 Inf8 5 6 0 4 13 9 Inf12 9 10 4 0 9 5 Inf21 18 19 13 9 0 3 417 14 15 9 5 3 0 6Inf Inf Inf Inf Inf 4 6 0R =1 2 3 2 2 2 2 81 2 4 4 4 4 4 81 4 3 4 4 4 4 82 2345 5 5 84 4 4 4567 85 5 5 5 567 85 5 5 5 567 81 2 3 4 5 6 7 8 k =6D =0 3 10 8 12 21 17 253 0 11 5 9 18 14 2210 11 0 6 10 19 15 238 5 6 0 4 13 9 1712 9 10 4 0 9 5 1321 18 19 13 9 0 3 417 14 15 9 5 3 0 625 22 23 17 13 4 6 0 R =1 2 3 2 2 2 2 21 2 4 4 4 4 4 41 4 3 4 4 4 4 42 2345 5 5 54 4 4 4567 65 5 5 5 567 85 5 5 5 567 86 6 6 6 6 678 k =7D =0 3 10 8 12 20 17 233 0 11 5 9 17 14 2010 11 0 6 10 18 15 218 5 6 0 4 12 9 1512 9 10 4 0 8 5 1120 17 18 12 8 0 3 417 14 15 9 5 3 0 623 20 21 15 11 4 6 0 R =1 2 3 2 2 2 2 21 2 4 4 4 4 4 41 4 3 4 4 4 4 42 2345 5 5 54 4 4 45 7 7 77 7 7 7 7 6 7 85 5 5 5 567 87 7 7 7 7 6 7 8 k =8D =0 3 10 8 12 20 17 233 0 11 5 9 17 14 2010 11 0 6 10 18 15 218 5 6 0 4 12 9 1512 9 10 4 0 8 5 1120 17 18 12 8 0 3 417 14 15 9 5 3 0 623 20 21 15 11 4 6 0R =1 2 3 2 2 2 2 21 2 4 4 4 4 4 41 4 3 4 4 4 4 42 2345 5 5 54 4 4 45 7 7 77 7 7 7 7 6 7 85 5 5 5 567 87 7 7 7 7 6 7 8D =0 3 10 8 12 20 17 233 0 11 5 9 17 14 2010 11 0 6 10 18 15 218 5 6 0 4 12 9 1512 9 10 4 0 8 5 1120 17 18 12 8 0 3 417 14 15 9 5 3 0 623 20 21 15 11 4 6 0 R =1 2 3 2 2 2 2 21 2 4 4 4 4 4 41 4 3 4 4 4 4 42 2345 5 5 54 4 4 45 7 7 77 7 7 7 7 6 7 85 5 5 5 567 87 7 7 7 7 6 7 8四、实验体会。

最短路问题(short-path problem)若网络中的每条边都有一个权值值(长度、成本、时间等)，则找出两节点(通常是源节点与结束点)之间总权和最小的路径就是最短路问题。

最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

最短路问题，我们通常归属为三类：单源最短路径问题（确定起点或确定终点的最短路径问题）、确定起点终点的最短路径问题（两节点之间的最短路径）1、Dijkstra算法：用邻接矩阵a表示带权有向图，d为从v0出发到图上其余各顶点可能达到的最短路径长度值，以v0为起点做一次dijkstra，便可以求出从结点v0到其他结点的最短路径长度代码：procedure dijkstra（v0：longint）；//v0为起点做一次dijkstrabegin//a数组是邻接矩阵，a[i,j]表示i到j的距离，无边就为maxlongintfor i:=1 to n do d[i]:=a[v0,i];//初始化d数组（用于记录从v0到结点i的最短路径）， fillchar(visit,sizeof(visit),false);//每个结点都未被连接到路径里visit[v0]:=true;//已经连接v0结点for i:=1 to n-1 do//剩下n-1个节点未加入路径里；beginmin:=maxlongint;//初始化minfor j:=1 to n do//找从v0开始到目前为止，哪个结点作为下一个连接起点（*可优化） if (not visit[j]) and (min>d[j]) then//结点k要未被连接进去且最小begin min:=d[j];k:=j;end;visit[k]:=true;//连接进去for j:=1 to n do//刷新数组d，通过k来更新到达未连接进去的节点最小值，if (not visit[j]) and (d[j]>d[k]+a[k,j]) then d[j]:=a[k,j]+d[k];end;writeln(d[n]);//结点v0到结点n的最短路。

最短路问题的求解方法最短路问题是图论中的经典问题之一，它在实际生活中有着广泛的应用，比如在交通规划、通信网络、物流配送等领域都有着重要的作用。

在解决最短路问题时，我们需要找到图中两个顶点之间的最短路径，即使得路径上的边的权值之和最小。

针对不同的图，我们可以采用不同的方法来求解最短路问题，下面将介绍几种常见的求解方法。

首先，最简单直接的方法是暴力搜索法。

暴力搜索法适用于小规模的图，它通过穷举所有可能的路径来找到最短路径。

虽然这种方法在理论上是可行的，但是在实际应用中由于时间复杂度过高，通常不适用于大规模的图。

其次，我们可以使用迪杰斯特拉算法来解决最短路问题。

迪杰斯特拉算法是一种贪心算法，它通过逐步扩展离源点距离最短的节点来逐步求解最短路径。

迪杰斯特拉算法的时间复杂度为O(V^2)，其中V为顶点数，因此适用于稠密图。

另外，我们还可以使用贝尔曼-福特算法来求解最短路问题。

贝尔曼-福特算法是一种动态规划算法，它通过多次松弛操作来逐步逼近最短路径。

贝尔曼-福特算法适用于存在负权边的图，但是由于其时间复杂度为O(VE)，因此在稠密图中效率较低。

最后，我们还可以使用Floyd-Warshall算法来解决最短路问题。

Floyd-Warshall算法是一种动态规划算法，它通过逐步考察所有顶点对之间的路径来求解最短路径。

Floyd-Warshall算法的时间复杂度为O(V^3)，因此适用于小规模图。

总的来说，不同的最短路求解方法适用于不同的图，我们需要根据具体的情况来选择合适的方法。

在实际应用中，我们还可以结合启发式算法、并行算法等方法来进一步提高求解效率。

希望本文介绍的内容能够对读者有所帮助，谢谢！。

最短路问题何谓最短路？最短路问题考虑的是有向网络N=（V，A，W），其中弧（i,j）∈A 对应的权又称为弧长或费用。

对于其中的两个顶点s，t∈V,以s 为起点，t 为终点的有向路称为s-t 有向路，其所经过的所有弧上的权（或弧长、费用）之和称为该有向路的权（或弧长、费用）。

所有s-t 有向路中权最小的一条称为s-t 最短路。

ij w 如何得到最短路？最短路问题的线性规划描述如下：(,)m i ni j i j i j A w x ∈∑ (1):(,):(,)1,,..1,,0,,ij ji j i j A j j i A i s s t x x s i s t ∈∈=⎧⎪t −=−=⎨⎪≠⎩∑∑ (2) 0ij x ≥ (3) 其中决策变量表示弧（i,j）是否位于s-t 路上：当=1时，表示弧（i,j）位于s-t 路上，当=0时，表示弧（i,j）不在s-t 路上。

本来，应当是0-1变量，但由于约束（2）的约束矩阵就是网络的关联矩阵，它是全幺模矩阵，因此0-1变量可以松弛为区间[0，1]中的实数（当用单纯形法求解时，将得到0-1整数解）。

ij x ij x ij x ij x 值得注意的是，我们这里将变量直接松弛为所有非负实数。

实际上，如果可以取0-1以外的整数，则约束条件并不能保证对应于非零的弧所构成的结构（记为P）一定是一条路，因为这一结构可能含有圈。

进一步分析，我们总是假设网络本身不含有负圈，而任何正圈不可能使目标函数最小，因此上面的约束条件（2），（3）可以保证当达到最优解时，P 如果包含圈，该圈一定是零圈，我们从P 中去掉所有的零圈，就可以得到最短路。

ij x ij x ij x 无圈网络与正费用网络一般采用标号设定算法。

Bellman 方程（最短路方程）将约束条件（2）两边同时乘以-1，得到其对偶问题为：m ax()t s u u − （4）..,(,)j i ij s t u u w i j A −≤∀∈ （5）根据互补松弛条件，当x 和u 分别为原问题和对偶问题的最优解时：()0,(,i j j i i j )x u u w i j −−=∀∈A （6） 因此,当某弧（i，j）位于最短路上时，即对应的变量＞0时，一定有ij x j i i u u w −=j 。

最短路最短路问题（short-path problem）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。

最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

单源最短路径包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。

在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

）算法可以采用Dijkstra 算法。

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法代码1#include <string.h>2#include<algorithm>3using namespace std;45const int maxnum = 100;6const int maxint = 99999999;78int dist[maxnum];9int prev[maxnum];//记录当前点的前一个结点10int c[maxnum][maxnum];11int n,line;1213void dijkstra(int n,int v,int *dist,int *prev,int c[maxnum][maxnum])//v代表源点14{15 bool s[maxnum];//判断是否已存入该点到S中16 for(int i = 1;i <= n;++i)17 {18 dist[i] = c[v][i];19 s[i] = 0;20 if(dist[i] == maxint)//代表当前点与源点没有直接相连21 prev[i] = 0;22 else23 prev[i] = v;//代表当前点的前一个节点是v，即源点24 }25 dist[v] = 0;//源点到源点的距离初始化为026 s[v] = 1;//源点已被遍历过，标记为12728 for(int i = 2;i <= n;++i)29 {30 int tmp = maxint;31 int u = v;32 for(int j = 1;j <= n;++j)33 {34 if((!s[j]) && dist[j] <tmp)//该点没有被遍历到并且源点到j点的距离小于记录的距离35 {36u = j;//记录下这一点37tmp = dist[j];//记录下这一点到源点的距离38 }39 }40 //找到距离最短的点退出循环41 s[u] = 1;//标记该点已经遍历过4243 for(int j = 1;j <= n;++j)44 {45 if((!s[j]) && c[u][j] <maxint)//j没有被遍历过并且从u到j还有这条路径46 {47 int newdist = dist[u] + c[u][j];//新的距离是从源点到u的距离加上从u到的距离48 if(newdist <dist[j])//如果新的距离比原来到j的距离要短49 {50 dist[j] = newdist;//则更新dist数组51 prev[j] = u;//标记j的前一个节点是u52 }53 }54 }55 }56}5758void searchpath(int *prev,int v,int u)//查找从v到u的最短路径59{60 int que[maxnum];//保存路径61 int tot = 1;62 que[tot] = u;//把终点存入路径数组63 tot++;64 int tmp = prev[u];65 while(tmp != v)66 {67 que[tot] = tmp;68 tot++;69tmp = prev[tmp];70 }71 que[tot] = v;72 for(int i = tot;i >= 1;--i)73 {74 if(i != 1)75 printf("%d->",que[i]);76 else77 printf("%d\n",que[i]);78 }79}808182int main()83{84 scanf("%d",&n);//输入结点数85 scanf("%d",&line);//输入路径数目86 int p,q,len;87 for(int i = 1;i <= n;++i)//初始化存储数组88 {89 for(int j = 1;j <= n;++j)90 {91 c[i][j] = maxint;92 }93 }94 for(int i = 1;i <= line;++i)//往存储数组里存放路径95 {96 scanf("%d%d%d",&p,&q,&len);97 if(len <c[p][q])//如果两个点之间有多条路，取路径较短的那一条98 c[p][q] = len;99 c[q][p] = len;//该语句根据实际情况写，用于无向路径中100 }101 for(int i = 1;i <= n;++i)//初始化标记数组102 dist[i] = maxint;//该数组记录从起点到该点的最短路径长度103104105 dijkstra(n,1,dist,prev,c);106 printf("从源点到最后一个顶点的最短路径长度为：%d\n",dist[n]);107 printf("从源点到最后一个顶点的路径为：");108 searchpath(prev,1,n);109}全局最短路求图中所有的最短路径。

最短路问题详解+题⽬概念若⽹络中的每条边都有⼀个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最⼩的路径就是最短路问题算法1. Floyd-warshall算法（1）介绍：⾮常的好⽤，通常可以在任何图中使⽤，包括有向图、带负权边的图。

（2）算法讲解：Floyd算法从第⼀个顶点开始，依次将每个顶点作为媒介k，然后对于每⼀对顶点u和v，查看其是否存在⼀条经过k的，距离⽐已知路径更短的路径，如果存在则更新它。

2. Dijkstra算法（1）介绍：是典型的单源最短路径算法，⽤于计算⼀个节点到其他所有节点的最短路径。

主要特点是以起始点为中⼼向外层层扩展，直到扩展到终点为⽌。

注意该算法要求图中不存在负权边。

（2）算法讲解：⽤贪⼼实现，先把起点到所有点的距离存下来找个最短的，进⾏松弛操作再找出最短的，把所有的点找遍之后就存下了起点到其他所有点的最短距离。

> 松弛操作：遍历⼀遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离> 注意：除了距离起点的距离为0外，其他距离均设为⽆穷⼤。

3. Bellman-Ford算法（1）介绍：Bellman-ford算法适⽤于单源最短路径，图中边的权重可为负数即负权边，但不可以出现负权环。

> 负权边：为负数的边。

> 负权环：源点到源点的⼀个环，环上权重和为负数。

（2）算法讲解：1.初始化：除了起点的距离为0外，其他均设为⽆穷⼤。

2.迭代求解：循环对边集合E的每条边进⾏松弛操作，使得顶点集合V中的每个顶点v的距离长逐步逼近最终等于其最短距离长；3.验证是否负权环：再对每条边进⾏松弛操作。

如果还能有⼀条边能进⾏松弛，那么就返回False，否则算法返回True题⽬输⼊:第⼀⾏n表⽰边的个数，接下来n⾏a,b,len，最后⼀⾏s，t求点s到点t的距离输⼊样例：71 2 22 5 21 3 42 3 13 5 61 4 73 4 1Dijkstra打法#include <bits/stdc++.h>#define maxx 0x7fusing namespace std;int u[105][105]={0x7f},dis[105];bool vis[105]={false};int main(){int n,s,t,x,y,minn,k;cin>>n;for (int i=1;i<=n;i++){dis[i]=maxx;vis[i]=false;}for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)u[i][j]=maxx;for (int i=1;i<=n;i++){cin>>x>>y;cin>>u[x][y];}cin>>s>>t;for (int i=1;i<=n;i++)dis[i]=u[s][i];dis[s]=0;vis[s]=true;for (int i=1;i<=n;i++){minn=maxx;k=0;for (int j=1;j<=n;j++)if (vis[j]==false&&dis[j]<minn){minn=dis[j];k=j;}if (k==0) break;vis[k]=true;for (int j=1;j<=n;j++)if (dis[k]+u[k][j]<dis[j])dis[j]=dis[k]+u[k][j];}cout<<dis[t];return 0;}floyd打法#include <bits/stdc++.h>using namespace std;const int maxx=0x7f;int u[105][105];int main(){int s,t,n,x,y;cin>>n;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)u[i][j]=0x7f;for (int i=1;i<=n;i++){cin>>x>>y;cin>>u[x][y];}cin>>s>>t;for (int k=1;k<=n;k++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){if (i!=j&&i!=k&&j!=k&&u[i][j]>u[i][k]+u[k][j])u[i][j]=u[i][k]+u[k][j];}cout<<u[s][t];return 0;}题⽬⼤意找⼀个点使得到其他点的距离总和最⼩Floyed穷举出答案#include <bits/stdc++.h>using namespace std;const int inf=100000007;int p[105],dis[105][105],sum;int n,lch,rch;int main(){cin>>n;memset(dis,inf,sizeof(dis));for(int i=1;i<=n;i++){dis[i][i]=0;cin>>p[i];cin>>lch>>rch;if(lch>=0) dis[i][lch]=1;dis[lch][i]=1;if(rch>=0) dis[i][rch]=1;dis[rch][i]=1;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; int minn=inf;for(int i=1;i<=n;i++){sum=0;for(int j=1;j<=n;j++)sum+=p[j]*dis[i][j];if(minn>sum) minn=sum;}cout<<minn<<endl;return 0;}。

最短路径问题的求解最短路径问题是信息学竞赛中常见的一类中等难题，这是一个非常能联系实际的问题，甚至有时一些看似跟最短路径问题无关的问题也可以归结为最短路径问题。

本文就简要分析一下此类问题的算法，以使大家一起探讨一下该类问题，也使没参加信息学竞赛的同学对信息学竞赛有个简单了解。

下面我们以具体例题来看看这类问题的解法：例1、假设A、B、C、D、E各个城市之间旅费如下图所示。

某人想从城市A 出发游览各城市一遍，而所用费用最少。

试编程序输出结果。

解这类题时同学们往往不得要领，不少同学采用穷举法把所有可能的情况全部列出，再找出其中最短的那条路径；或是采用递归或深度搜索，找出所有路径，再找出最短的那条。

这两种方法可见都是费时非常多的解法，如果城市数目多的话则很可能要超时了。

实际上我们知道，递归、深度搜索等算法一般用于求所有解问题（例如求A 出发每个城市走一遍一共有哪几种走法），而这几种算法对于求最短路径这类最优解问题显然是不合适的，以下介绍的几种算法就要优越很多。

首先，对于这类图我们都应该先建立一个邻接矩阵来存放任意两点间的距离数据，以便在程序中方便调用，如下：const dis:array[1..5,1..5] of integer =( ( 0, 7, 3,10,15),( 7, 0, 5,13,12),( 3, 5, 0, 5,10),(10,13, 5, 0,11),(15,12,10,11, 0));以下是几种解法：一、宽度优先搜索宽度优先搜索并不是一种很优秀的算法，只里只是简单介绍一下它的算法。

具体方法是：1、从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其距离；2、再次以AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然AD可以展开得到ADB、ADC、ADE，AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其距离；3、再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABED……AEDB、AEDC，每个结点也需记录下其距离；4、再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、……、AEDBC、AEDCB，每个结点也需记录下其距离；5、到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。