最短路问题案例(short-path problem)

含参数的最短路问题及其原始—对偶算法
一、含参数的最短路问题
含参数的最短路问题（Parametrized Shortest Path Problem, PSP）是最短路径问题（Shortest Path Problem, SPP）的扩展，是的待求解的网络拓扑结构依赖于一组实参构成的参数，它主要用在那些路径选择依赖于实参因素的场合。

与传统SPP相比，在含参数SPP中任务不在于仅求出只依赖于路径上边/弧权值的最短路径，而是求出优化另外一组实数参数的最优路径，这给出的解决方案不再是路径，而是一组相关的参数值，通常这组参数值都是路径上一个或多个节点的权值值。

二、原始——对偶算法
含参数SPP的计算机解决方案一般有两种：原始——对偶算法和隐式唯一性解法。

原—对偶算法是一种割点问题求解方法，由原始算法和对偶算法组成。

原始算法通过改变权值算出最优路径及其关联参数；而对偶算法则采用贪心算法来进行搜索最优路径，当采用原始-对
偶算法解决SPP时，先利用原始算法找出最优的路径及参数，然后再用对偶算法进行简化和精确，以此来减少搜索范围，加快收敛速度。

原始算法首先先利用贪心算法找出满足要求的路径，确定出路径上所有节点的参数值。

然后利用搜索策略对得到的路径进行优化，其方法有：一是贪心优化，二是贪心轮换，三是贪心随机优化，等等。

贪心优化主要是按贪婪算法边/弧及其所有变量依次改变其参数值，找出更优的路径；贪心轮换的思路主要是尝试若干次通过不同参数设置对路径上某些节点变换使得路径达到最佳状态；而贪心随机优化则是改变每个变量以优化整个路径。

最短路问题基本内容：（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－Ｖ２－Ｖ３－Ｖ６－Ｖ７－Ｖ８。

问题：求出A-F之间最短路线；（1）写出思路于算法；（2）Matlab 编程找出最短路径。

答案：A-F之间的最短路线有A-B3-D3-E1-F，A-B3-D3-E1-E2-F；A-B2-C1-D1-D2-E2-F 这三条路线的最短距离均为8。

方案一：思路：对于是否返回的分析：如图可以看出只有B端才能跨越C端的点直接到达D端的，其余的各端点都是必须按照字母顺序一路下来。

若如D端返回到C端或B端这是不可能的，因为这样无疑增加了路程，如图可以看出C端的点能到达D端的各个点，所以要求的直接命中想到达的该点；而D端出发去到E端后有图可以看出不可能再返回D端了，因为这只会增加路线的长度，而且E 端的各点是相通的，也没必要再返回D端；同样B端到达C端或D端的，因为B2,B2到能直接到达C端的各点，只有B1只能到达C1，但B1它到D1的距离和B1点到C1的距离同样为4但也不可能经过C1后返回B端的，因为C1也是联系D端的各点，而且你要返回B 段端，还不如在A端的时候就选择好一个理想的B点，这样距离会更加短。

所以不能进行返回。

如图将我们本来所需要的的路线分成两半，以D字母的为中间端。

后半部分：后半部分主要由D端连接到E端最后才连接到F端的,同时D端无法越过E端直接连接到F端。

更为重要的是前半部分，也必须要经过D端才能与F端相接，所以构成他们之间的枢纽定在D端是最好不过的。

首先的是先分析D端的三个点D1，D2，D3分别到点F的最短距离。

一、已经从D端出发去到E端后有图可以看出不可能再返回D端了，因为这只会增加路线的长度，而且E端的各点是相通的，也没必要再返回D端；二、由图可以看出E端到点F最好的路线是E2-F距离为1，除E2外的E1，E3他们到F点的方式（E1-F, E1-E2-F ,E3-F ,E3-E2-F）的距离均为2；所以如果能先到达E2则可以只考虑E2到F这条路线。

若先到达了E1，或E3、则这路线的最短路径必定变化为两条。

最短路问题实际案例介绍最短路问题是图论中的一个经典问题，其目标是找到两个顶点之间的最短路径。

这个问题在日常生活中有着广泛的应用，例如导航系统、网络路由以及物流配送等场景中都需要解决最短路问题。

本文将通过实际案例来深入探讨最短路问题及其应用。

什么是最短路问题？最短路问题是指在一个给定的图中，找到两个顶点之间的最短路径。

通常情况下，路径的长度可以通过边的权重来衡量。

最短路问题可以分为单源最短路问题和全源最短路问题，前者是指从一个固定的起点出发，求到图中其他所有顶点的最短路径；后者是指求图中任意两个顶点之间的最短路径。

实际案例：导航系统导航系统是最短路问题的一个典型应用。

当我们使用导航系统来规划路线时，系统需要找到最短路径以优化我们的行车时间。

下面以一个具体案例来说明导航系统如何解决最短路问题。

案例场景假设我们身处一座陌生的城市，想要前往城市中心的一个著名景点。

我们打开导航系统，输入起点和终点信息。

导航系统会根据地图数据自动生成最短路径，并提供导航指引。

导航系统的实现导航系统实现最短路径规划的过程可以分为以下几个步骤：1.构建路网图：将城市中的道路以及交叉口等信息转化为图的形式。

图中的节点表示交叉口，边表示道路，边的权重可以表示行驶距离、时间等。

2.选择算法：根据实际需求选择合适的最短路径算法。

常见的算法有Dijkstra算法、Bellman-Ford算法和A*算法等。

3.计算最短路径：根据选定的算法，在路网图上计算起点到终点的最短路径。

算法会考虑边的权重以及路径的方向等因素。

4.导航指引：根据计算得到的最短路径，导航系统会生成具体的导航指引，包括行驶指示、路口转向、距离和预计时间等信息。

优化策略导航系统通过不断的优化，提高了最短路径的计算效率和准确性。

以下是几种常见的优化策略：1.路网数据更新：导航系统会及时更新路网数据，包括道路信息、交通状况等。

这样可以保证计算得到的最短路径更准确。

2.平行算法：为了加快计算速度，导航系统采用并行算法来计算最短路径。

最短路问题(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的最短路。

最短路最短路问题（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}全局最短路求图中所有的最短路径。