最短路问题（一）

一、最短路问题简述

最短路问题是网络理论中应用最广泛的问题之一，许多优化问题：比如设备更新，管道铺设、线路安排，工厂布局，运输线路安排等，都可以转化为最短路问题。

最短路问题有两种叙述：

（1）指定图中两点s,t，求连接s和t的链μ的权和最小，即

（2）求图G的任意两点之间的最短距离，为求解其它问题作铺设。

二、求定点间的最短距离（Dijkstra算法）

 设G=(V,E)为连通图，赋权矩阵为A，vs和vn是图的两个顶点，μ是连接vs,vn的一条链，求使得链上所有边的权和最小的链，称为连接vs,vn的最短路径。数学模型为

1、Dijkstra(笛卡斯特拉）算法（1959年）原理

若{vs,v1,v2,…,vn-1,vn}是连接vs,vn的最短路径，则{vs,v1,…,vn-1}是连接vs,vn-1的最短路径。

2、符号说明

• V为顶点集合
• E为边集
• vs为起点v
• vn为终点
• p(vi)为vs到vi的最短距离,i=s,1,…,n。

3、Dijkstra算法步骤（标号法）

步骤1：

初始化参数：距离初始化：p(vs)=0,t(vi)=+∞,i=1,2,…,n；

步骤2：

设vi是刚刚得到p标号的点，计算

步骤3：

比较所有标t标号的点，把最小值的改为p标号，即 若有几个同时最小，都改为标号p；

步骤4：

用vk0替代vi重复步骤2-步骤3，直到所有点都改为p标号。

案例1

用笛杰斯特拉算法求图1中v1到v8的最短距离。

【符号设置】

• d=d(i,j)8×8； 图1的权矩阵；
• p=[0,∞,∞,∞,∞,∞,∞,∞,∞]：各顶点的p标号初始值；
• t=[0,∞,∞,∞,∞,∞,∞,∞,∞]：各顶点t标号的初值；
• (u,v):起点为u，终点为v的边，(u,v)∈E；
• yu : 记录计算顶点的顺序；

【求解流程】

【求解结果】

按照以上流程编写matlab程序，计算得到表1

% 初始化代价矩阵，8x8 的零矩阵
d = zeros(8,8);
% 设置代价矩阵中的边权，表示节点之间的距离或权重
d(1,2) = 4; d(1,3) = 6; d(2,4) = 5; d(2,5) = 4;
d(3,4) = 4; d(3,5) = 7; d(4,6) = 9; d(4,7) = 7;
d(5,6) = 5; d(5,7) = 6; d(6,7) = 5; d(6,8) = 4; d(7,8) = 1;
% 初始化顶点到源点 1 的最短路径长度 p，所有值初始化为无穷大
p = inf * ones(1,8);
p(1) = 0;
% 存储当前计算的最短路径长度
t = p;
% 记录已经遍历过的顶点
r = 1;
% 存储当前点 u 的前一个点 v，即最短路径上 u 的前一个顶点是 v
yu = zeros(1,8);
yu(1) = 1;
% 当前点 u 的索引
u = 1;
% 进行 Dijkstra 算法的主循环，一直到遍历完所有节点
while r < 8
    % 找出点 u 所有可以到达的点 v
    v = find(d(u,:) > 0);
    % 计算点 v 相对于源点 1 的最短路径长度并存储在 t(v) 中
    nv = length(v);
    for k = 1:nv
        t(v(k)) = min(t(v(k)), p(u)+d(u,v(k)));
    end
    % 找到目前为止未处理的所有点中，距离源点 1 最近的点
    pinf = find(p == inf);
    mu = min(t(pinf));
    dm = find(t == mu);
    % 多个可选点中选择第一个作为新的当前点
    p(dm) = mu;
    u = dm(1);
    % 记录最短路径上点 u 的前一个点
    yu(u) = u;
    % 统计遍历到的节点数
    r = r+1;
end

表1   各点到1的最短距离

三、求任意两点之间的最短路径（Floyd算法）

有些问题，比如运输问题、网络布局问题、旅游路线规划问题，需要计算任意两点的最短路径，可用前面的Dijkstra算法，但点比较多时，就比较繁琐，下面介绍Floyd算法（1962年）可求出任意两点之间的最短距离。

【算法步骤】

步骤1：

输入权矩阵D(0)=D;

步骤2：

计算

步骤3：

中(i,j)元素就是vi,vj的最短距离。

案例2

求图中所示G的任意两点之间的最短距离。

【符号设置】

D：网络权矩阵D=(dij)n×n;

【计算流程】

【计算结果】

编写例2的Floyd算法的matlab程序，计算得到个点之间的最短距离存入表.

d=inf*ones(5,5);
d(1,2)=5;d(1,3)=1;d(1,4)=2;
d(2,1)=5;d(2,3)=10;d(2,5)=2;
d(3,1)=2;d(3,2)=3;d(3,4)=2;d(3,5)=8;
d(4,1)=2;d(4,3)=6;d(4,5)=4;
d(5,2)=2;d(5,3)=4;d(5,4)=4;
for k=1:5
    d(k,k)=0;
end
for k=1:5
   for k1=1:5
      for k2=1:5
        d(k1,k2)=min(d(k1,k2),d(k1,k)+d(k,k2));
      end
   end
end