精华内容
下载资源
问答
  • 基于 matlab 的 floyd 算法 matlab 计算最短路径 function [d,path]=floyd(a,sp,ep) % floyd - 最短路问题 % % Syntax: [d,path]=floyd(a,sp,ep) % % Inputs: % a - 距离矩阵是指 i 到 j 之间的距离可以是有向的 % ...
  • SHPATH - 避障的最短路径(版本 1.3) 给定一个由 0(对于开放空间)和 1(对于障碍物)组成的“地形”矩阵,该函数计算两个指定点之间的最短路径,同时避开障碍物。 采用两阶段解决方案。 在第一阶段,算法通过...
  • Matlab计算最短路径及路径的个数

    万次阅读 2016-04-26 12:00:45
    最近老板让计算最短路径及路径个数,找遍了所有工具箱,都没现成的。急死了,什么Dijkstra和Floyd都搞不定。最后,想了想,算了吧,自己编吧,反正自己用,又没有算法复杂度要求。于是自己就写了个小程序(本程序仅...

        最近老板让计算最短路径及路径个数,找遍了所有工具箱,都没现成的。急死了,什么Dijkstra和Floyd都搞不定。最后,想了想,算了吧,自己编吧,反正自己用,又没有算法复杂度要求。于是自己就写了个小程序(本程序仅限无权无向连通图),算法复杂度不晓得(偷笑)。

       本人不是计算机出身,就不写算法步骤了,直接上图解。


       我们首先计算的是节点1到所有节点的最短路径,及个数。s存放节点1到所有节点的最短路径,p_num存放路径的个数。

       初始化:s=[0,0,0,0,0,0,0]      p_num=[1,0,0,0,0,0,0]

        第一轮迭代:找节点1的所有邻居节点2,3,4。则:s([2,3,4])=1

                                在看节点2的邻居1和5.则: p_num(2)= p_num(1)+ p_num(5)=1+0=1

                                同理:p_num(3)=p_num(4)=1

                                则本轮会得到:s=[0,1,1,1,0,0,0]      p_num=[1,1,1,1,0,0,0]

        第二轮迭代:找节点2,3,4的所有邻居节点(没有被找过的节点)5,6。则:s([5,6])=2

                                再看节点5的邻居2,3和7.则: p_num(5)= p_num(2)+ p_num(3)+ p_num(7)=1+1+0=2

                                同理:p_num(6)=1

                                则本轮会得到:s=[0,1,1,1,2,2,0]      p_num=[1,1,1,1,2,1,0]

        第三轮迭代:找节点5,6的所有邻居节点(没有被找过的节点)7。则:s([7])=3

                                在看节点7的邻居5和6.则: p_num(2)= p_num(5)+ p_num(6)=2+1=3

                                则本轮会得到:s=[0,1,1,1,2,2,3]      p_num=[1,1,1,1,2,1,3]

       找节点7的所有邻居节点(没有被找过的节点),没啦,迭代终止。哈哈节点到所有节点的最短路径及条数搞定,然后来个循环就把任意两个点的最短路径及个数搞定。

      哇嘎嘎,简单粗暴,下面有程序,能力有限。使用前记得要仔细拍错误哦哦




    function [all_s,all_p_num]=all_node_shortest(w)
        %全联通无权无向图
        %输入邻接矩阵w
        %all_s为所有节点间的最短距离
        %all_p_num为最短路径的个数
        %树状搜索(纯属自己想的,没有优化,可以跑小网络)
        n=length(w);                    %节点的个数
        all_s=zeros(n,n);               %初始化
        all_p_num=zeros(n,n);       %初始化
        for i=1:n
            [s,p_num]=node_shortest(w,i);
            all_s(i,:)=s;
            all_p_num(i,:)=p_num;   
        end


    end


    function [s,p_num]=node_shortest(w,node)
        %全联通无权无向图
        %输入邻接矩阵w
        %初始节点 node
        %s为node到所有节点的最短距离
        %p_num为最短路径的个数
        %树状搜索(纯属自己想的)
        n=length(w);                    %节点的个数
        s=zeros(1,n);                   %初始化
        p_num=zeros(1,n);               %初始化
        p_num(node)=1;                %node到node本身距离为零,个数记为1           
        node_all=zeros(1,n);               
        node_all(node)=1;               %记录哪些节点被搜索到,搜索到的节点记为1,否则为0
        lj=node;                        %lj为当前步到达的节点(到lj的距离都为k)
        k=1;
        while sum(node_all)<n           %搜索至所有节点停止迭代
            lj=find(sum(w(lj,:),1)>0&node_all==0);      %上一时刻的所有节点的邻居且没有被找到过的节点是这一次的邻居
            s(lj)=k;                                    %记录时刻即路径长度               
            p_num(lj)=sum(w(:,lj).*repmat(p_num',[1,length(lj)]),1); %这一时刻的路径的条数为:这个节点上一时刻已经到达的邻居的所有路径和
            node_all(lj)=1;                                          %这些节点在这个时刻已经被找到
            k=k+1;                                                   %下一时刻
        end
    end
    展开全文
  • 每一次迭代产生一个永久标号,把它接入到以起始点为v0根的树中,在这棵树上每一个顶点与根结点之间的路径皆为最短路径。 1.3实例 寻找从顶点1到顶点5的最短路径: 一共有六个顶点,生成的带权邻接矩阵为:



    1.Dijkstra算法

    1.1使用范围

    ∙ \bullet 寻求从一固定顶点到其余各点的最短路径

    ∙ \bullet 有向图、无向图和混合图

    ∙ \bullet 权非负

    1.2算法思路

    每一次迭代产生一个永久标号,把它接入到以起始点为v0根的树中,在这棵树上每一个顶点与根结点之间的路径皆为最短路径。

    1.3实例

    寻找从顶点1到顶点5的最短路径:
    在这里插入图片描述
    一共有六个顶点,生成的带权邻接矩阵为:

    [ 0 7 9 i n f i n f 14 7 0 10 15 i n f i n f 9 10 0 11 i n f 2 i n f 15 11 0 6 i n f i n f i n f i n f 6 0 9 14 i n f 2 i n f 9 0 ] \begin{bmatrix} 0 & 7 & 9 & inf & inf & 14\\ 7 & 0 & 10 &15 & inf & inf\\ 9 & 10 & 0 & 11 & inf & 2\\ inf & 15 & 11 & 0 & 6 & inf\\ inf & inf & inf & 6 & 0 & 9\\ 14 & inf & 2 & inf & 9 & 0\\ \end{bmatrix} 079infinf14701015infinf910011inf2inf151106infinfinfinf60914inf2inf90


    2.代码

    2.1dijstra函数

    function [min,path]=dijkstra(w,start,terminal)
    %输入变量w为所求图的带权邻接矩阵,start、terminal分别为路径的起点和终点的编号。
    %返回path为从start到termial的最短路径以及长度min
    
    n=size(w,1); label(start)=0; f(start)=start;
    %n为所求图的顶点个数,label存放到各点的最短路径,f(v)表示v的父顶点用来还原路径
    
    %初始化将除了start以外的顶点label均设置为无穷大
    for i=1:n
        if i~=start
           label(i)=inf;
        end
    end
    
    %s数组存放已经搜好的顶点集,初始化只有start
    s(1)=start; u=start;
    while length(s)<n
        %遍历一遍顶点,将不在顶点集中的顶点选出来进行下面的if判定
        for i=1:n
            ins=0;
            for j=1:length(s)
                if i==s(j)
                    ins=1;
                end  
            end
            %判断是否有中继顶点使得它们之间的距离更短,如果有的话更新距离并更新前驱结点
            if ins==0
                v=i;
                if label(v)>(label(u)+w(u,v))
                    label(v)=(label(u)+w(u,v)); f(v)=u;
                end 
            end
        end   
        v1=0;
        k=inf;
        %同上再次进行遍历,找到目前最短的路径顶点v1,放入顶点集并改变u的值
        for i=1:n
            ins=0;
            for j=1:length(s)
                if i==s(j)
                    ins=1;
                end
            end
            if ins==0
                v=i;
                if k>label(v)
                    k=label(v);  v1=v;
                end  
            end
        end
        s(length(s)+1)=v1;  
        u=v1;
    end
    
    min=label(terminal); path(1)=terminal;
    i=1; 
    
    %按倒序结果推出最短路径
    while path(i)~=start
        path(i+1)=f(path(i));
        i=i+1 ;
    end
    path(i)=start;
    L=length(path);
    %翻转得到最短路径
    path=path(L:-1:1);
    

    2.2调用函数

    w = [0,7,9,inf,inf,14;
         7,0,10,15,inf,inf;
         9,10,0,11,inf,2;
         inf,15,11,0,6,inf;
         inf,inf,inf,6,0,9;
         14,inf,2,inf,9,0];
     start=1;terminal=5;
    [min,path]=dijkstra(w,start,terminal);
    min,path
    

    结果
    在这里插入图片描述



    展开全文
  • MATLAB实现最短路径

    2021-08-30 22:55:17
    目录 一、Dijkstra是什么?...最短路径即从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径 二、使用步骤 1.引入库 代码如下(示例): import numpy as np import pandas as p

    目录

    一、Dijkstra是什么?

    二、算法介绍

    1.核心思想

    2.具体思路

    3MATLAB实现

    总结


    前言

    本人是数学建模在学习的小白,分享一下最近学习的内容也顺便做一下笔记。


    提示:以下是本篇文章正文内容,下面案例可供参考

    一、Dijkstra是什么?

    Dijkstra是解决最短路径的一种算法

    最短路径即从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径

    二、算法介绍

    1.核心思想

    广度优先搜索

    2.具体思路

    1.初始化,即所有的节点都是未访问节点(0),所有的距离都是无穷大(INF),所有的父亲节点都是-1,表示不存在。

    2.假设起点(A),然后对应的访问状态变为1,对应的距离变为0,其父亲节点变为本身。

    3.开始访问与起点相邻的节点(B)的信息(此时这些节点还没有被访问)

    更新规则如下:

    如果(A与B的距离加上A列表中的距离)小于(B列表中的距离),那么我们就将B列表中的距离更新为较小的距离,并将其父亲节点更新为A。

    4在所有未访问的节点里找到表格里具有最小距离的那个节点,并将其作为新的已访问节点。

    3MATLAB实现

    s = [9 9 1 1 2 2 2 7 7 6 6 5 5 4];
    t = [1 7 7 2 8 3 5 8 6 8 5 3 4 3 ];
    w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9];%权重
    G = graph(s,t,w);
    plot(G,'EdgeLabel',G.Edges.Weight,'LineWidth',2);
    [P,D] = shortestpath(G,9,4);
    %%高亮显示路径
    myplot = plot(G,'EdgeLabel',G.Edges.Weight,'LineWidth',2);
    highlight(myplot,P,'EdgeColor','r');

    结果:


    三、总结

    这既是今天学习的内容。

    ——更新于2021.8.31

    展开全文
  • matlab求解最短路径

    万次阅读 多人点赞 2017-08-16 16:13:57
    matlab工具箱求图的最短路径

    matlab工具箱求图4.7中从v1到v11的最短路径
                           图4.7

    1、先构造一个n(各点的数量)维矩阵,如果是无向图则是对称矩阵。

    a(1,2)=2;a(1,3)=8;a(1,4)=1;

    a(2,3)=1;a(2,3)=6;a(2,5)=1;

    a(3,4)=7;a(3,5)=5;a(3,6)=1;a(3,7)=2;

    a(4,7)=9;

    a(5,6)=3;a(5,8)=2;a(5,9)=9;

    a(6,7)=4;a(6,9)=6;

    a(7,9)=3;a(7,10)=1;

    a(8,9)=7;a(8,11)=9;

    a(9,10)=1;a(9,11)=2;

    a(10,11)=4;

    2、找到矩阵中的每一个非零元。

    [i,j,v]=find(a);

    3、利用最短距离函数求解。

    [x,y,z]=graphshortestpath(b,1,11,'Directed',false) % Directed是标志图为有向或无向的属性,该图是无向图,对应的属性值为false,或0

    结果与分析

    b =

     

       (2,1)        2

       (3,1)        8

       (4,1)        1

       (3,2)        6

       (5,2)        1

       (4,3)        7

       (5,3)        5

       (6,3)        1

       (7,3)        2

       (7,4)        9

       (6,5)        3

       (8,5)        2

       (9,5)        9

       (7,6)        4

       (9,6)        6

       (9,7)        3

      (10,7)        1

       (9,8)        7

      (11,8)        9

      (10,9)        1

      (11,9)        2

      (11,10)       4

    x =

        13

    y =

         1     2     5     6     3     7    10     9    11

    z =

         0     1     6     1     2     5     3     5    10     7     9

    可得最短路径长度为13.最短路径为:1->2->5->6->3->7->10->9->11.

    附录:

    clc, clear
    a(1,2)=2;a(1,3)=8;a(1,4)=1;
    a(2,3)=1;a(2,3)=6;a(2,5)=1;
    a(3,4)=7;a(3,5)=5;a(3,6)=1;a(3,7)=2;
    a(4,7)=9;
    a(5,6)=3;a(5,8)=2;a(5,9)=9;
    a(6,7)=4;a(6,9)=6;
    a(7,9)=3;a(7,10)=1;
    a(8,9)=7;a(8,11)=9;
    a(9,10)=1;a(9,11)=2;
    a(10,11)=4;
    a=a';   %matlab工具箱要求数据是下三角矩阵
    [i,j,v]=find(a);
    b=sparse(i,j,v,11,11) %构造稀疏矩阵
    [x,y,z]=graphshortestpath(b,1,11,'Directed',false) % Directed是标志图为有向或无向的属性,该图是无向图,对应的属性值为false,或0。



    展开全文
  • floyd算法+matlab计算,对数学建模爱好者有很大的好处~~~~
  • 用遗传算法计算最短路径MATLAB程序,在数学建模及其他编程中一种重要的算法思想
  • 在地图上找到从起始节点到结束节点的最短路径和距离** 2. 找出地图上从起始节点到所有其他节点的最短路径和距离** **地图应由节点和段组成,例如: 1.节点的格式为[ID XY]或[ID XYZ](ID为整数,X,Y,Z代表位置坐标...
  • matlab最短路径

    千次阅读 2020-11-14 21:35:14
    图论最短路径 (1)matlab作图 G = graph(s, t) 其中,s 和 t 都是节点组成的向量,表示从s 、t对应节点之间有边。 然后,plot(G)即可画出图。 G = graph(s, t, w) ...(2)Matlab计算最短路径 [P,d] = s
  • 用粒子群算法计算最短路径,一般用于车辆路径问题%------基本粒子群优化算法(Particle Swarm Optimization)----------- %------名称:基本粒子群优化算法(PSO) %------作用:求解优化问题 %------说明:全局性,...
  • Matlab编程求最短路径

    2021-10-12 16:23:11
    %以下构造一个图并求最短路径,注意图中节点的编号从1开始,不能为0 clear %起点集 s = [9 9 9 9 9 9 9 9 1 1 1 2 2 2 3 4 5 5 6 7]; %终点集 e = [1 2 3 4 5 6 7 8 2 4 8 3 4 8 8 8 6 8 8 8]; %顶点到顶点的边上的...
  • 复杂网络最短路径代码,可以学习,可以直接用。能很好的计算出网络的最短路径
  • 按街口的坐标位置画出街道图,并在街道图上画出9号街口到各街口的最短道路(最短路程树)。有代码,main运行即可
  • MATLAB实现的最短路径算法

    热门讨论 2009-10-26 16:25:18
    MATLAB实现的最短路径算法,在图论里比较重要,可以计算出个对象之间的距离。
  • 能求出任意两点间所有最短路径。数模时编写。考虑邻接矩阵中主对角线数据(虽然一般情况都取零)。更具实用性 能求出任意两点间所有最短路径。数模时编写。考虑邻接矩阵中主对角线数据(虽然一般情况都取零)。更具...
  • 利用 Matlab 编程计算最短路径及中位点选址,最短路问题 两个指定顶点之间的最短路径。
  • MATLAB-K最短路径算法(KSP,K-shortest pathes)

    千次阅读 热门讨论 2020-10-16 17:30:12
    MATLAB-K最短路径算法(KSP,K-shortest pathes) MATLAB代码封装成函数,直接使用。 参考: k最短路径算法之Yen’s Algorithm 基于网络流量的SDN最短路径转发应用 算法背景 K 最短路径问题是最短路径问题的扩展和变形...
  • 利用graphshortestpath 可以求最短路径,具体用法参考MATLAB帮助 S=[1 1 2 2 3 3 4 4 4 4 5 6 6 7 8]; %起始节点向量 E=[2 3 5 4 4 6 5 7 8 6 7 8 9 9 9]; %终止节点向量 W=[1 2 12 6 3 4 4 15 7 2 7 7 15 3 ...
  • MATLAB无向图 无权重w G1 = graph(s1,t1) ; plot (G1) %注意哦,编号最好是从1开始连续编号,不要自己随便定义编号 s1 = [1,2,3,4]; t1 = [2,3,1,1]; G1 = graph(s1,t1) ; plot(G1) %注意字符串元胞数组是用大...
  • 外卖最短路径计算

    2018-10-11 15:54:19
    外卖最短路径计算项目,采用Java代码实现,亲测可用,请放心下载。
  • 图论--Matlab实现最短路径算法

    万次阅读 2014-09-05 17:23:05
    对于一幅有向带权图,如下,可以使用Matlab
  • 复杂网络平均路径长度的m文件,先将复杂网络存储为矩阵,再对其matlab编程,
  • 最短路径 Dijkstra算法的Matlab代码实现

    千次阅读 多人点赞 2020-09-11 09:29:25
    % 利用dijkstra算法计算两点间的最短路径 % A:邻接矩阵 % strat:起点编号 % dest:终点编号 % path:最短路径索引 % distence:最短路径下的距离值 function [dist,path] = dijkstra(A,start,dest) % 测试数据 A =...
  • 系统主要实现了图的创建、单源点最短路径计算功能。依照本系统可以解决实际生活中许多路径选择问题,比如交通旅游、城市规划以及电网架设等等。系统性能稳定,适应性强,界面清晰,操作简单,适合用户使用。 课程...
  • matlab 可视化】MATLAB最短路径网络图

    万次阅读 多人点赞 2017-06-09 15:24:38
    clc,clear a=zeros(7); a(1,2)=4;a(1,3)=2; a(2,3)=3;a(2,4)=2;a(2,5)=6; a(3,4)=5;a(3,6)=4; a(4,5)=2;a(4,6)=7; a(5,6)=4;a(5,7)=8; a(6,7)=3;% %构建稀疏矩阵 ...h=view(biograph(b,[],'showArrows','o
  • 图的最短路径算法 Dijkstra算法 Dijkstra算法研究的是从初始点到其他任一结点的最短路径,即单源最短路径问题,其对图的要求是不存在负权值的边。 Dijkstra算法主要特点是以起始点为中心向外层层扩展,直到扩展到...
  • 最短路径Dijkstra算法原理及Matlab实现

    千次阅读 2020-10-26 16:53:03
    Dijkstra算法研究的是从初始点到其他每一结点的最短路径 以下图为例,首先介绍Dijstra的原理 红字为各结点的编号,蓝字为各结点之间的距离 首先定义几个变量 结点个数n; 二维矩阵M(nxn),距离矩阵,连通的...
  • 最短路径算法 matlab

    2018-12-31 15:25:29
    利用matlab实现了网络最短路径的搜索算法,通过输入邻接矩阵和需要输出最短路径的始节点和终节点,即可得到这连点间可行的最短路。
  • matlab图论工具箱主要用于求最短路径,最小生成树和最大流。 其常见命令如下表: 函数名 功能 graphallshortestpaths 求图中所有顶点对之间的最短距离 graphconncomp 找无向图的连通分支,或有向图的强...

空空如也

空空如也

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

matlab计算最短路径

matlab 订阅