当前位置：首页 > news >正文

图与网络模型

news 来源：原创 2025/7/13 17:35:47

图的基本概念

例题：比赛的安排

MATLAB作图

最短路径模型

Dijkstra算法步骤

最短路径的Dijkstra算法示例

Dijkstra算法的Matlab函数

最短路径的Floyd算法模型

最短路径的Floyd算法步骤

Floyd算法的Matlab函数

图的基本概念

图G是一个二重组： G=〈V, E〉，其中V是非空结点（或顶点）集合， E是边集合（可以为空集）。图G的边e是一个结点偶对： [a, b]，其中a,b=V. e可以是有序的，称为有向边，简称为弧， a称为弧e 的始点，b称为e 的终点，统称为e 的端点；称e关联于结点a和b，或称结点a和b是邻接的；关联于同一结点的一条边称为自回路（环）。 e也可以是无序的，称为无向边，简称棱。每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图。

例题：比赛的安排

有5名运动员参加游泳比赛，表7.1.1给出每位运动员参加比赛的项目，问如何安排比赛，才能使每位运动员都不连续参加比赛.

核心：定义好点和边！！

解：分别用顶点v1, v2, v3, v4, v5表示比赛项目. 若两项比赛没有同一名运动员参加，则可以把这两个项目紧排在一起，用一条边把相应的两个顶点连起来；如图1，找出包含所有顶点的基本路径，就找出了满足条件的一种安排. 如： S={v2, v3, v4, v1, v5}.

图1

运动员

50m仰泳

50m蛙泳

100m蝶泳

100m自由泳

200m自由泳

甲

√

乙

√

丙

√

丁

√

戊

√

图论作图网站：https://csacademy.com/app/graph_editor/

MATLAB作图


% 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并生成一个图                      G1 = graph(s1, t1);
plot(G1)% 函数graph(s,t,w)：可在 s 和 t 中的对应节点之间以w 的权重创建边，并生成一个图 G2 = graph(s2, t2);
plot(G2, 'linewidth', 2)  % 设置线的宽度
% 下面的命令是在画图后不显示坐标
set( gca, 'XTick', [], 'YTick', [] );上面都是无向图
要做出有向图，只需要将graph改为digraph就行了。

最短路径模型

最短路：对赋权有向图D中任两结点u和v ，若在从u到 v 的所有路径中能找到一条路径，使得该路径所有弧的权数（可以是时间，距离或费用）之和最小，则称这条路为从u到v 的最短路.

最短路问题是网络优化中的基本问题，在交通运输、设备更新、线路设计等方面有广泛应用. 原理：网络图中，若{v1, v2, …, vn-1, vn}是从v1 到vn 的最短路径，则{v1, v2, …, vn-1}也必然是从v1 到vn-1 的最短路径.

Dijkstra算法步骤

最短路径的Dijkstra算法示例

图2是一个石油流向的管网示意图， v1代表石油开采地， v7代表石油汇集站，线旁的数字表示管线的长度，现在要从v1地调运石油到v7地，怎么选择管线可使路径最短？

图2

求解步骤

Dijkstra算法的Matlab函数


function [d Q] = shorta(T)pp(1:length(T)) = 0;   pp(1) = 1;   Q = 1;
M = max(T(:));   d(1:length(T)) = M;   d(1) = 0;   K = 1;
while sum(pp)<length(T)tt = find(pp==0);   % 找出未标记的点d(tt) = min(d(tt), d(K)+T(K,tt));ttt = find(d(tt)==min(d(tt)));K = tt(ttt(1));   pp(K) = 1;   Q = [Q, K];end

T = [0, 20, 15, inf, inf, inf, inf; inf, 0, inf, 8, 24, inf, inf; ...
inf, inf, 0, 10, inf, 6, inf; inf, inf, inf, 0, 10, 8, inf; ...inf, inf, inf, inf, 0, inf, 11; inf, inf, inf, inf, inf, 0, 20];
[d Q] = shorta(T)

运行结果如下： d = 0 20 15 25 35 21 41

Q = 1 3 2 6 4 5 7

由运行结果可以看出从起点到各个点的最短路长，还可以得到标号的顺序，即v1, v3, v2, v6, v4, v5, v7 。但Dijkstra算法只适用于权数为非负实数的情况，若权数有负值，则可用下面的逐次逼近法。

