最短路径问题是图论研究中的一个经典算法问题。
那什么是图论呢？
简单点说，如果我们能用点表示某事物，用点与点之间的线表示事物之间的联系，就可以把这件事物抽象地用图的方式表示出来。而运用抽象的方式将问题抽象为图，并为之建立的数学模型，就是图论。
专业点说，图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型。
至此，我们就可以运用图论的概念、理论和方法，对能抽象为图的问题进行求解。
著名瑞士数学家欧拉的哥尼斯堡七桥问题就是对图论最经典的应用。
七桥问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。
欧拉将七桥问题抽象出来，把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。并由此得到了如上图中右图一样的几何图形。
分别用A、B、C、D四个点表示为哥尼斯堡的四个区域。这样著名的“七桥问题”便转化为是否能够用一笔不重复的画出过此七条线的问题。
除此之外还有邮递员问题、选址问题、铁路造价最低问题等，涉及到经济管理、计算机科学、交通工程、通信工程、系统工程、运筹学、信息论、控制理论等众多领域等诸多领域。
所以说，学好图论，学到就是赚到。今天就和大家共同学习一下图论的经典算法问题之一——最短路径问题。
在正式开始学习之前，难免有的同学对图的定义和术语不了解，可以先行观看第二篇文章。
最短路径问题根据初始条件的不同，可分为五种情况：
最短路径问题， 旨在寻找图中两点之间的最短路径。
确定起点的最短路径问题 ，即已知起点，求最短路径的问题。
确定终点的最短路径问题 ，与确定起点的问题相反，该问题是已知终点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题，即已知起点和终点，求两点之间的最短路径。
全局最短路径问题，求图中任意两点间的最短路径。
也可以合并为一种情况——全局最短路径问题，只要求出全局最短路径，那其余四种情况也已经包含在内了。
而计算最短路径的常用算法一共有两种：狄克斯特拉（Dijkstra）算法、弗洛伊德（Floyd）算法。
Dijkstra算法
其研究的是从初始点到其他每一结点的最短路径，解决的是有向图中最短路径问题。其主要特点是以初始点为中心向外层层扩展，直到扩展到终点为止。
具体算法思想大家可以课后自行学习，这里先把程序摆出来让大家学会。
下面的Dijkstra.m函数实现的是给出各边权值的邻接矩阵、起点、终点，求最短距离和路径。
如果要实现最短路径的五种情况，只需添加两个for循环，即可算出任意两点间的最短距离和最短路径。
%% 测试部分
clc,clear
w=zeros(6);
w(1,2)=50;w(1,4)=40;w(1,5)=25;w(1,6)=10;
w(2,3)=15;w(2,4)=20;w(2,6)=25;
w(3,4)=10;w(3,5)=20;
w(4,5)=10;w(4,6)=25;
w(5,6)=55;
w=w+w’; % 此处考虑为无向图，如为有向图，则把所有路径权值输入邻接矩阵
w(w==0)=inf;%无路径的点对之间赋值为无穷大
distance=zeros(size(w,1));
path=cell(size(w,1));
for i=1:size(w,1)
for j=i+1:size(w,1)
[distance(i,j),path{i,j}]=Dijkstra(w,i,j);
end
end
%% Dijkstra算法（另存为Dijkstra.m文件）
% 输入的w为存放各边权值的邻接矩阵，start搜索的起点，terminal搜索的终点
function [distance,path] =Dijkstra(w,start,terminal)
n=length(w);%节点数
D = w(start,:);
visit= ones(1:n); visit(start)=0;
parent = zeros(1,n);%记录每个节点的上一个节点
path =[];
for i=1:n-1
temp = [];
%从起点出发，找最短距离的下一个点，每次不会重复原来的轨迹，设置visit判断节点是否访问
for j=1:n
if visit(j)
temp =[temp D(j)];
else
temp =[temp inf];
end
end
[~,index] = min(temp);
visit(index) = 0;
%更新 如果经过index节点，从起点到每个节点的路径长度更小，则更新，记录前趋节点，方便后面回溯循迹
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(terminal);%最短距离
%回溯法 从尾部往前寻找搜索路径
t = terminal;
while t~=start && t>0
path =[t,path];
p=parent(t);t=p;
end
path =[start,path];%最短路径
end
Floyd算法
其研究的是任意两结点之间的最短路径，可以正确处理有向图或有负权的有向图（但不可存在负权回路)的最短路径问题。
在Floyd算法中一般有两个矩阵，一个距离矩阵D，一个路由矩阵R，其中距离矩阵用于存储任意两点之间的最短距离，而路由矩阵则记录任意两点之间的最短路径信息。
其思想是：如果可以从一个点进行中转，就进行比较从这个点中转和不中转的距离，存储距离小的情况，并更新距离矩阵和路由矩阵。
下面给大家展示程序，包括计算距离矩阵和路由矩阵的Floyd.m函数与打印Floyd路由矩阵的FloydDisplayPath.m路径函数。
%% 测试部分
a = [0 2 6 4;
inf 0 3 inf;
7 inf 0 1 ;
5 inf 12 0];
[d,r]=floyd(a);
for i = 1 : 4
for j = 1 : 4
FloydDisplayPath(r, i, j);
end
end
%% 弗洛伊德（Floyd）算法（另存为Floyd.m文件）
% 采用floyd算法计算图a中每对顶点最短路
% d是矩离矩阵
% r是路由矩阵
function [d,r]=Floyd(a)
n=size(a,1);
% 初始化距离矩阵
d=a;
% 初始化路由矩阵
for i=1:n
for j=1:n
r(i,j)=j;
end
end
% Floyd算法开始
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);
r(i,j)=r(i,k);
end
end
end
end
%% 打印Floyd路由矩阵的路径函数（另存为FloydDisplayPath.m文件）
function FloydDisplayPath(route, start, dest)
% 打印出任意两点之间的最短路径
% route : 路由表
% start : 起点index
% dest : 终点index
while 1
if(route(start, dest) ~= dest)
fprintf(‘V%s -> ‘, num2str(start));
start = route(start, dest);
else
fprintf(‘V%s -> ‘, num2str(start));
fprintf(‘V%s\n’, num2str(dest));
break;
end
end
end
