最短路问题基本内容：（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－Ｖ２－Ｖ３－Ｖ６－Ｖ７－Ｖ８。
任意两点间的最短路Floyd及其本质我们知道在已知起点的情况下，求到其他任何⼀点的最短路是⽤dijkstra，那么在⼀个有向图中，我们想知道任意两点之间的最短路，我们就可以使⽤floyd，⽽且这个算法表⾯看起来⾮常的简单，就是⼀个三重循环，如果这个图有N个点，那么复杂度为O(|N|3)，代码如下。
1for(int k=0;k<n;k++)2for(int i=0;i<n;i++)3for(int j=0;j<n;j++)4 d[i][j]=min(d[i][j],d[i][k]+d[k][j]);在复杂度这么⾼的情况下，⼀般情况下如果不是板⼦题直接⽤的话肯定是会超时的，所以我们还是需要了解Floyd是怎么进⾏的，其实它的本质就是dp。
其实我从上⾯的代码中不难看出Floyd是采⽤状态转移的⽅式来更新各个点之间的距离的，⽽这个点就是k，即从i-j之间的最短路是否经过k点，不断的更新从⽽取得最优解，下⾯我们详细的说⼀下。
假设从顶点i出发，仅经由顶点V k={1，2，3，···，k}抵达顶点j的最短路径成本为A k[i,j]。
⾸先，A0[i,j]表⽰从i到j不经由其他任何顶点，所以其值就等于连接i,j边的权值，如果不存在边时其⼤⼩为正⽆穷，接下来是k=1,2,3,···,|N|的情况，我们需要通过A k-1来计算A k，那么我们只需要考虑是否经过k点两种情况。
如果经过k，则路径会被分为i-k，k-j两个路径，⽽且这两个路径全都只经过V k-1，中的顶点，因此A k=A k-1[i,k]+A k-1[k,j]。
如果不经过k，那就意味着A k[i,j]只经过i,j及属于V k-1中的顶点，所以A k[i,j]=A k-1[i,j];综上所知A k[i,j]=min(A k-1[i,j],A k-1[i,k]+A k-1[k,j])。
最短路问题(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的最短路。
