1.Floyed算法

1.1适用范围

$\bullet$ 求每队顶点的最短路径

$\bullet$ 有向图、无向图和混合图

1.2算法思想

直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1)，D(2)…D(n)（每次加入一个点然后更新最短路径矩阵D），D(n)是图的最短距离矩阵，同时引入一个后继点矩阵path记录两点间的最短路径。

1.3实例

对于如下无向图：

我们可以得如下带权邻接矩阵：
$$\left[\begin{array}{cccccc}0& 7& 9& inf& inf& 14\\ 7& 0& 10& 15& inf& inf\\ 9& 10& 0& 11& inf& 2\\ inf& 15& 11& 0& 6& inf\\ inf& inf& inf& 6& 0& 9\\ 14& inf& 2& inf& 9& 0\end{array}\right]$$

实现步骤：

$\bullet$ 变量：输入变量与输出变量

$\bullet$ 赋初值：对所有的i、j，$$D(i,j)=w(i,j),path(i,j)=j,k=1(k表示加入的顶点个数)$$

$\bullet$ 更新D(i,j)、path(i,j)，对于所有i、j，若$$D(i,k)+D(k,j)<D(i,j)$$
则：$$D(i,j)=D(i,k)+D(k,j),path(i,j)=path(i,k),k=k+1$$

$\bullet$ 每次插入一个顶点重复进行更新操作，直到 k=n+1 终止。

2.代码

2.1floyd函数

function [D,path,min1,path1]=floyd(a,start,terminal)
%D(i,j)表示i到j的最短路径，path(i,j)表示i到j之间的最短路径上顶点i的后继点。
%min1返回start和terminal之间的最短距离，path1返回start和terminal之间的最短路径
%a为带权邻接矩阵，start、terminal分别是起始点和终止点

D=a;n=size(D,1);path=zeros(n,n);
%n为顶点个数，生成D、path矩阵

%遍历一遍矩阵，初始化path矩阵，先将可以直接相连的点的path进行补充
for i=1:n
    for j=1:n
        if D(i,j)~=inf
            path(i,j)=j;
        end  
    end
end

%三重遍历，查找是否有中继点可以使得路径缩短，若有则更新D、path矩阵
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);
                path(i,j)=path(i,k);
            end 
        end
    end
%这里演示了每一步的调整过程
k,D,path
end

%判断输出参数是否为三个
if nargin==3
    min1=D(start,terminal);
    m(1)=start;
    i=1;
    path1=[ ];   
    %根据path路径一步一步跳转找到具体路径，返回path1
    while   path(m(i),terminal)~=terminal
        k=i+1;                                
        m(k)=path(m(i),terminal);
        i=i+1;
    end
    m(i+1)=terminal;
    path1=m;
end   

2.2调用函数

w = [0,7,9,inf,inf,14;
     7,0,10,15,inf,inf;
     9,10,0,11,inf,2;
     inf,15,11,0,6,inf;
     inf,inf,inf,6,0,9;
     14,inf,2,inf,9,0];
 start=1;terminal=5;
[D,path,min,path1]=floyd(w,start,terminal);
D,path,min,path1

结果：

这里介绍一下如何看path矩阵查找最短路径：比如说要查找1到5的最短路径

$\bullet$ 那么我们就要找 path(1,5)=3，所以目前路径为1->3

$\bullet$ 接着我们就要找 path(3,5)=6，所以目前路径为1->3->6

$\bullet$ 接着我们就要找 path(6,5)=5，到达终点，所以最终路径为1->3->6->5

注意：调用floyd函数的时候，同时还会输出每次插入一个顶点之后D矩阵和path矩阵的变化。

一、最短路问题

1、定义

• 设$P(u,v)$是网络加权图中从结点$u$到$v$的路径，该路径上的边权之和称为该路径的权，记为$W(P)$。从结点$u$到$v$的路径中边权最之和小者$P^{\ast }(u,v)$称为$u$到$v$的最短路径。

2、用途

• 最短路问题(short-path problem)是网络理论解决的典型问题之一，其基本内容是:若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两结点(通常是源结点和阱结点)之间总权和最小的路径就是最短路问题。该问题可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

3、常用算法

• 最短路问题常用的算法有Floyd算法、Dijkstra算法、SPFA算法等。本文主要介绍网络最短路问题的Floyd算法及其MATLAB实现。

二、理论准备

1、网络弧集和权矩阵

为了论述方便，本文借助下图，介绍网络弧集$E$和网络权矩阵$W$的概念。

