零、写在前面
本文讲述Dijkstra、Bellman-Ford、Floyd-Warshall算法
一、 分类
G（graph）：图
V（vertex）：点
E（edge）：边
一个图可以用数学语言描述为。
W（weights）：权
所以一个图也可以用数学语言描述为。
二、作图
2.1作图网站（推荐）
在线作图网站：图论作图网站
Graph Editor用法：
Undirected/Directed：有向图/无向图。
0-index/1-index：从0开始/从1开始。
Node Count：几个点。
Graph Data：图数据，第一位数字为点，第一位和第二位为边（有向），第三位为权。
Graph Data会影响到Node Count和Undirected/Directed，所以一般不用管Node Count和Undirected/Directed，只需要关注Graph Data和Undirected/Directed即可。
拖动图标可改变相对位置。
Force：固定
Draw：生产node、连线、
Edit：更改node和edge的数值
Delete：删除
Config：类似于设置
Download as png：生产图片
2.2MATLAB作图
无向图
% Matlab作无向图
% （1）无权重（每条边的权重默认为1）
% 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并生成一个图
% s 和 t 都必须具有相同的元素数；这些节点必须都是从1开始的正整数，或都是字符串元胞数组。
s1 = [1,2,3,4];
t1 = [2,3,1,1];
G1 = graph(s1, t1);
plot(G1)
% 注意哦，编号最好是从1开始连续编号，不要自己随便定义编号
s1 = [1,2,3,4];
t1 = [2,3,1,1];
G1 = graph(s1, t1);
plot(G1)
% 注意字符串元胞数组是用大括号包起来的哦
s2 = {'学校','电影院','网吧','酒店'};
t2 = {'电影院','酒店','酒店','KTV'};
G2 = graph(s2, t2);
plot(G2, 'linewidth', 2) % 设置线的宽度
% 下面的命令是在画图后不显示坐标
set( gca, 'XTick', [], 'YTick', [] );
% （2）有权重
% 函数graph(s,t,w)：可在 s 和 t 中的对应节点之间以w的权重创建边，并生成一个图
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = graph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2)
set( gca, 'XTick', [], 'YTick', [] );
有向图
% Matlab作有向图
% 无权图 digraph(s,t)
s = [1,2,3,4,1];
t = [2,3,1,1,4];
G = digraph(s, t);
plot(G)
set( gca, 'XTick', [], 'YTick', [] );
% 有权图 digraph(s,t,w)
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = digraph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2)
set( gca, 'XTick', [], 'YTick', [] ); 三、算法
3.1几个矩阵
3.1.1邻接矩阵
邻接矩阵即储存edge权值的矩阵，显然邻接矩阵是对称矩阵
3.2负权回路
如果存在一个环，环上的权值之和为负数，那么这个环就称作负权环，也叫负权回路，不管什么算法都无法求解存在负权回路的图。
含有负权值的无向图都是负权回路。
一般无向图不存在负权值，出现负权值往往都在有向图中。
3.3迪杰斯特拉算法Dijkstra
两点之间的最短路径，不能处理负权重。
3.4贝尔曼福特算法Bellman-Ford
两点之间的最短路径，可处理存在负权值的有向图。
3.5弗洛伊德算法Floyd-Warshall
输出任意两点间的最短路径
四、代码
4.1两点之间的最短路径
包括Dijkstra算法和Bellman-Ford算法
[P,d] = shortestpath(G,start,end [,'Method',algorithm])
%功能：
返回图G中start节点到end节点的最短路径。
%输入参数：
%G：输入图（graph对象|digraph（有向图）对象）。
%start起始的节点。
%end目标的节点。
%[,'Method',algorithm]可选参数，表示计算最短路径的算法。一般默认为'auto'，MATLAB会根据我们的图选择合适的算法。
%输出参数：
%P：最短路径经过的节点。
%d：最短路径。
%Method
%'auto'自动选择算法。
%'unweighted'广度优先算法，所有权值都为1。
%'positive'Dijkstra算法，要求所有权值均为非负数。
%'mixed'bellman-ford算法，要求图不存在负权回路。
4.2任意两点的最短路径
Floyd算法
d = distance(G [,'Method',algorithm])
D = distances(G) %注意：该函数matlab2015b之后才有哦
D(1,2) % 1 -> 2的最短路径
D(9,4) % 9 -> 4的最短路径
% 找出给定范围内的所有点 nearest(G,s,d)
% 返回图形 G 中与节点 s 的距离在 d 之内的所有节点
[nodeIDs,dist] = nearest(G, 2, 10) %注意：该函数matlab2016a之后才有哦4.3找出给定范围内所有的点
% 找出给定范围内的所有点 nearest(G,s,d)
% 返回图形 G 中与节点 s 的距离在 d 之内的所有节点
% nodelDs是符合条件的节点
% Dist是这些节点与s的距离
[nodeIDs,dist] = nearest(G, 2, 10) %注意：该函数matlab2016a之后才有哦五、实例
求0到4的最小路径。
由于MATLAB中shortestpath函数需要从1开始编号，所以把每一位数字往前进一个。
除此之外，还能直接将0变为9，效果一样。
问题就变成了求从1到5的最小路径。
可得邻接矩阵为
然后对着这个图，把数据保存在G（图）中，然后计算即可。
为了不出现错误，我们需要手写出G三遍，防止出现错误。
%质朴版求解1
s=[1 1 2 2 3 3 3 4 4 5 6 7 7 8];
t=[2 8 3 8 4 9 6 5 6 6 7 8 9 9];
w=[4 8 8 3 7 2 4 9 14 10 2 6 6 1];
%可以根据邻接矩阵准确获得，如果是无向图，还可以遮住对角线及其以下部分进行输入数据。
G=graph(s,t,w);
[P,d]=shortestpath(G,1,5)
%质朴版求解2
s=[1 1 2 2 3 3 3 4 4 5 6 7 7 8];
t=[2 8 3 8 4 9 6 5 6 6 7 8 9 9];
w=[4 8 8 3 7 2 4 9 14 10 2 6 6 1];
G=graph(s,t,w);
D = distance(G)
D(1,5)
%豪华版求解(包含美观的图片)
s=[1 1 2 2 3 3 3 4 4 5 6 7 7 8];
t=[2 8 3 8 4 9 6 5 6 6 7 8 9 9];
w=[4 8 8 3 7 2 4 9 14 10 2 6 6 1];
G=graph(s,t,w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2)
set( gca, 'XTick', [], 'YTick', [] );
[P,d]=shortestpath(G,1,5)
% 在图中高亮我们的最短路径
myplot = plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2); %首先将图赋给一个变量
highlight(myplot, P, 'EdgeColor', 'r') %对这个变量即我们刚刚绘制的图形进行高亮处理（给边加上r红色）