前N条最短路算法matlab源代码.doc

前N条最短路可以通过第归地调用最短路算法实现，具体算法可以查找相关文献，下面是一个实例。，附有详细的注释，希望对你有所帮助。 %满足时延约束的前N条最短路算法%Delay------------当前时延邻接矩阵%Delta------------延时约束%Source-----------源节点%End--------------目的节点%Routes-----------升序排列的最短路径集，用细胞结构存储%Len--------------升序排列的各路径长度（时延）function [Routes,Len]=N_floyd(Delay,Delta,Source,End)Len=[];%升序排列的各路径时延Routes=cell(1,1);%升序排列的最短路径集，用细胞结构存储Net=cell(1,1);%升序排列的网络拓扑，用延时邻接矩阵表示Net{1}=Delay;%Delay存储当前网络%第一次调用floyd算法，得最短路，加入路径集[D,path]=floyd(Delay);[L,R]=router(D,path,Source,End);%R存储当前路径，L存储当前路径长度i=1;%当前路径序号Len(i)=L;Routes{i}=R;while L=Delta%只要当前路径长度不超过约束，就继续搜寻次短路??? Sub_len=[];%当前子图的最短路径长度??? Sub_routes=cell(1,1);%当前子图的最短路径??? Sub_net=cell(1,1);%当前子图的邻接矩阵??? %计算当前子图及其最短路径??? J=length(R)-1;%存储当前路径的跳数??? for j=1:J??????? Dy=Delay;??????? Dy(R(j),R(j+1))=inf;??????? Dy(R(j+1),R(j))=inf;??????? Sub_net{j}=Dy;??????? [DD,pp]=floyd(Dy);??????? [Sub_len(j),Sub_routes{j}]=router(DD,pp,Source,End);??? end??? %删除路径长度大于约束的路径以及空路径??? S_len=[];??? S_routes=cell(1,1);??? S_net=cell(1,1);??? ii=1;??? for j=1:J??????? RR=Sub_routes(j);??????? if (Sub_len(j)=Delta)(length(RR)~=0)??????????? S_net{ii}=Sub_net{j};??????????? S_routes{ii}=Sub_routes{j};??????????? S_len(ii)=Sub_len(j);??????????? ii=ii+1;??????? end??? end??? Sub_net=S_net;??? Sub_routes=S_routes;??? Sub_len=S_len;????? %将当前子图结构，最短路径，路径长度加入到总路径集中??? Net=[Net Sub_net];??? Routes=[Routes Sub_routes];??? Len=[Len,Sub_len];??? %对总路径集进行升序排列??? J=length(Len);??? for j=1:(J-1)??????? for k=(j+1):J??????????? if Len(k)Len(j)??????????????? temp_len=Len(j);??????????????? temp_routes=Routes{j};??????????????? temp_net=Net{j};??????????????? Len(j)=Len(k);??????????????? Len(k)=temp_len;??????????????? Routes{j}=Routes{k};??????????????? Routes{k}=temp_routes;??????????????? Net{j}=Net{k};??????????????? Net{k}=temp_net;??????????? end??????? end??? end??? %修改当前路径??? i=i+1;??? Delay=Net{i};??? R=Routes{i};??? if ilength(Len)??????? L=inf;??? else???????