最短路径树（SPT）介绍及matlab代码

文章目录

• 前言
• 一、最短路径树是什么？
• 二、最短路径树的算法
• • 1、Dijkstra算法（我比较常用和喜欢的算法）
  • 2、Floyd算法
• 总结

---

前言

  最短路径树是路由算法设计中常用到的一种树，往往我们利用其中继转发的特性将其传输成本作为基线进行比较。SPT可以保证每个节点到接收器节点（sink node）的路径最短，但是不能保证整个网络的路径和最小，大家一定要将其和MST（最小生成树）区分开。在这里和大家聊一聊SPT的基本原理和两种算法，希望大家有所收获~

---

一、最短路径树是什么？

  最短路径树，英文名称为Shortest Path Tree，简称为SPT，是一种使用最短路径算法生成的数据结构树。其定义如下。
  考虑一个连通无向图 G G G，一个以顶点 v v v为根节点的最短路径树 T T T是图 G G G满足下列条件的生成树——树 T T T中从根节点 v v v到其它顶点 u u u的路径距离是在两点间的最短路径距离，因此可以满足每个节点到sink的路径都是最短的。
  在一个所有最短路径都明确（例如没有负长度的环）的连通图，我们可以使用如下算法构造最短路径树：
  使用Dijkstra算法或Floyd算法计算图 G G G 从根节点 v v v到顶点 u u u的最短距离 。
  对于所有的非根顶点 u u u，我们可以给 u u u分配一个父顶点 f u f_u fu​， 连接至 u u u且 d i s t ( f u ) + e d g e dist(f_u)+edge dist(fu​)+edge- d i s t ( f u , u ) = d i s t ( u ) dist(f_u,u)=dist(u) dist(fu​,u)=dist(u) 。当有多个 f u f_u fu​满足条件时，选择从 v v v到 f u f_u fu​的最短路径中边最少的 f u f_u fu​。当存在零长度环的时候，这条规则可以避免循环。
  用各个顶点和它们的父节点之间的边构造最短最短路径树。
  上面的算法保证了最短路径树的存在。像最小生成树一样，最短路径树通常也不只有一个的。在所有边的权重都相同的时候，最短路径树和广度优先搜索树一致。在存在负长度的环时，从 v v v到其它顶点的最短简单路径不一定构成最短路径树(还没用到过负长度）。
  以上内容参考百度百科：

https://baike.baidu.com/item/%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E6%A0%91/22787159

二、最短路径树的算法 1、Dijkstra算法（我比较常用和喜欢的算法）

  设置两个定点的集合 T T T和 S S S，集合 S S S中存放已找到最短路径的定点，集合 T T T中存放当前还未找到的最短路径的定点。初始状态时，集合 S S S中只包含顶点 v v v然后不断从集合 T T T中选取到顶点 v v v路径长度最短的节点 u u u加入集合 S S S，集合 S S S中每加入一个新的节点 u u u，都要修改顶点 v v v到集合 T T T中剩余节点的最短路径长度值，集合 T T T中每个节点新的最短路径长度值为刚加进来的节点 u u u到原节点的最短距离值+原节点到顶点 v v v的距离值和刚加进来的节点 u u u到顶点 v v v的距离的较小值。此过程不断重复，直到集合T的顶点全部加入到集合S为止。
  其中，以上内容参考自百度百科，更详细的介绍和下面所示的代码皆出自以下网址，写的很详细。

百度百科
https://baike.baidu.com/item/%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E6%A0%91/22787159
详细介绍
https://blog.csdn.net/weixin_41971010/article/details/107666810

function [mydistance,mypath]=dijkstra(a,sb,db);
% 输入：a—邻接矩阵(aij)是指i到j之间的距离，无向矩阵
% sb—起点的标号, db—终点的标号
% 输出：mydistance—短路的距离, mypath—短路的路径
n=size(a,1);         %找出节点个数n
visited(1:n)=0;      %构建初步的查找矩阵visited，0代表未查找，1代表查找过
distance(1:n)=inf;   %保存起点到各顶点的短距离
distance(sb)=0;      %从起点sb到起点的距离为0
parent(1:n)=0;       
for i=1:n-1                   %循环查找n-1次   
    temp=distance;            %将distance中的值赋给temp，避免运算时丢失原值
    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

2、Floyd算法

  从代表任意两个节点 V i V_i Vi​到 V j V_j Vj​距离的带权邻接矩阵 D ( 0 ) D(0) D(0)开始，首先计算 D ( 1 ) D(1) D(1)，即计算 V i V_i Vi​到 V j V_j Vj​经过一次经转的所有可能路径，经过比较后选出最短路，代替 D ( 0 ) D(0) D(0)中对应的路径，迭代列出距离矩阵 D ( 1 ) D(1) D(1)， D ( 1 ) D(1) D(1)中各元素表示通过一次迭代后网络中任意两点间最短路，也即网络中任意两点之间直接到达或只经过一个中间点时的最短路。在此基础上依次计算 D ( 2 ) ， D ( 3 ) ， … ， D ( k ) D(2)，D(3)，…，D(k) D(2)，D(3)，…，D(k)， D ( k ) D(k) D(k)中对应的元素表示任意两点间不经过中间点或最多允许经过 2 k + 1 2k+1 2k+1个中间点时的最短路。当 D ( k + 1 ) = D ( k ) D(k+1)=D(k) D(k+1)=D(k)时，表明得到的带权邻接矩阵 D ( k ) D(k) D(k)就反映了所有顶点对之间的最短距离信息，成为最短距离矩阵。
  其中，以上内容也参考自百度百科，更详细的介绍和下面所示的代码皆出自以下网址，写的也很详细。

百度百科
https://baike.baidu.com/item/%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E6%A0%91/22787159
详细介绍
https://blog.csdn.net/qq_42916979/article/details/104128709

%% FileName:Floyd.m
%% Date:2020-4-13
%% Writer:Yida
%% Function:输出网络图的最短距离矩阵和路由矩阵，指定两结点间的最短距离及其路径

%%
function [D, P, dis, path] = Floyd(W, start, stop) %start为指定起始结点，stop为指定终止结点
D = W; %最短距离矩阵赋初值
n = length(D); %n为结点个数
P = zeros(n,n); %路由矩阵赋初值

for i = 1:n
    for j = 1:n
        P(i,j) = j;
    end
end

for k = 1:n
    for i = 1:n
        for j = 1:n
            if D(i,k) + D(k,j) < D(i,j)
                D(i,j) = D(i,k) + D(k,j);   %核心代码
                P(i,j) = P(i,k);
            end
        end
    end
end
                  
if nargin ~= 3
    errordlg('参数个数输入有误！', 'Warning!')
else
    dis = D(start, stop); %指定两结点间的最短距离
    m(1) = start;
    i = 1;

    while P(m(i),stop) ~= stop
        k = i + 1;
        m(k) = P(m(i),stop);
        i = i + 1;
    end
    m(i+1) = stop;
    path = m; %指定两结点之间的最短路径
end
%%

总结

  SPT算法是通信网络领域最常用的算法之一，希望大家可以仔细研究算法的原理再进行代码的尝试，因为这样很容易发现问题或者进行改进，希望大家可以通过这篇博客有所收获~