function dis = Dijkstra_all_minpath(matr, start)% matr：邻接矩阵，start：起始节点（MATLAB的索引从1开始）n = size(matr, 1); % 图中节点的数量dis = inf(1, n); % 初始化距离数组为无穷大dis(start) = 0; % 起始节点到自己的距离为0temp = dis;temp(start) = 0; % 临时数组将访问过的节点设置为0visited = false(1, n); % 访问标记数组，初始均为falsevisited(start) = true; % 标记起始节点为已访问parent = start * ones(1, n); % 用于存储路径信息while sum(visited) < n[~, i] = min(temp); % 找到当前距离最小的节点的索引temp(i) = inf; % 将其临时距离设置为无穷大（表示已访问）for j = 1:nif ~visited(j) && (dis(i) + matr(i, j)) < dis(j)dis(j) = dis(i) + matr(i, j); % 更新到节点j的最短距离temp(j) = dis(j); % 更新临时距离parent(j) = i; % 将节点j的父节点设置为iendendvisited(i) = true; % 标记节点i为已访问% 重建从起点到节点i的路径path = [];current = i;while parent(current) ~= startpath = [parent(current), path];current = parent(current);endpath = [start, path, i]; % 添加起点和当前节点到路径中% 打印路径fprintf('%d:', i);fprintf('%d->', path(1:end-1));fprintf('%d\n', path(end));end
end% 示例邻接矩阵
a = [0, 1, 2, inf, 7, inf, 4, 8;1, 0, 2, 3, inf, inf, inf, 7;2, 2, 0, 1, 5, inf, inf, inf;inf, 3, 1, 0, 3, 6, inf, inf;7, inf, 5, 3, 0, 4, 3, inf;inf, inf, inf, 6, 4, 0, 6, 4;4, inf, inf, inf, 3, 6, 0, 2;8, 7, inf, inf, inf, 4, 2, 0];% 调用Dijkstra算法函数并打印结果
start = 4; 
dis = Dijkstra_all_minpath(a, start);
fprintf('从v%d到所有顶点的最短距离为：', start);
disp(dis);

最短路径的Floyd算法模型

设图 G = (V, E) , wij 表示边(vi , vj ) 上的权,若 vi 和vj 不相邻，则 wij = +无穷；用 dij 表示顶点 vi 到顶点 vj 的最短距离，则对于任何一个顶点 vk eV，从顶点 vi 到顶点 vj 的最短路或者经过 v k ，或者不经过 vk ，可利用动态规划思想来比较 dij 和 dik + dkj 的大小. 若 dij > dik + dkj ，则令 dij = dik + dkj ，保持 dij 为顶点 vi 到顶点 vj 的最短距离. 重复这一过程直到搜索完所有顶点 vk ，此时 dij 就是顶点 vi 到顶点 vj 的最短距离.

最短路径的Floyd算法步骤

step 1. 输入图 G 的权矩阵 W，对所有 i, j，dij = wij ， k = 1 ；

step 2. 更新 dij ，对所有 i , j ，若 dik + dkj < dij ，则令 dij = dik + dkj ；

step 3. 若dii < 0，则存在一条含顶点 vi 的负权值回路，算法终止；或 k = n 算法终止；否则令 k = k +1，并转step 2.

Floyd算法的Matlab函数


function [P, u] = f_path(W)
% W表示权值矩阵;   P表示最短路;   % u表示最短路的权和
n = length(W);   U = W;   k = 1;  % Step1 初始化
% Step2
while  k<=nfor  i=1:nfor j=1:nif U(i, j) > U(i, k) + U(k, j)U(i, j) = U(i, k) + U(k, j);end;   end;   endk = k+1;
endu = U(1, n);% 输出最短路的顶点
P1 = zeros(1,n);   k = 1;   P1(k) = n;   V = ones(1,n)*inf;   kk = n;
while  kk~=1for  i=1:nV(1, i) = U(1, kk) - W(i, kk);if V(1, i)==U(1, i)P1(k+1) = i;   kk = i;   k = k+1;end;   end;
end
k = 1;   wrow = find(P1~=0);
for j=length(wrow) : (-1) : 1P(k) = P1(wrow(j));       k = k+1;endW = [0, 20, 15, inf, inf, inf, inf; inf, 0, inf, 8, 24, inf, inf; ...inf, inf, 0, 10, inf, 6, inf; inf, inf, inf, 0, 10, 8, inf; ...inf, inf, inf, inf, 0, inf, 11; inf, inf, inf, inf, inf, 0, 20; ...inf, inf, inf, inf, inf, inf, inf];
[P, u] = f_path(W)

运行结果如下：
P = 1 3 6 7
Q = 41
即从v1 到v7 的最短路为 v1->v3-> v6->v7 ，最短路长为41.

图的基本概念

例题：比赛的安排

MATLAB作图

最短路径模型

Dijkstra算法步骤

最短路径的Dijkstra算法示例

Dijkstra算法的Matlab函数

最短路径的Floyd算法模型

最短路径的Floyd算法步骤

Floyd算法的Matlab函数

相关文章：