【漫漫科研路\Matlab】最小跳数最大权重算法

本文主要是介绍【漫漫科研路\Matlab】最小跳数最大权重算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

上周，实验室国际友人让我帮忙实现满足条件的最小跳数最大权重的算法。他的具体问题如下：
给定一个权重图（如下图所示），给出节点之间最小跳数最大权重矩阵，其中任意两点之间跳数小于等于3，否则权重为inf。

如图所示， A到F的最小跳数为2：A-C-F和A-E-F，权重(这里权重表示为所有路径上的权重乘积，当然也可以稍加修改变成权重和)分别为4*1=4、3*4=12。因此A到F的最小跳数最大权重为12，路径为A-E-F。下面给出了具体的代码实现：
主要有两个文件，测试脚本文件main.m和dijkstra_all.m函数文件：
1、测试脚本文件main.m

clear all
clc   
AdjMatrix=[0 inf 4 6 3 inf;inf 0 3 2 inf 4;4 3 0 1 1 1;6 2 1 0 inf inf;3 inf 1 inf 0 4;inf 4 1 inf 4 0;];AdjMatrix1=AdjMatrix;% weight matrix
IND=AdjMatrix<inf&AdjMatrix>0;
AdjMatrix(IND)=1;% adjacent matrixResMatrix=zeros(size(AdjMatrix));%ouput matrix: the weights between each pair of nodes
N=length(AdjMatrix);% the number of nodesfor i=1:Nfor j=1:Nif(i==j)ResMatrix(i,j)=0;else[sp, spcost]=dijkstra_all(AdjMatrix, i, j);% condition 1: find all the minimum hops    temp_num=sum(sp(1,:)>0);if(temp_num<=4)% condition 2: the number of the minimum hop is less than 3temp=ones(1,size(sp,1));% the number of the minimum hopsfor m=1:size(sp,1)for k=1:temp_num-1temp(m)=temp(m)*AdjMatrix1(sp(m,k),sp(m,k+1));% Calculate the weights of all the minimum hops, change * to + for the sum of the weights endendResMatrix(i,j)=max(temp);% condition 3: choose the maximum weight among all the minimum hopselseResMatrix(i,j)=inf; % the number of the minimum hop is larger than 3endendend
endResMatrix

2、dijkstra_all.m函数文件（sp为所有的最小跳数路径集合，spcost为最小跳数）

function [sp, spcost] = dijkstra_all(AdjMatrix, s, d)
% This is an implementation of the dijkstra algorithm, wich finds the 
% minimal cost path between two nodes. It is used to solve the problem on 
% possitive weighted instances.% the inputs of the algorithm are:
%AdjMatrix: the adjacent matrix of a graph
% s: source node index;
% d: destination node index;
n=size(AdjMatrix,1);
S(1:n) = 0;     %s, vector, set of visited vectors
dist(1:n) = inf;   % it stores the shortest distance between the source node and any other node;
prev = zeros(50,n); % Previous node, informs about the best previous node known to reach each  network node, 50 should be changed when the path is long.
count(1:n)=0;dist(s) = 0;while sum(S)~=ncandidate=[];for i=1:nif S(i)==0candidate=[candidate dist(i)];elsecandidate=[candidate inf];endend[u_index u]=min(candidate);S(u)=1;for i=1:nif(dist(u)+AdjMatrix(u,u)+AdjMatrix(u,i))<dist(i)dist(i)=dist(u)+AdjMatrix(u,u)+AdjMatrix(u,i);prev(:,i)=prev(:,i).*0;prev(1,i)=u;count(i)=1;elseif ((dist(u)+AdjMatrix(u,u)+AdjMatrix(u,i))==dist(i))&&(dist(i)~=inf)&&(u~=i)        if count(i)<49count(i)=count(i)+1;endprev(count(i),i)=u;           endendend
endsp=[];
stack=[];
num=[];
%backup
stack = [d,zeros(1,9)];
num=[1,zeros(1,9)];
spcost = dist(d);while stack(1) ~= 0if stack(1)==s%record the pathsp=[sp;stack];%popstack=[stack(2:10),0];% the first element of stack is outnum=[num(2:10),0];continue;endtmp=prev(num(1),stack(1));if tmp==0%popstack=[stack(2:10),0];num=[num(2:10),0];continue;else%pushnum(1)=num(1)+1;stack=[tmp,stack(1:9)];num=[1,num(1,1:9)];endend

运行main脚本文件，可得最小跳数最大权重矩阵如下：

这篇关于【漫漫科研路\Matlab】最小跳数最大权重算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---