基于Dijkstra算法的农村医疗点选址及道路规划

% 定义村庄数量 N = 100;

% 读取村庄位置数据 data = readmatrix('位置.xlsx');

% 读取连接道路数据 dataS1 = readmatrix('连接道路.xlsx');

% 检查村庄编号是否都在1到N之间，若不是则删除 data(all(data(:,1) < 1 | data(:,1) > N, 2), :) = []; dataS1(all(dataS1(:,2) < 1 | dataS1(:,2) > N | dataS1(:,3) < 1 | dataS1(:,3) > N, 2), :) = [];

% 构建邻接矩阵 G = Inf(N); for i = 1:size(dataS1 , 1) start_node = dataS1(i, 2); end_node = dataS1(i, 3); G(start_node, end_node) = norm(data(start_node, :) - data(end_node, :)); G(end_node, start_node) = G(start_node, end_node); end

% 定义医疗点数量 K = 3;

% 初始化医疗点位置 X0 = [2000, 2000; 8000, 8000; 14000, 14000];

% 进行优化 options = optimoptions('fminunc', 'Algorithm', 'quasi-newton', 'Display', 'off'); X = fminunc(@(X) objective_fun(G, X, K), X0, options);

% 计算最小距离总和 S1 = objective_fun(G, X, K);

% 输出结果 disp('医疗点位置：'); disp(X); fprintf('各村庄村民到医疗点的距离总和S1为：%f\n', S1);

% 计算每个村庄到最近医疗点的距离 D = Inf(N, K); for k = 1:K [~, D(:, k)] = dijkstra(G, X(k, 1), X(k, 2)); end [~, I] = min(D, [], 2);

% 绘制结果图 figure; hold on; for i = 1:size(dataS1, 1) if I(dataS1(i, 2)) == I(dataS1(i, 3)) plot(data(dataS1(i, [2, 3]), 2), data(dataS1(i, [2, 3]), 3), 'r-'); else plot(data(dataS1(i, [2, 3]), 2), data(dataS1(i, [2, 3]), 3), 'k-'); end end for k = 1:K plot(X(k, 1), X(k, 2), 'bo', 'MarkerFaceColor', 'b'); plot(data(I == k, 2), data(I == k, 3), 'rx'); end axis equal; title('最优解可视化');

% 计算需要维修的道路 E = []; D_new = Inf(N, K); for k = 1:K [~, D_new(:, k), E_new] = dijkstra(G, X(k, 1), X(k, 2)); E = union(E, E_new, 'rows'); end S2 = sum(sum(D_new < D)); fprintf('需要维修的道路总里程为：%f\n', S2);

% 绘制维修道路图 figure; hold on; for i = 1:size(dataS1, 1) if any(ismember(E, dataS1(i, :), 'rows')) plot(data(dataS1(i, [2, 3]), 2), data(dataS1(i, [2, 3]), 3), 'r-'); else plot(data(dataS1(i, [2, 3]), 2), data(dataS1(i, [2, 3]), 3), 'k-'); end end for k = 1:K plot(X(k, 1), X(k, 2), 'bo', 'MarkerFaceColor', 'b'); plot(data(I == k, 2), data(I == k, 3), 'rx'); end axis equal; title('维修道路可视化');

% 定义目标函数 function S = objective_fun(G, X, K) D = Inf(size(G)); for k = 1:K [~, D(:, k)] = dijkstra(G, X(k, 1), X(k, 2)); end S = sum(min(D, [], 2)); end

% Dijkstra算法实现 function [D, P, E] = dijkstra(G, s, t) N = size(G, 1); D = Inf(N, 1); P = zeros(N, 1); E = []; Q = 1:N; D(s) = 0; while ~isempty(Q) [~, u] = min(D(Q)); u = Q(u); Q(Q == u) = []; if u == t break; end V = find(G(u, :) < Inf); for i = 1:length(V) v = V(i); if ismember(v, Q) d = D(u) + G(u, v); if d < D(v) D(v) = d; P(v) = u; E = [E; u, v]; end end end end end