【数学建模算法】(8)图的应用：最短路问题

作者: 热爱学习的高老板 | 来源:发表于2019-08-10 16:31 被阅读5次

我们上一部分了解了有关图的一系列基础概念，这一部分我们尝试进行应用解决一个经典问题——最短路径问题。

1.两个指定顶点之间的最短路径

问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。

以各城镇为 $G$ 的顶点，两城镇间的直通铁路为图 $G$ 的相应两顶点间的边，得图 $G$ 。对 $G$ 的每一边 $e$ ，赋以一个实数 $w(e)$ ——铁路的长度，称为 $e$ 的权，得到赋权图 $G$ 。 $G$ 的子图的权指子图的各边的权和。问题就是求赋权图 $G$ 中指定的两个顶点 $u_{0}, v_{0}$ 见具有最小权的轨。这条轨叫做 $u_{0}, v_{0}$ 间的最短路，它的权叫做 $u_{0}, v_{0}$ 间的距离，也记做 $d\left(u_{0}, v_{0}\right)$ 。

求最短路已有成熟算法：（Dijkstra算法），其基本思想是按距 $u_{0}$ 从近到远为顺序，依次求得 $u_{0}$ 到 $G$ 各顶点的最短路和距离，直到 $v_{0}$ （或直至 $G$ 的所有顶点），算法结束，为避免重复保留每一步的计算信息，采用了标号算法。下面是该算法。

1.令 $l\left(u_{0}\right)=0$ ，对 $v \neq u_{0}$ ，令 $l(v)=\infty$ ， $S_{0}=\left\{u_{0}\right\}, \quad i=0$
2.对每个 $v \in \overline{S}_{i}\left(\overline{S}_{i}=V \backslash S_{i}\right)$ （反斜杠代表求差集，所以 $\overline{S}_{i}$ 代表 $\overline{S}_{i}$ 的补集），用 $\min _{u \in S_{j}}\{l(v), l(u)+w(u v)\}$ 代替 $l(v)$ ，计算
$\min _{v \in S}\{l(v)\}$ ，把达到这个最小值的一个顶点记为 $u_{i+1}$ ，令 $S_{i+1}=S_{i} \cup\left\{u_{i+1}\right\}$
3.若 $i=|V|-1$ ，停止；若 $i<|V|-1$ ，用 $i+1$ 代替 $i$ ，转到第2步。

算法结束时，从 $u_{0}$ 到各顶点 $v$ 的距离由 $v$ 的最后一次的标号 $l(v)$ 给出。在 $v$ 进入 $S_{i}$ 之前的标号 $l(v)$ 叫做 $T$ 标号， $v$ 进入 $S_{i}$ 时的标号 $l(v)$ 叫做 $P$ 标号，算法就是不断修改各项点的 $T$ 标号，直至获得 $P$ 标号。若在算法运行过程中，将每一顶点获得 $P$ 标号所由来的边在图上标明，则算法结束时， $u_{0}$ 至各项点的最短路也在图上标示出来了。

下图是一个计算例子，横杠上的数字代表权值。

例1 如下图，计算最短路问题

计算流程1
计算流程2

例2 某公司在六个城市 $c_{1}, c_{2}, \cdots, c_{6}$ 中有分公司，从 $c_{i}$ 到 $c_{j}$ 的直接航程票价记在下述矩阵(i,j)位置上（ $\infty$ 代表无直接航路），请帮助该公司设计一张城市 $c_{i}$ 到其他城市间的票价的最便宜的路线图。
$\left[\begin{array}{cccccc}{0} & {50} & {\infty} & {40} & {25} & {10} \\ {50} & {0} & {15} & {20} & {\infty} & {25} \\ {\infty} & {15} & {0} & {10} & {20} & {\infty} \\ {40} & {20} & {10} & {0} & {10} & {25} \\ {25} & {\infty} & {20} & {10} & {0} & {55} \\ {10} & {25} & {\infty} & {25} & {55} & {0}\end{array}\right]$

用矩阵 $a_{n \times n}$ （n为顶点个数）存放各边权的邻接矩阵，行向量 $pb,index_{1},index_{2},d$ 分别用来存放 $P$ 标号信息，标号顶点顺序，标号顶点索引，最短通路的值。其中分量。
$p b(i)=\left\{\begin{array}{l}{1}，第i顶点已编号 \\ {0}，第i顶点未标号\end{array}\right.$
$index _{2}(i)$ 存放始点到第 $i$ 点最短通路中第 $i$ 顶点前一顶点的序号；
$d(i)$ 存放由始点到第 $i$ 点最短通路的值。
求第一个城市到其他城市的最短路径的Matlab程序如下：

clc,clear
a=zeros(6);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
a(5,6)=55;
a=a+a';
a(find(a==0))=inf;
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
d(1:length(a))=inf;d(1)=0;temp=1;
while sum(pb)<length(a)
    tb=find(pb==0);
    d(tb)=min(d(tb),d(temp)+a(temp,tb));
    tmpb=find(d(tb)==min(d(tb)));
    temp=tb(tmpb(1));
    pb(temp)=1;
    index1=[index1,temp];
    temp2=find(d(index1)==d(temp)-a(temp,index1));
    index2(temp)=index1(temp2(1));
end
d, index1, index2

这里提供Dijkstra标号算法的函数：

function [mydistance,mypath]=mydijkstra(a,sb,db);
% 输入：a—邻接矩阵(aij)是指i到j之间的距离，可以是有向的
% sb—起点的标号, db—终点的标号
% 输出：mydistance—最短路的距离, mypath—最短路的路径
n=size(a,1); visited(1:n) = 0;
distance(1:n) = inf; % 保存起点到各顶点的最短距离
distance(sb) = 0; parent(1:n) = 0;
for i = 1: n-1
    temp=distance;
    id1=find(visited==1); %查找已经标号的点
    temp(id1)=inf; %已标号点的距离换成无穷
    [t, u] = min(temp); %找标号值最小的顶点
    visited(u) = 1; %标记已经标号的顶点
    id2=find(visited==0); %查找未标号的顶点
    for v = id2
        if a(u, v) + distance(u) < distance(v)
            distance(v) = distance(u) + a(u, v); %修改标号值
            parent(v) = u;
        end
    end
end
mypath = [];
if parent(db) ~= 0 %如果存在路!
    t = db; mypath = [db];
    while t ~= sb
        p = parent(t);
        mypath = [p mypath];
        t = p;
    end
end
mydistance = distance(db);
return

【数学建模算法】(8)图的应用：最短路问题

1.两个指定顶点之间的最短路径

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数学建模艺术

【散人】数学建模

数学建模课程笔记