(上述网络图上标的数字为各段弧的权值，该图左侧为无向网络图，右侧为有向网络图。)
对于上述无向网络图而言，网络弧集$$\begin{gathered} E_1=[(v_1,v_2),(v_1,v_4),(v_2,v_1),(v_2,v_4),(v_2,v_3), \\ (v_3,v_2),(v_3,v_4),(v_4,v_1),(v_4,v_2),(v_4,v_3)] \end{gathered}$$，
对于上述有向网络图而言，网络弧集$E_2=[(v_1,v_2),(v_1,v_4),(v_2,v_3),(v_2,v_4),(v_3,v_4)]$。
由此可见，集合$E$就是网络图的所有弧集合。
网络权矩阵$W=(W_{ij}{)}_{n\times n}$，其中,
当$(v_i,v_j)\in E$时，$W_{ij}=L_{ij}$，$L_{ij}$为弧$(v_i,v_j)$的权；
$W_{ii}=0,i=1,2,\dots ,n$;
当$(v_i,v_j)\notin E$且$i\ne j$时，$W_{ij}=inf$，($inf$为无穷大，$n$为网络节点个数)
则按上述规定，上面无向网络图和有向网络图的权矩阵分别为
$W_1=\left[\begin{array}{cccc}0& 4& inf& 5\\ 4& 0& 3& 5\\ inf& 3& 0& 2\\ 5& 5& 2& 0\end{array}\right]$，
$W_2=\left[\begin{array}{cccc}0& 4& inf& 5\\ inf& 0& 3& 1\\ inf& inf& 0& 2\\ inf& inf& inf& 0\end{array}\right]$
由于上述网络图均只有4个结点，故网络的权矩阵均为4阶矩阵。

2、Floyd算法

1.使用范围

①求任意两结点的最短路径；
②有向图、无向图、混合图。

2.基本思想

直接在网络图的权矩阵$W$中用插入顶点的方法依次递推地构造出$n$个矩阵$D(1)，D(2)，\dots ，D(n)$，$D(n)$是网络图的最短距离矩阵，同时引入一个路由矩阵记录任意两点之间的最短路径。

3.算法步骤

设$D_{ij}$为结点$v_i$到$v_j$的距离；$P_{ij}$为结点$v_i$到$v_j$路径上$v_i$的后继点；$W$为权矩阵。

• 第1步：$\forall i，j，D_{ij}=W_{ij},P_{ij}=j，k=1$；(赋初值)
• 第2步：$\forall i，j，若D_{ik}+D_{kj}<D_{ij}$，则$$\begin{gathered} D_{ij}=D_{ik}+D_{kj}， \\ {P}_{ij}=P_{ik}，k=k+1 \end{gathered}$$；(更新$D，P$)
• 第3步：重复第2步，直到$k=n+1$。

三、实例求解

1、程序实现

下面给出一个例子，网络图如下：

可以看出，上图为无向网络图，其结点个数$n=7$，权矩阵为：
$W=\left[\begin{array}{ccccccc}0& 4& 6& 5& inf& inf& inf\\ 4& 0& 1& inf& 7& inf& inf\\ 6& 1& 0& 2& 5& 4& inf\\ 5& inf& 2& 0& inf& inf& inf\\ inf& 7& 5& inf& 0& 1& 6\\ inf& inf& 4& 5& 1& 0& 8\\ inf& inf& inf& inf& 6& 8& 0\end{array}\right]$

下面利用MATLAB编写程序求其最短距离矩阵、路由矩阵以及任给两结点之间的最短距离和路径。

%% 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
%%

调用上述函数求该网络图的最短距离矩阵，并确定结点$v_1$到$v_7$的最短距离对应的路径，程序如下：

W = ones(7) * inf; %权矩阵初始化
for i = 1:7
    W(i,i) = 0;
end
W(1,2) = 4; W(1,3) = 6; W(1,4) = 5;
W(2,1) = 4; W(2,3) = 1; W(2,5) = 7;
W(3,1) = 6; W(3,2) = 1; W(3,4) = 2; W(3,5) = 5; W(3,6) = 4;
W(4,1) = 5; W(4,3) = 2; W(4,6) = 5;
W(5,2) = 7; W(5,3) = 5; W(5,6) = 1; W(5,7) = 6;
W(6,3) = 4; W(6,4) = 5; W(6,5) = 1; W(6,7) = 8;
W(7,5) = 6; W(7,6) = 8; %修改元素后W为权矩阵

pre_path = {'v1', 'v2', 'v3', 'v4', 'v5', 'v6', 'v7'}; %本例中网络图结点
 
