精华内容
下载资源
问答
  • 经典Dijkstra算法Matlab实现
    2021-04-19 02:17:10

    下面给出了我用Matlab实现的Dijkstra算法(函数形式)。

    function [minD,path]=dijkstra(w,start,terminal)

    %求单源最短路径的Dijkstra算法(图论)

    %调用格式:[min,path]=dijkstra(w,start,terminal)

    %输入:

    % w------------图的带权邻接矩阵(可以是有向图,对于无向图,它应该是

    % 一个对角线为0的对称阵。权值必须都是正的,如果两点之间

    % 没有边直连,则边权为无穷大)

    % start--------起点标号

    % terminal-----终点标号

    %输出:

    % minD---------起点到终点的最短路径的距离

    % path---------是一个向量,存储了从起点到终点的路径,即经过的节点标号

    n = size(w,1); %节点数量

    %% 初始化

    sptSet = zeros(1, n); % 集合S存放已经找到最短路径的节点,

    % 1表示已找到,0表示未处理过的

    dist = zeros(1, n); % dist存放源点到其他节点的最短路径

    f = zeros(1, n); % f存放源点到该点的最短路径中的前一个节点

    f(start) = start; % 源点到它本身的最短路径的前一个节点当然是其本身

    % 初始化最短路径长度

    for i = 1:n

    dist(i) = inf;

    end

    dist(start) = 0; % 源点到它自己的距离当然是0

    %% 主循环

    while sum(sptSet) < n

    % 从集合sptSet外的节点集中选择源点到其路径最短的

    mindis = inf;

    for i = 1:n

    if sptSet(i)==0 && dist(i)<=mindis % 注意这里必须取小于等于,

    % 否则对于有向图就无能为力了

    mindis = dist(i);

    u = i;

    end

    end

    % 将节点加入到集合S中

    sptSet(u) = 1;

    % 根据被选中的点u更新dist

    for v = 1:n

    % 当满足:(1)节点v不在集合sptSet中;(2)u,v相邻且可达;

    % (3)源点到u的最短距离+(u,v)的权值比原先源点到v的最短距离短

    if ( ~sptSet(v) && w(u, v)~=inf && dist(u)+w(u,v)

    dist(v) = dist(u) + w(u,v);

    f(v) = u; % 源点到v的最短路径中前一个节点是u

    end

    end

    end

    %% 输出结果

    if nargin == 2 % 如果只输入2个参数,则输出源点到所有节点的最短路径和最短路径树

    minD = dist;

    path = f;

    else % 否则(输入了终点),输出源点到终点的最短路径和经过的节点

    minD = dist(terminal);

    if minD ~= inf % 如果可达再来寻找路径

    % 从f中回溯

    path(1) = terminal;

    forward = 1;

    while path(forward) ~= start

    path(forward+1) = f(path(forward));

    forward = forward + 1;

    end

    %调整顺序

    L = length(path);

    path = path(L:-1:1);

    else

    path = 0; % 表示不可达

    end

    end

    参考:

    http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

    更多相关内容
  • matlab中实现网络最短路径求解,最经典的最短路径求解方法,以网络邻接矩阵为输入变量,输出任意节点间的最短路径。
  • Dijkstra算法matlab代码

    2021-04-19 05:25:49
    一:求解最短路径的Dijkstra算法二:Dijkstra算法伪代码Vs(iN,2): Vs(iN,1)==1表示顶点iN在集合Vs,Vs(iN,2)存储到iN最短距离。Ay(NN,NN): 领接矩阵存储边权。 不可行的路记为无穷大。By(NN,NN): 记录到顶点iN...

    :求解最短路径的Dijkstra算法

    二:Dijkstra算法伪代码

    Vs(iN,2):  Vs(iN,1)==1表示顶点iN在集合Vs,Vs(iN,2)存储到iN最短距离。

    Ay(NN,NN):  领接矩阵存储边权。  不可行的路记为无穷大。

    By(NN,NN):  记录到顶点iN最短路径的前一个顶点。

    Minp=0;  jn=0;

    while (Vs(NN,1)==1)  %顶点jN表示末点。

    for (iN=1:NN)

    if (Vs(iN,1)==1)%从在集合Vs顶点中找出到外顶点的最短路。

    子函数:找出顶点iN 到外的最短路长与 顶点号[minp2,jN];

    If  Minp >minp2

    Minp=minp2;

    毁掉前记录,从新记录顶点jN与iNN;

    End

    If  Minp==minp2

    Minp=minp2;

    记录顶点jN与iNN;

    End

    End

    End

    %上For循环结束,表找最短路 向前推进一次。

    %记录上面寻找的最短路。

    修改By(jN,iNN)=1;  表示iNN为到jN前一个顶点

    修改Vs(jN,:)      ;

    End

    子函数:找出顶点iN 到外的最短路长与 顶点号[minp2,jN];

    Function  [jN, Minp2 ]=Minp(AyI, Vs )

    Minp2=Inf ;

    For  tN=1:length(AyI)

    If  Minp2 >AyI( tN )&&Vs(tN,1)==0

    Minp2=AyI(tN);

    jN=tN;

    End

    End

    三:代码

    function   f=MinPath()   %记所求起点为0,终点NN

    [NN,Ay]=InitGraph();

    By=zeros(NN);

    Vs=zeros(NN,2);

    Vs(1,1)=1; %起点放入集合Vs

    JiLuQian=zeros(1,NN); is=1; %记录前一顶点

    while  Vs(NN,1)~=1  %结束顶点

    Minp=inf; jN0=0;

    for  iN=1:NN

    if  Vs(iN,1)==1

    [Minp2,jN]=Minpa(Ay(iN,:),Vs);

    Minp2=Minp2+Vs(iN,2);

    %寻之后,jN一个;而它前一个顶点可能有多个

    if  Minp>Minp2

    Minp=Minp2; jN0=jN;

    is=1;  JiLuQian(1,is)=iN; continue ;

    end

    if  Minp ==Minp2&jN0==jN;

    %排除同时多条路径相等,但到达顶点不相同

    is=is+1;  JiLuQian(1,is)=iN;

    end

    end

    end

    if Minp>=inf

    disp(‘不能找到通路到所求顶点!’);

    break;

    end

    Vs(jN0,:)=[1,Minp];

    isl=1;

    while isl<=is

    By(jN0,JiLuQian(1,isl))=1  ;

    isl=isl+1;

    end

    end

    %回搜By找最短路径输出

    Search( By, NN, NN);

    f=Vs(NN,2);

    end

    %  顶点到外的最小路经

    function [Minp2,jN]=Minpa(AyI,Vs)

    Minp2=inf;

    jN=[];

    for tN=1:length(AyI)

    if Minp2 >AyI(tN) & Vs(tN,1)==0 %找一顶点到外的最小路经

    Minp2=AyI(tN);

    jN=tN;

    end

    end

    end

    %  回寻输出最短路径

    function  tp=Search( By, NN,jv)

    tp=1;

    if jv==1

    return;

    end

    it=1;

    while it

    if By(jv,it)~=0

    Search( By, NN, it);

    fprintf(1,’%d–>’,it);

    if jv==NN

    fprintf(1,’%d\n’,NN);

    end

    end

    it=it+1;

    end

    end

    %  建立图形

    function [NN,Ay]=InitGraph()

    %顶点列:1     2     3     4    5    %顶点行

    Ay= [  Inf   1     2     Inf   Inf   %  1

    Inf   Inf   Inf   3     5     %  2

    Inf   4     3     Inf   Inf   %  3

    Inf   Inf   Inf   Inf   2     %  4

    Inf   Inf   Inf   Inf   Inf   %  5

    ]

    NN= 5 ; %表示领接矩阵的行列数,即图的顶点数

    %    建立图的领接链表

    %NN= input(‘请输入顶点数:’);

    %Ay=zeros(NN);   Ay(:,:)=inf;

    %disp(‘输入弧的起点,终点,权值(输入都为0结束)!’);

    %v0=input(‘v0= ‘);v1=input(‘v1= ‘);dis=input(‘dis=   ‘);

    %while v0~=0|v1~=0|dis~=0

    %    Ay(v0,v1)=dis;

    %  v0=input(‘v0= ‘);v1=input(‘v1= ‘);dis=input(‘dis=   ‘);

    %end

    %    建立图的领接链表

    end

    展开全文
  • Dijkstra算法MATLAB仿真

    2020-11-14 16:18:05
    这个代码是使用D算法寻找给定矩阵形式的图,来搜索指定节点到其他节点的最短距离,和最短路径。程序需要输入节点数,图的矩阵和指定的节点
  • Dijkstra算法求解格栅地图路径matlab代码
  • 已经输入图的信息,运行程序,选择工作模式,输入任务信息即可得到最短路径详细信息。两种工作模式,一种为输入要途径的节点序列,且节点顺序已定,程序输出最短路径的途径节点及路径距离。第二种为输入要途径的节点...
  • Dijkstra最短路径算法Matlab实现 包括最短路径的打印子程序
  • Dijkstra算法算是贪⼼思想实现的,⾸先把起点到所有点的距离存下来找个最短的,然后松弛⼀次再找出最短的,所谓的松弛操作就是,遍历⼀遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,...
  • 优化完整的Dijkstra算法MATLAB仿真程序,可以任意修改栅格地图大小并随意添加障碍验证自己的算法实现效果,同事也可以生随机地图对算法可行性进行实时验证,希望可以帮到每一位学习中的同学。
  • MATLAB代码实现最短路径Dijkstra算法,寻找全局最优路径。系统偷偷把所需积分抬高了好多,我重新提交降一下积分
  • matlab中实现网络最短路径求解,最经典的最短路径求解方法,以网络邻接矩阵为输入变量,输出任意节点间的最短路径。
  • dijkstra算法,用matlab实现,本人自己写的。有需要的可以参考下。
  • 在学习上述K最短路径算法时,需要调用Dijkstra算法, 为方便大家调用,将之模块化,引用烦请标明出处。 function [pathout cost] = dijkstra(netCostMatrix, source, destination) %Dijkstra算法以其提出者人名命名...

    首先感谢一位博主“乐观的阿锡”分享了K最短路径算法:
    参考:
    MATLAB-K最短路径算法(KSP,K-shortest pathes)

    在学习上述K最短路径算法时,需要调用Dijkstra算法,
    为方便大家调用,将之模块化,引用烦请标明出处。

    function [pathout cost] = dijkstra(netCostMatrix, source, destination)
    
    %Dijkstra算法以其提出者人名命名,理论部分请参考教材P269《最优化技术与数学建模》董文永等编清华大学出版社2010%代码已模块化,可以直接调用,引用请标注出处。
    %若接收的destination不为空则返回起点到终点的路径和路径总权重,否则返回最短路径上前一节点的列坐标值和当前节点的永久标号值。
    
    m=netCostMatrix;n=size(netCostMatrix,1);%CostMatrix为n*n矩阵,默认行为起点列为终点,没有通路时请赋值为inf。
    lub(1:n)=0;lub(source)=1;%若求出最短路径的永久标号值,设路标为1,否则为0d(1:n)=inf;d(source)=0;%临时存放各点的标号值,当路标为1时临时标号值即为永久标号值。
    pathnode(1:n)=0;%存放最短路径上当前节点的前一点的列坐标值。
    count=1;
    while count<n %应用Dijkstra算法n-1次可以求处所有点间的最短路径    
     yb=find(lub);%列出已在最短路径上的点,默认起点已标出
     wb=find(lub==0);%列出未在最短路径上的点
     tempvalue=inf;
     lastpoint=source;
     for i=1:length(yb)
         for j=1:length(wb)
             plus=d(yb(i))+m(yb(i),wb(j));%找到与已知最短路径相接的下一节点的临时标号值
             if plus<tempvalue %逐个比较,以找到与已知最短路径相接的最小标号值
                 tempvalue=plus;
                 lastpoint=wb(j);
                 d(lastpoint)=tempvalue;             
                 pathnode(lastpoint)=yb(i);
             end
         end
     end
     lub(lastpoint)=1;%使时临时标号值转为永久标号值
     count=count+1;
    end
    
    pathout=destination;%终点一定在最短路径上,通过回溯至起点找到最短路径
    if ~isempty(destination)
        cost=d(destination);
        temptvalue=destination;
        for k=1:n
            pathout=[pathout,pathnode(temptvalue)];
            if source==pathnode(temptvalue) %判断是否到达起点,若是则回溯结束返回结果
                pathout=fliplr(pathout);
                return
            elseif~pathnode(temptvalue)%判断是否存在通路,若不存在则回溯结束返回结果
                pathout=[];
                cost=[];
                return
            else            
            temptvalue=pathnode(temptvalue);
            end
        end
    else
        cost=d;
        pathout=pathnode;  
    end
    end
    
    展开全文
  • 改进的考虑路阻的Dijkstra算法matlab算法代码及注解
  • 压缩包里有Dijkstra算法的描述文档、实现原理以及MATLAB代码压缩包里有Dijkstra算法的描述文档、实现原理以及MATLAB代码
  • Dijkstra算法Matlab程序,用于求各点之间的最短路距离。该程序解决了一个有九个点的无向图中求任意两点之间最短路距离的例子。程序中的每一步都有详细说明。
  • Dijkstra算法matlab实现)

    千次阅读 2021-03-17 07:37:02
    Dijkstra算法 Dijkstra算法主要是用来解决单源点最短路径问题。 该算法的思路如下: 在一个带非负权值的图G=(V,E)中,把顶点集V分为两组。 S:已求出最短路径的顶点的集合,初始时集合S中只有源点s。 V-S:尚未...

    Dijkstra算法

    Dijkstra算法主要是用来解决单源点最短路径问题。


    该算法的思路如下:

    • 在一个带非负权值的图G=(V,E)中,把顶点集V分为两组。
    • S:已求出最短路径的顶点的集合,初始时集合S中只有源点s。
    • V-S:尚未确定最短路径的顶点集合,将V-S中顶点按最短路径递增的次序加入S中。
    function [mydistance,mypath]=mydijkstra(a,sb,db);
    %输入:a——邻接矩阵;a(i,j)——i到j之间的距离,可以是有向的
    %sb——起点的标号,db——终点的标号
    %输出:mydistance——最短路的距离,mypath——最短路的路径
    
    n=size(a,1);visited(1:0)=0;
    distance(1:n)=inf;distance(sb)=0;	%起点到各顶点距离的初始化
    visited(sb)=1;u=sb;		%u为最新的S集合顶点
    parent(1:0)=0;		%前驱顶点的初始化
    for i=1:n-1
    	id=find(visited==0);	%查找V-S集合的顶点
    	for v=id
    		if a(u,v)+distance(u)<distance(v)
    			distance(v)=distance(u)+a(u,v);		%修改标号值
    			parent(v)=u;
    		end
    	end
    	temp=distance;
    	temp(visited==1)=inf;	%已标号点的距离换成无穷大
    	[t,u]=min(temp);	%找标号值最小的顶点
    	visited(u)=1;	%标记已经标号的顶点
    end
    mypath=[];
    if parent(db)~=0 	%如果存在路!
    	t=db;mypath=[db];
    	while t~=sb
    		P=parent(t);
    		mypath=[P mypath];
    		t=P;
    	end
    end
    mydistance=distance(db);
    
    展开全文
  • 最短路Dijkstra算法 Matlab代码Function部分,通用各种类型网络
  • 基于Dijkstra算法路径规划matlab实现
  • Dijkstra算法可以用于求出从给定节点到其他各个节点的...下面直接给出Matlab实现的Dijkstra算法adjacent_M = input("请输入邻接矩阵(结点从1开始递增编号): ");Distance = zeros(1,size(adjacent_M,1)); %用于存放从...
  • 最短路径 Dijkstra算法Matlab代码实现

    万次阅读 多人点赞 2020-09-11 09:29:25
    % 利用dijkstra算法计算两点间的最短路径 % A:邻接矩阵 % strat:起点编号 % dest:终点编号 % path:最短路径索引 % distence:最短路径下的距离值 function [dist,path] = dijkstra(A,start,dest) % 测试数据 A =...
  • MATLAB】最短路径Dijkstra算法

    千次阅读 热门讨论 2021-07-30 19:06:29
    目录1.Dijkstra算法1.1使用范围1.2算法思路1.3实例2.代码2.1dijstra函数2.2调用函数 1.Dijkstra算法 1.1使用范围 ∙\bullet∙ 寻求从一固定顶点到其余各点的最短路径 ∙\bullet∙ 有向图、无向图和混合图 ∙\...
  • Dijkstra算法及其matlab实现

    万次阅读 2018-09-05 20:17:01
    最短路问题和Dijkstra算法 图的概念 图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种...
  • matlab中使用dijkstra算法

    千次阅读 2020-04-17 16:25:44
    matlab中使用dijkstr算法求最短路径 最近在搞数学建模,这个dijkst算法搞了好几天才明白,所以小菜鸡来记录一下。 来讲一下大概思路: dijkstr算法整体是贪心算法思想 以这个无向图为例,假设从点1开始: 第一步...
  • MATLAB-Dijkstra算法

    2017-12-25 13:25:12
    采用Dijkstra算法,编写了MATLAB-m文件,求解出最短路径
  • Dijkstra算法计算最短路径一、 Dijkstra算法分析算法介绍算法步骤算法实例二、程序实现 一、 Dijkstra算法分析 算法介绍 Dijkstra算法是由荷兰计算机科学家Dijkstra于1959 年提出的,是从一个顶点到其余各顶点的...
  • 最短路Dijkstra算法 Matlab代码Input例子,一个小网络,用于测试Function
  • Dijkstra算法是一种最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多...
  • 资源名:dijkstra算法_Dijkstra最短路算法_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有...
  • 图论 Dijkstra算法matlab结果解读可以求出图G中从顶点开始到其余各个顶点的最短路。在这里不列出复杂的数学公式,只对其原理和使用方式做叙述原理Dijkstra算法能够求出顶点到其余各个顶点的最短路径。属于贪心算数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,653
精华内容 661
关键字:

dijkstra算法matlab

matlab 订阅