目录

五、图论模型

1.迪杰斯特拉（Dijkstra）算法、贝尔曼-福特（Bellman-Ford）算法

2.弗洛伊德（Floyd）算法

六、分类模型

1.逻辑回归

2.Fisher线性判别分析

---

五、图论模型

图论模型主要解决最短路径问题，根据图的不同，对应采用迪杰斯特拉（Dijkstra）算法、贝尔曼-福特（Bellman-Ford）算法、弗洛伊德算法（Floyd）。

Matlab代码：

% Matlab中的图节点要从1开始编号
s = [9 9 1 1 2 2 2 7 7 6 6  5  5 4];
t = [1 7 7 2 8 3 5 8 6 8 5  3  4 3];
w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9];
G = graph(s,t,w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) 
set( gca, 'XTick', [], 'YTick', [] );  

%% Matlab作无向图% （1）无权重（每条边的权重默认为1）
% 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并生成一个图
% s 和 t 都必须具有相同的元素数；这些节点必须都是从1开始的正整数，或都是字符串元胞数组
% 注意：编号从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', [] );  

1.迪杰斯特拉（Dijkstra）算法、贝尔曼-福特（Bellman-Ford）算法

        迪杰斯特拉算法是基于贪婪算法的思想，从起点出发逐步找到通向终点的最短距离。

将所有顶点分为两个集合：已选顶点集合，未选顶点集合

（将起点加入已选顶点集合，更新列表信息）

①更新列表信息，当每加入一个新的顶点，则更新所有位于未选顶点集合中与该顶点相连的顶点的距离信息：当新节点的距离加边的权值小于对应节点当前的距离时，则更新对应节点距离和父列表的信息，否则维持不变；

②扫描距离列表信息，找到所有未选顶点集合中距离最小的顶点；

③添加改顶点到已选顶点集合，作为新的节点重复

注意：改节点总是处在靠近已选顶点集合的边缘位置（由近及远）

 

 

 Matlab代码：

s = [9 9 1 1 2 2 2 7 7 6 6  5  5 4];
t = [1 7 7 2 8 3 5 8 6 8 5  3  4 3];
w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9];
G = graph(s,t,w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) 
set( gca, 'XTick', [], 'YTick', [] );  [P,d] = shortestpath(G, 9, 4)  % 高亮最短路径
myplot = plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2);
highlight(myplot, P, 'EdgeColor', 'r') 

 Matlab代码：

s = [9 9 1 1 2 2 2 7 7 6 6  5  5 4];
t = [1 7 7 2 8 3 5 8 6 8 5  3  4 3];
w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9];
G = graph(s,t,w);% 任意两点的最短路径矩阵
D = distances(G)  % 1 -> 2的最短路径
D(1,2)% 9 -> 4的最短路径  
D(9,4)  

 Matlab代码：

s = [9 9 1 1 2 2 2 7 7 6 6  5  5 4];
t = [1 7 7 2 8 3 5 8 6 8 5  3  4 3];
w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9];
G = graph(s,t,w);% 找出给定范围内的所有点  
% nearest(G,s,d)：返回图形 G 中与节点 s 的距离在 d 之内的所有节点
[nodeIDs,dist] = nearest(G, 2, 10) 

---

2.弗洛伊德（Floyd）算法

        弗洛伊德算法是基于动态规划的思路，通过循环迭代的方法同时找出任意两个顶点间的最短距离。

 

---

六、分类模型

        分类模型可划分为二分类模型和多分类模型：

对于二分类模型，主要有逻辑回归和Fisher线性判别分析两种分类算法；

对于多分类模型，主要进行SPSS中的多分类线性判别分析和多分类逻辑回归的操作。

1.逻辑回归

 

Logistic回归也可用于多分类：

 

---

2.Fisher线性判别分析

 

---

内容原作者：数学建模清风

学习用途，仅作参考。