start = 1; %起始节点为v1
stop = 7; %终止结点为v7

[D, P, dis, path] = Floyd(W, start, stop); %调用函数求解
fprintf('\n最短距离矩阵 D =\n\n')
disp(D)
fprintf('\n路由矩阵 P =\n\n')
disp(P)
fprintf('结点%s到%s的最短距离为:%f\n\n', pre_path{start}, pre_path{stop}, dis)

fprintf('结点%s到%s的最短路径为:\n\n', pre_path{start}, pre_path{stop}) %输出两给定结点间的最短路径

for i = 1:length(path)-1
    fprintf('%s', pre_path{path(i)})
    fprintf(' -> ')
end
fprintf('%s.\n', pre_path{path(length(path))})

程序运行结果如下：

最短距离矩阵 D =

     0     4     5     5    10     9    16
     4     0     1     3     6     5    12
     5     1     0     2     5     4    11
     5     3     2     0     6     5    12
    10     6     5     6     0     1     6
     9     5     4     5     1     0     7
    16    12    11    12     6     7     0


路由矩阵 P =

     1     2     2     4     2     2     2
     1     2     3     3     3     3     3
     2     2     3     4     5     6     5
     1     3     3     4     6     6     6
     3     3     3     6     5     6     7
     3     3     3     4     5     6     5
     5     5     5     5     5     5     7

结点v1到v7的最短距离为:16.000000

结点v1到v7的最短路径为:

v1 -> v2 -> v3 -> v5 -> v7.

由程序运行结果知，该无向网络图的最短距离矩阵为：
$D=\left[\begin{array}{ccccccc}0& 4& 5& 5& 10& 9& 16\\ 4& 0& 1& 3& 6& 5& 12\\ 5& 1& 0& 2& 5& 4& 11\\ 5& 3& 2& 0& 6& 5& 12\\ 10& 6& 5& 6& 0& 1& 6\\ 9& 5& 4& 5& 1& 0& 7\\ 16& 12& 11& 12& 6& 7& 0\end{array}\right]$
结点$v_1$到$v_7$的最短距离为16，其最短路径为：$v_1->v_2->v_3->v_5->v_7$。

2、一个思考

值得注意的是，上述由结点$v_1$到$v_7$的最短距离确实为16，但是，由$v_1$到$v_7$的最短距离对应的路径却不止一条(另一条为：$v_1->v_2->v_3->v_6->v_5->v_7$)，这是为什么呢？让我们回到上述算法步骤第2步，要求$\forall i，j，若D_{ik}+D_{kj}<D_{ij}$，则$D_{ij}=D_{ik}+D_{kj}$，而$D_{35}=5，D_{36}=4，D_{65}=1，所以D_{35}=D_{36}+D_{65}，$但是，由于此时$P_{35}=5$，而不能改为$P_{35}=6$，所以在程序运行结果的最短路径中没有结点$v_6$。由此可见，上述算法只能确定一条最短路径，如果某两结点之间的最短路径不止一条，该算法并不能完全找出。那么，是不是任意两结点之间必定有一条最短路径呢？答案是否定的，下面给出一个反例。

3、一个反例

下图就不存在1号顶点到3号顶点的最短路径，因为在$1->2->3->1->2->3->\dots 1->2->3$这样的路径中，每绕一次$1->2->3$这样的环，最短路径就会减少1，永远找不到最短路径。所以，Floyd算法不能解决带有"负权回路"(或者叫"负权环")的网络图，因为带有"负权回路"的网络图没有最短路径。

结束语：本文根据理解编写，如有错误或不妥之处，请指正！

声明：更详细介绍请看本人简文弗洛伊德（Floyd）算法详解 | MATLAB实现

觉得不错？关注一下，点个赞呗！

Dijkstra算法代码来源于 作者：无名小卒1990

Floyd算法，来源于 小石老师课程资源

视频学习

Dijkstra算法原理

https://www.bilibili.com/video/BV1QK411V7V4?from=search&seid=16592423916000157660

Floyd算法原理

https://www.bilibili.com/video/BV1Mt411x7CH?t=594&p=6

Dijkstra

例如上图，从D出发，到各点的距离：

D[5 9 inf 0 15 6 inf], (ACDEFG排序)

找出矩阵D[ ]中最小的值，离D最近的是A节点，再从A节点出发，到B节点的

距离为7，而5+7>9，所以D[5 9 inf 0 15 6 inf]不需要更新。A节点标记已经遍

历，并给其赋值为inf，即D[inf 9 inf 0 15 6 inf]。

继续重复找出矩阵D[ ]中最小值，重复上述操作，直到所有节点都遍历过。

