精华内容
下载资源
问答
  • 2020-11-03 16:57:05

     题目描述:

    求从左上角到右下角的权重和最小的路径,可以向上、下、左、右四个方向行走

    思路:

    动态规划:先根据上、下、左、右四个位置计算走到该单元格的最短距离;然后根据得到的单元和最短距离更新上、下、左、右四个位置的最短距离;

    m,n=5,3
    arr=[[1,1,1],[5,1,1],[1,1,1],[1,5,7],[1,1,1]]
    
    weight=[[float("inf")]*n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i==0 and j==0:
                weight[i][j]=arr[i][j]
            else:
                cur_min=float("inf")
                if i-1>=0:
                    cur_min=min(cur_min,weight[i-1][j])
                if i+1<m:
                    cur_min = min(cur_min, weight[i + 1][j])
                if j-1>=0:
                    cur_min = min(cur_min, weight[i ][j-1])
                if j+1<n:
                    cur_min = min(cur_min, weight[i][j + 1])
                weight[i][j] = cur_min+arr[i][j]
                if i-1>=0:
                    weight[i - 1][j]=min(weight[i][j]+arr[i-1][j],weight[i-1][j])
                if i+1<m:
                    weight[i + 1][j] = min(weight[i][j] + arr[i+1][j], weight[i + 1][j])
                if j-1>=0:
                    weight[i ][j-1] = min(weight[i][j] + arr[i ][j-1], weight[i ][j-1])
                if j+1<n:
                    weight[i][j + 1] = min(weight[i][j] + arr[i][j + 1], weight[i][j + 1])
    print(weight)
    

     

    更多相关内容
  • ArcGIS Pro中生成路径矩阵的工具箱
  • 给出了二维元素矩阵的概念,对于赋权图对应的赋权矩阵,定义了二维元素初始赋权路径矩阵和二维元素一般赋权路径矩阵,在通常赋权矩阵“乘法”运算基础上定义了路径“乘法”运算,从而得到了二维元素一般赋权路径矩阵...
  • 电网络的课堂作业,希望对以后的人有所帮助,不过这个过程还是比较简单的,希望后人改进。
  • 此程序是根据《VLSI数字信号处理系统设计与实现》的第2.4.1节内容编写的,实现了利用最长路径矩阵计算迭代边界。
  • 构造了邻接矩阵存储,初始化时全部为零 #include using namespace std; typedef int Vertex; const int MaxVertexNum = 4; typedef struct GNode * MGraph; const int Infinity = 10; int Dist[MaxVertexNum

    这个是陈越数据结构第六章的习题6.12

    构造了邻接矩阵存储,初始化时全部为零


    #include<iostream>
    using namespace std;
    typedef int Vertex;
    const int MaxVertexNum = 4;
    typedef struct GNode * MGraph;
    const int Infinity = 10;
    int Dist[MaxVertexNum][MaxVertexNum], Path[MaxVertexNum][MaxVertexNum];
    struct GNode {
    	int Nv;
    	int Ne;
    	int G[MaxVertexNum][MaxVertexNum];
    };
    typedef struct ENode * Edge;
    struct ENode {
    	Vertex V1, V2;
    	int Weight;
    };
    MGraph CreatGraph(int N)
    {
    	MGraph Graph = new struct GNode;
    	Graph->Nv = N;
    	Graph->Ne = 0;
    	for (Vertex V = 0; V < Graph->Nv; V++)
    		for (Vertex W = 0; W < Graph->Nv; W++)
    			Graph->G[V][W] = 0;
    	return Graph;
    }
    void Insert(MGraph Graph, Edge E)
    {
    	Graph->G[E->V1][E->V2] = E->Weight;
    }
    MGraph BuildGraph()
    {
    	int Nv;
    	MGraph Graph;
    	cin >> Nv;
    	cin.get();
    	Graph = CreatGraph(Nv);
    	cin >> Graph->Ne;
    	int k = Graph->Ne;
    	while (k--)
    	{
    		Edge E = new struct ENode;
    		cin >> E->V1;
    		cin.get();
    		cin >> E->V2;
    		cin.get();
    		cin >> E->Weight;
    		cin.get();
    		Insert(Graph, E);
    	}
    	return Graph;
    }
    int Floyed(MGraph Graph)
    {
    	Vertex V, W;
    	for (V = 0; V < Graph->Nv; V++)
    		for (W = 0; W < Graph->Nv; W++)
    		{
    			Dist[V][W] = Graph->G[V][W];
    			Path[V][W] = -1;
    		}
    	int k, i, j;
    	for (k = 0; k<Graph->Nv; k++)
    		for (i = 0; i<Graph->Nv; i++)
    			for (j = 0; j < Graph->Nv; j++)
    			{
    				if (Dist[i][k] + Dist[k][j] < Dist[i][j])
    				{
    					Dist[i][j] = Dist[i][k] + Dist[k][j];
    					Path[i][j] = k;
    					if (i == j&&Dist[i][j] < 0)return -1;
    				}
    			}
    	
    	for (V = 0; V < MaxVertexNum; V++)
    	{
    		for (W = 0; W < MaxVertexNum; W++)
    			cout << Dist[V][W] << " ";
    		cout << endl;
    	}
    	return 1;
    }
    void OutPath(int Path[][MaxVertexNum])
    {
    	int V, W;
    	for (V = 0; V < MaxVertexNum; V++)
    	{
    		for (W = 0; W < MaxVertexNum; W++)
    			cout << Path[V][W] << " ";
    		cout << endl;
    	}
    }
    void main()
    {
    	MGraph Graph = BuildGraph();
    	int k = Floyed(Graph);
    	if (k) OutPath(Path);
    	else cout << "None";
    	cin.get();
    }
    
    /*输入
    4
    12
    0 1 3
    0 2 4
    0 3 2
    1 0 8
    1 2 30
    1 3 30
    2 0 6
    2 1 2
    2 3 30
    3 0 30
    3 1 30
    3 2 3
    */
    输出结果为下

    0 3 4 2
    8 0 12 10
    6 2 0 8
    9 5 3 0
    -1 -1 -1 -1
    -1 -1 0 0
    -1 -1 -1 0
    2 2 -1 -1

    Dist矩阵里Infinity我选的30,尽量选择大一些的数,我一开始选的10发现输出距离有问题。


    展开全文
  • 计算任何阶段的所有路径矩阵
  • 接下分享一下利用存有邻接矩阵的csv文件得到最短路径矩阵(存有任意两个节点之间的最短路径)的csv文件,想获得一般的ODM也同样适用。方法用的是Floyd算法,基于python3,使用pandas和copy模块。 输入文是一个csv文件...

    我之前写过一篇将arcgis的swm文件处理成为保存矩阵的文本文件格式的博客,得到的是csv文件。该文件保存的空间权重矩阵。csv文件方便进一步的空间分析。接下分享一下利用存有邻接矩阵的csv文件得到最短路径矩阵(存有任意两个节点之间的最短路径)的csv文件,想获得一般的ODM也同样适用。方法用的是Floyd算法,基于python3,使用pandas和copy模块。

    输入文是一个csv文件,存有空间邻接矩阵,1代表相邻,0代表不相邻。比如4和2相邻,4与3不相邻。



    import pandas as pd
    import copy
    
    A=pd.read_csv(r'E:\atest\NYC\drug\linjie.csv',index_col=0)
    #A是邻接矩阵,相邻对象元素为1,不相邻为0
    
    D=copy.deepcopy(A)
    #用于储存节点对的最短路径,相邻的为实际权值(本例为1),不相邻设置为很大的数(远大于所有边的权值,本例设置为999)
    ilter=[i for i in range(len(A))]
    #o代表起始节点ID,d是终点ID,mid是内插节点
    for o in ilter:
        for d in ilter:
            if d==o:
                continue
            if D.iloc[o,d]==0:
                D.iloc[o,d]=999
    print("得到矩阵D")
    #D初始化完毕
    
    
    #使用Floyd算法计算SP
    
    for mid in ilter:
        if mid%10==0:
            print("进度~~%d/%d"%(mid,len(A)))
        for o in ilter:
            for d in ilter:
                if D.iloc[o,mid]!=999 and D.iloc[mid,d]!=999 and D.iloc[o,d]>D.iloc[o,mid]+D.iloc[mid,d]:
                    D.iloc[o,d]=D.iloc[o,mid]+D.iloc[mid,d]
                            
    D.to_csv(r'E:\atest\NYC\drug\ODM.csv')
    得到的最短路径矩阵如下:

    从文件可以直观看到0到1的SP为2,0到2的SP为4。
    一段简单的代码分享,希望能帮到需要解决相关问题的朋友们。

    展开全文
  • %对这个变量即我们刚刚绘制的图形进行高亮处理 补充: 求出任意两点的最短路径矩阵 %求出任意两点的最短路径矩阵 D=distances(G); %注意:该函数matlab2015b之后才有 D(1,2)% 1 -> 2的最短路径 D(3,9)% 3 -> 9的最短...

    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) 
    
    %注意字符串元胞数组是用大括号包起来
    s2 = {’学校’,’电影院’,’网吧’,’酒店’};
    t2 = {’电影院’,’酒店’,’酒店’,’KTV'} ;
    G2 = graph(s2,t2);
    plot(G2,'linewidth', 2) %设置线的宽度
    
    %下面的命令是在画图后不显示坐标
    set( gca,'XTick' ,[] ,'YTick',[]);
    

    无向图,有权重w

    %函数graph(s, t,w): 可在s和t中的对应节点之间以w的权重创建边,并生成一个图
    s =[1,2,3,4];
    t = [2,3,1,1];
    w = [3,8,9,2];
    G = graph(s,t,w):
    plot(G,’ EdgeLabel',G. Edges. Weight,’ linewidth'2)
    set( gca,'XTick'[], 'YTick',[] ) ;
    

    Matlab作有向图

    无权图

    %无权图digraph(s, t)
    s =[1,2,3,4,1];
    t = [2,3,1,1,4];
    G = digraph(s,t) ;
    plot (G);
    set( gca,'XTick',[], 'YTick', [] );
    

    有权图

    %有权图digraph(s, t, w)
    s =[1,2,3,4];
    t =[2,3,1,1];
    w = [3,8,9,2];
    G = digraph(s,t,w);
    plot (G,’EdgeLabel', G.Edges.Weight,'linewidth', 2);
    set( gca,'XTick',[], 'YTick', [] );
    

    最短路径,注意:该函数matlab2015b之后才有

    [P,d] = shortestpath (G, start , end [,'Method', algorithm] )
    功能:返回图G中start节点到end节点的最短路径
    

    输入参数:

    • G输入图( graph对象| digraph对象)
    • start起始的节点
    • end目标的节点
    • [,‘Method’,algorithm]是可选的参数,表示计算最短路径的算法。一般我们不用手动设置,默认使用的是“auto” ;

    输出参数:

    • P 最短路径经过的节点
    • d 最短距离

    选项说明:

    'auto' (默认值):
    'auto'选项会自动选择算法:
    'unweighted'用于没有边权重的graph和digraph输入。
    'positive'用于具有边权重的所有graph输入,并要求权重为非负数。此选项还用于具有非负边权重的digraph输入。
    'mixed'用于其边权重包含某些负值的digraph输入。图
    不能包含负循环。
    
    'unweighted'
    广度优先计算,将所有边权重都视为1
    'positive'
    Dijkstra算法,要求所有边权重均为非负数。
    
    
    'mixed' (仅适用于digraph )
    适用于有向图的Bellman-Ford算法,要求图没有负循环。
    尽管对于相同的问题, 'mixed'的速度慢于'positive' ,'mixed'更为通用,因为它允许某些边权重为负数。
    

    举例

    在这里插入图片描述

    s=[1 1 1 2 3 3 4 5 5 5 5 6 6 7 9 9];%编号
    t=[2 3 4 5 2 4 6 4 6 7 8 7 5 8 5 8];%能走的下一个编号
    w=[6 3 1 1 2 2 10 6 4 3 6 2 10 4 2 3];%距离
    G= digraph(s,t,w);
    plot(G,'EdgeLabel', G.Edges.Weight,'linewidth',2);
    set(gca,'XTick',[],'YTick',[] ) ;
    
    [P,d] = shortestpath(G,1,8); %注意:该函数matlab2015b之后才有
    
    %在图中高亮我们的最短路径
    myplot = plot(G,'EdgeLabel',G.Edges.Weight,'linewidth',2); %首先将图赋给一个变量
    highlight (myplot,P,'EdgeColor','r');%对这个变量即我们刚刚绘制的图形进行高亮处理
    

    在这里插入图片描述在这里插入图片描述

    补充:

    求出任意两点的最短路径矩阵

    %求出任意两点的最短路径矩阵
    D=distances(G); %注意:该函数matlab2015b之后才有
    D(1,2)% 1 -> 2的最短路径
    D(3,9)% 3 -> 9的最短路径
    

    找出给定范围内的所有点nearest(G, s, d)

    %找出给定范围内的所有点nearest(G, s, d)
    %返回图形G中与节点s的距离在d之内的所有节点
    [nodeIDs, dist] = nearest(G, 2,10)
    %注意:该函数matlab2016a之后才有
    
    展开全文
  • Floyd算法 邻接矩阵 最短路径 上机作业没问题
  • 将数值v填充到闭合区域a的中央。主要利用MATLAB的find函数,亦可使用路径填充算法实现。
  • 动态规划题目类型 & 做题思路总览:动态规划解题套路 & 题型总结 & 思路讲解 文章目录 二、矩阵路径 1. 矩阵的最小路径和 2. 矩阵的总路径数 3. 矩阵的总路径数 Ⅱ 4. 三角形路径 5. 与矩阵路径有关的初始值 二、...
  • 矩阵最短路径-动态规划

    千次阅读 2021-02-25 23:04:29
    矩阵最短路径-动态规划
  • 矩阵最优路径

    2018-05-23 17:32:29
    矩阵最左上角位置移动到最右下角位置(每次只能向右或向下移动一步),每移动一次要相应加上矩阵元素上的能量值,基础能量值为2000,中途若能量值小于0便认定死亡,挑战不成功;求所有满足条件的路径;求能量值...
  • 矩阵求最短路径

    千次阅读 2018-08-05 15:29:39
    给定一个M×N的矩阵,定义一条路径为:从矩阵左上顶点数字出发到达右下数字,每一次只可以从一个数字出发向右移动一步或向下移动一步,定义路径和为:路径经过的数字的和。要求编写一个程序,找到路径和最小的那条...
  • 主要为大家详细介绍了python矩阵/字典实现最短路径算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 1091. 二进制矩阵中的最短路径 给你一个 n x n 的二进制矩阵 grid 中,返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径,返回 -1 。 二进制矩阵中的 畅通路径 是一条从 左上角 单元格(即,(0, 0))到 右下角...
  • 矩阵最大路径问题

    千次阅读 2019-04-15 01:16:56
    比如在遍历到3这个点时,我们要计算到达这个点的最大路径,要先求出子路径,而3的上面没有点,只有左面有,因此到达3的最大路径就是10的最大路径加3,这样第一行就都能求出来 再往下看,例如我们遍历到12这个点,...
  • 矩阵中的路径(思路与实现)

    千次阅读 2018-07-02 23:24:39
    题目描述请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的...
  • 今天和同学讨论概率转移矩阵时如何选择N步最大概率路径问题想到了以下内容。 问题:一个有权图(有无向都可以)对应于一个矩阵。其中矩阵元素i,j对应图中点i到点j的权。 如何找到点i切好n步到点j的所有路径中权值...
  • 博文是主要实现王道机构学长所说的path矩阵递归找到完整路径,也是一个很简单递归,主要是将起点和终点之间的其他连接结点找到,所以用递归类似于二分,找到一个中间结点之后再对左右分别进行递归。 本文提供了完整...
  • 剑指Offer(Python多种思路实现):矩阵中的路径 面试12题: 题目:矩阵中的路径 题:请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径路径可以从矩阵中的任意一个格子开始,每一步可以...
  • 矩阵的最短路径

    2018-06-22 18:13:41
    int findshortcurt() { int base[4][4]={{1,3,5,9},{8,1,3,4},{6,6,6,6},{8,8,8,0}}; int dp[4][4]={{0,},{0,}}; dp[0][0] = base[0][0];... /*求出矩阵的第一行和第一列的步骤值*/ for(i=1;i&lt;4;i+...
  • 文章出处:极客时间《数据结构和算法之美》-作者:王争。该系列文章是本人的学习笔记。 题目 ...我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少...
  • 最短路径(二维矩阵)

    千次阅读 2019-05-07 10:51:00
    题目 给定一个矩阵m,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有路径中最小的路径和。 例子: 给定m如下: 1 3 5 9 8 1 3 4 5 0 6 1 8 8 4 0 路径1,...
  • c代码-矩阵最小路径和 概述: 给定一个矩阵,大小为m,从左上角开始每次只能向右走或者向下走,最后达到右下角的位置。路径中所有数字累加起来就是路径和,返回所有路径的最小路径和。 示例1 比如输入矩阵...
  • 基于矩阵实现的最短路径算法

    万次阅读 2015-11-10 20:13:32
    1.最短路径 图中最短路径是指:寻找图(由结点和路径组成的)中两结点之间的权重最小的路径。Wikipedia上最短路径(Shortest Path)的定义如下: In graph theory, the shortest path problem is the problem of ...
  • 求解矩阵最短路径问题

    千次阅读 2017-10-26 20:18:53
    首先,分析这个问题,你需要寻找的其实就是从哪个位置到达所需要的点G[i][j]是最小的,这里建立一个新的矩阵,用来存储到达每个点的和,记为s[i][j],到达G[i][j],只有两个位置,即s[i-1][j]和s[i][j-1],那么利用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 164,471
精华内容 65,788
关键字:

路径矩阵