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

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

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

以各城镇为的顶点，两城镇间的直通铁路为图的相应两顶点间的边，得图。对的每一边，赋以一个实数——铁路的长度，称为的权，得到赋权图。的子图的权指子图的各边的权和。问题就是求赋权图中指定的两个顶点见具有最小权的轨。这条轨叫做间的最短路，它的权叫做间的距离，也记做。

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

1.令，对，令，
2.对每个（反斜杠代表求差集，所以代表的补集），用代替，计算
，把达到这个最小值的一个顶点记为，令
3.若，停止；若，用代替，转到第2步。

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

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

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

计算流程1

计算流程2

例2 某公司在六个城市中有分公司，从到的直接航程票价记在下述矩阵(i,j)位置上（代表无直接航路），请帮助该公司设计一张城市到其他城市间的票价的最便宜的路线图。

用矩阵（n为顶点个数）存放各边权的邻接矩阵，行向量分别用来存放标号信息，标号顶点顺序，标号顶点索引，最短通路的值。其中分量。

存放始点到第点最短通路中第顶点前一顶点的序号；
存放由始点到第点最短通路的值。
求第一个城市到其他城市的最短路径的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