Dijkstra源程序：

主函数 tulun1.m

weight = input('please enter the weight:');
start = input('please enter the start:');
terminal = input('please enter the terminal:');
          [dis, path]= Dijk(weight,start, terminal)

Dijkstra函数 Dijk.m

%% Dijkstra算法函数
function [ distance path] = Dijk( W,st,e )
%DIJK Summary of this function goes here
%   W  权值矩阵   st 搜索的起点   e 搜索的终点
n=length(W);%计算节点数
D = W(st,:);%记录起点到各点距离，此时，为初始时刻，起点到各点的距离
visit= ones(1:n); %设置visit判断节点是否访问
visit(st)=0;  %我称其为预遍历
parent = zeros(1,n);%记录每个节点的上一个节点
path =[]; %用于记录路径
for i=1:n-1 %将除了起点之外的节点都遍历一遍
    temp = []; %用于存储矩阵D的数据，并将距离本为0的换成inf，即无穷大，以免后面求最小值时，出现问题
%% 从起点出发，找最短距离的下一个点，每次不会重复原来的轨迹，设置visit判断节点是否访问
    for j=1:n
       if visit(j)
           temp =[temp D(j)]; %如果换成temp = [D(j)],将只能存储一个数据，即循环一次，数据变一次
       else
           temp =[temp inf];
       end
    end
 [value,index] = min(temp); %求temp的最小值以及最小值的位置

 visit(index) = 0;
    
%% 更新 如果经过index节点，从起点到每个节点的路径长度更小，则更新，记录前趋节点，方便后面回溯循迹
%比如从起点（1,1）出发，到达（1,2）最短距离为L1，再从（1,2）找（2,3），（2,4）的距离分别为L2、L3，若L1+L2小于从（1,1）直达（1,3）的距离，则更新
    for k=1:n
        if D(k)>D(index)+W(index,k)
           D(k) = D(index)+W(index,k);
           parent(k) = index;
        end
    end
end

%% 以下为获取最短距离，及获得路径

distance = D(e);%最短距离
%回溯法  从尾部往前寻找搜索路径
t = e;
while t~=st && t>0
 path =[t,path];
  p=parent(t);t=p;
end
path =[st,path];%最短路径
end

输入：
计算从D点到C点的最短路径

[0 7 inf 5 inf inf inf;
7 0 8 9 7 inf inf;
inf 8 0 inf 5 inf inf;
5 9 inf 0 15 6 inf;;
inf 7 5 15 0 8 9;
inf inf inf 6 8 0 11;
inf inf inf inf 9 11 0]

起点：4
终点：3

输出结果：

Floyd算法

依旧以上图为例

邻接矩阵

描述的是，各个节点之间的直接距离，如若没有直接距离，则为inf（无穷大），到自己的距离为0；

路由矩阵

描述的是节点到另一个节点的路径，需要经过的路径。

如上图，如果，需要找从A点到F点的距离，按照ABCDEF排序，A为1，F为

6，则看path(1,6)的值，为4，到达第四节点，则从第四个节点找，即从第四

行找path(4,6)，其值为6，则可知到达第六节点，即到达F节点，故其路径为

A——D——F

那么问题就在于如何求路由矩阵

Floyd 被称为“ 3 * for ”算法，即 用3个for循环求得，至于原理咋样，看一下代

码，自己理解一下，推理一下，大概就能了解，主要是在这解释有点麻烦。

Floyd源代码

主程序 tulun2.m

function [D,path,min1,path1]=floyd(a,start,terminal)
D=a;n=size(D,1);path=zeros(n,n);
for i=1:n
   for j=1:n
      if D(i,j)~=inf
         path(i,j)=j; %初始路由矩阵
      end
   end
end
%% 3*for 程序的开始

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);
            path(i,j)=path(i,k);
         end
      end
   end
end

%% 计算最短距离，以及查找最短路径
   min1=D(start,terminal);
   m(1)=start;
   i=1;
   path1=[ ];   
   while   path(m(i),terminal)~=terminal
      k=i+1;                                
      m(k)=path(m(i),terminal);
      i=i+1;
   end
   m(i+1)=terminal;
   path1=m;

输入：
计算从D点到C点的最短路径

[0 7 inf 5 inf inf inf;
7 0 8 9 7 inf inf;
inf 8 0 inf 5 inf inf;
5 9 inf 0 15 6 inf;;
inf 7 5 15 0 8 9;
inf inf inf 6 8 0 11;
inf inf inf inf 9 11 0]

起点：4
终点：3

输出