精华内容
下载资源
问答
  • 他从第一个城镇出发,走向(没钱只能走)第n个城镇,现在,请你帮wzy找到一条最短的路径,并倒序(从n到1)输出一条最短路径。 地精小提示:路是单向的QAQ。 输入格式 第一行两个数n,m ,(1≤n≤103,1≤m≤103) ...

    这个问题难受了半天终于搞懂了,来给分享一下
    先弄个例子看看;

    B.wzy的大冒险——出发咯QAQ

    wzy踏上了冒险的旅程。
    现在他从地精手里买了一份地图,地图上有n个城镇。
    他从第一个城镇出发,走向(没钱只能走)第n个城镇,现在,请你帮wzy找到一条最短的路径,并倒序(从n到1)输出一条最短路径。
    地精小提示:路是单向的QAQ。

    输入格式

    第一行两个数n,m ,(1≤n≤103,1≤m≤103)

    接下来m行,每行三个数x,y,z,表示点 x 与点 y 之间有一条权值为 z 的有向边 (1≤x,y,z≤103).

    输出格式

    第一行一个整数表示 1 到 n 的最短距离;
    第二行倒序输出这条路径。

    样例

    input
    5 7
    1 2 69
    1 3 87
    1 4 79
    2 5 94
    2 3 10
    3 5 79
    4 5 43
    output
    122
    5 4 1

    解题思路

    一看这道题就是求最短路径,就是输出路径这一点要搞清楚,看代码解析。

    #pragma GCC optimize(2)
    #include<bits/stdc++.h>
    const int inf =0x3f3f3f3f;
    using namespace std;
    const int maxn =1e3+10;
    typedef long long ll;
    int way[maxn][maxn];//记录从点a到点b的距离 
    int dis[maxn];//某线段的权值 
    int flag[maxn];//用来标记走过的点 
    int d[maxn];//用来存路径,具体存法是他上一个点是从那来的,不懂往下看 
    int n,m;//n是顶点个数,m有多少个边 
    int dijkstra()
    {
    	memset(dis,0,sizeof(dis));
    	for(int i=1;i<=n;i++)
    	{
    		dis[i]=way[1][i];//从1到第i的顶的距离赋给dis 
    		if(way[1][i]!=inf)
    		{
    			d[i]=1;//记录i点事由1到达的 
    		}
    	}
        flag[1]=1; dis[1]=0;
        int x;
    	for(int i=1;i<=n;i++)//循环n次每次找到一个最近的点 ,走过的点标记 
    	{
    		int ans=inf;
    		for(int j=1;j<=n;j++)
    		{
    			if(ans>dis[j]&&!flag[j])
    			{
    				ans=dis[j];
    				x=j;
    			}
    		}
    		flag[x]=1;//已经找到给一个标记 
    		for(int i=1;i<=n;i++)
    		{
    			if(!flag[i])
    			{
    				if(dis[i]>dis[x]+way[x][i])
    				{
    					dis[i]=dis[x]+way[x][i];
    					d[i]=x;//记录到i点事由x过来的 
    				}			
    			}
    		}
    	}
    }
    
    int main()
    {
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			way[i][j]=inf;//把每条路先赋成最大 
    		}
    	}
    	for(int i=1;i<=m;i++)
    	{
    		int a,b,c;
    		cin>>a>>b>>c;
    		way[a][b]=c;//记录a到b的距离 
    	}
    	dijkstra();
    	cout<<dis[n]<<endl;//输出最短距离 
    	int t=n;
    	cout<<n<<" ";//输出路径的最后一个点 
    	int s=1;
    	while(t!=1)
    	{
    		t=d[t];
    		if(s)
    		{
    			cout<<t;//注意下输出 
    			s=0;
    		}
    		else cout<<" "<<t;	
    	}
    	return 0;
    } 
    

    欢迎使用Markdown编辑器

    你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。

    新的改变

    我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客:

    1. 全新的界面设计 ,将会带来全新的写作体验;
    2. 在创作中心设置你喜爱的代码高亮样式,Markdown 将代码片显示选择的高亮样式 进行展示;
    3. 增加了 图片拖拽 功能,你可以将本地的图片直接拖拽到编辑区域直接展示;
    4. 全新的 KaTeX数学公式 语法;
    5. 增加了支持甘特图的mermaid语法1 功能;
    6. 增加了 多屏幕编辑 Markdown文章功能;
    7. 增加了 焦点写作模式、预览模式、简洁写作模式、左右区域同步滚轮设置 等功能,功能按钮位于编辑区域与预览区域中间;
    8. 增加了 检查列表 功能。

    功能快捷键

    撤销:Ctrl/Command + Z
    重做:Ctrl/Command + Y
    加粗:Ctrl/Command + B
    斜体:Ctrl/Command + I
    标题:Ctrl/Command + Shift + H
    无序列表:Ctrl/Command + Shift + U
    有序列表:Ctrl/Command + Shift + O
    检查列表:Ctrl/Command + Shift + C
    插入代码:Ctrl/Command + Shift + K
    插入链接:Ctrl/Command + Shift + L
    插入图片:Ctrl/Command + Shift + G

    合理的创建标题,有助于目录的生成

    直接输入1次#,并按下space后,将生成1级标题。
    输入2次#,并按下space后,将生成2级标题。
    以此类推,我们支持6级标题。有助于使用TOC语法后生成一个完美的目录。

    如何改变文本的样式

    强调文本 强调文本

    加粗文本 加粗文本

    标记文本

    删除文本

    引用文本

    H2O is是液体。

    210 运算结果是 1024.

    插入链接与图片

    链接: link.

    图片: Alt

    带尺寸的图片: Alt

    居中的图片: Alt

    居中并且带尺寸的图片: Alt

    当然,我们为了让用户更加便捷,我们增加了图片拖拽功能。

    如何插入一段漂亮的代码片

    博客设置页面,选择一款你喜欢的代码片高亮样式,下面展示同样高亮的 代码片.

    // An highlighted block
    var foo = 'bar';
    

    生成一个适合你的列表

    • 项目
      • 项目
        • 项目
    1. 项目1
    2. 项目2
    3. 项目3
    • 计划任务
    • 完成任务

    创建一个表格

    一个简单的表格是这么创建的:

    项目Value
    电脑$1600
    手机$12
    导管$1

    设定内容居中、居左、居右

    使用:---------:居中
    使用:----------居左
    使用----------:居右

    第一列第二列第三列
    第一列文本居中第二列文本居右第三列文本居左

    SmartyPants

    SmartyPants将ASCII标点字符转换为“智能”印刷标点HTML实体。例如:

    TYPEASCIIHTML
    Single backticks'Isn't this fun?'‘Isn’t this fun?’
    Quotes"Isn't this fun?"“Isn’t this fun?”
    Dashes-- is en-dash, --- is em-dash– is en-dash, — is em-dash

    创建一个自定义列表

    Markdown
    Text-to- HTML conversion tool
    Authors
    John
    Luke

    如何创建一个注脚

    一个具有注脚的文本。2

    注释也是必不可少的

    Markdown将文本转换为 HTML

    KaTeX数学公式

    您可以使用渲染LaTeX数学表达式 KaTeX:

    Gamma公式展示 Γ ( n ) = ( n − 1 ) ! ∀ n ∈ N \Gamma(n) = (n-1)!\quad\forall n\in\mathbb N Γ(n)=(n1)!nN 是通过欧拉积分

    Γ ( z ) = ∫ 0 ∞ t z − 1 e − t d t &ThinSpace; . \Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,. Γ(z)=0tz1etdt.

    你可以找到更多关于的信息 LaTeX 数学表达式here.

    新的甘特图功能,丰富你的文章

    Mon 06 Mon 13 Mon 20 已完成 进行中 计划一 计划二 现有任务 Adding GANTT diagram functionality to mermaid
    • 关于 甘特图 语法,参考 这儿,

    UML 图表

    可以使用UML图表进行渲染。 Mermaid. 例如下面产生的一个序列图::

    张三 李四 王五 你好!李四, 最近怎么样? 你最近怎么样,王五? 我很好,谢谢! 我很好,谢谢! 李四想了很长时间, 文字太长了 不适合放在一行. 打量着王五... 很好... 王五, 你怎么样? 张三 李四 王五

    这将产生一个流程图。:

    链接
    长方形
    圆角长方形
    菱形
    • 关于 Mermaid 语法,参考 这儿,

    FLowchart流程图

    我们依旧会支持flowchart的流程图:

    Created with Raphaël 2.2.0 开始 我的操作 确认? 结束 yes no
    • 关于 Flowchart流程图 语法,参考 这儿.

    导出与导入

    导出

    如果你想尝试使用此编辑器, 你可以在此篇文章任意编辑。当你完成了一篇文章的写作, 在上方工具栏找到 文章导出 ,生成一个.md文件或者.html文件进行本地保存。

    导入

    如果你想加载一篇你写过的.md文件,在上方工具栏可以选择导入功能进行对应扩展名的文件导入,
    继续你的创作。


    1. mermaid语法说明 ↩︎

    2. 注脚的解释 ↩︎

    展开全文
  • 无向图弗洛伊德算法求最短路径 输出路径

    千次阅读 多人点赞 2020-07-08 10:27:55
    弗洛伊德算法求最短路径 输出路径 弗洛伊德算法其实比较好理解 这里我用邻接矩阵的储存方法来写 一.算法思想 1.1 如果我们要用邻接矩阵来写代码的话,就要储存他的权值信息 这里我们用map[][]这个二维数组来储存 ...

    弗洛伊德算法求最短路径 输出路径

    弗洛伊德算法其实比较好理解
    这里我用邻接矩阵的储存方法来写

    一.算法思想

    1.1
    如果我们要用邻接矩阵来写代码的话,就要储存他的权值信息
    这里我们用map[][]这个二维数组来储存
    其次要输出他的最短路径
    就用path[][]来储存

        int map[100][100];
    	int path[100][100];
    

    1.2
    初始化这个储存权值邻接矩阵
    由于是无环图,自己到自己是 0
    剩下的边的权值我们赋值为MAX

    for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(i==j)
                    map[i][j]=0;
                else
                    map[i][j]=max;
    

    1.3
    读入边的信息
    如果两个结点i,j之间有权值,就把他赋值给map[i][j]
    并且这个时候将j赋值给path[i][j]

    	cout<<"输入点1到点2的距离"<<endl; 
        for(int i=1; i<=m; i++)
        {
            cin>>t1>>t2>>t3;
            map[t1][t2]=t3;
            map[t2][t1]=t3;
            path[t1][t2]=t2;
        }
    

    这个路径的赋值如果在后面有更优解
    将会更新这个值,如果没有,那说明i直接到j就是最短的

    1.4 核心算法
    这个核心算法使用一个三重循环来一个一个找最优解
    第一重循环控制中转结点k
    第二重控制起始结点i
    第三重控制终止结点j

    如果我们发现i->k->j的路径小于i->j
    那我们就更新路径,将path[i][j]=path[i][k]
    同时权值邻接矩阵更新`map[i][j]=map[i][k]+map[k][j]

    for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    if(map[i][k]+map[k][j]<map[i][j])
                    {
                    	 map[i][j]=map[i][k]+map[k][j];
                    	 path[i][j]=path[i][k];
    				}
    

    1.5
    输出最短路径的值

    for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                cout<<map[i][j]<<" ";
                cout<<endl;
        }
    

    1.6
    输出最短路径
    这里我们要输入两个结点v1 v2
    最后输出的就是v1v2的最短路径
    仔细想想我们的path[v1][v2]储存的是v1 v2的第一个中转节点z的信息
    输出z后,path[z][v2]储存的是zv2的第一个中转结点
    一个一个输出这些中转结点
    以此类推,直到zv2的时候,这就是v1v2的最短路径

    int v1,v2,z;
        cout<<"输入两个点,输出之间路径"<<endl; 
        cin>>v1>>v2;
        z=path[v1][v2];
        cout<<v1;
        while(z!=v2)
        {
        	cout<<"->"<<z;
        	z=path[z][v2];
    	}
    	cout<<"->"<<v2;
    

    二.测试数据

    在这里插入图片描述
    在这里插入图片描述
    这里的最短距离我直接的输出距离矩阵了
    如果要输出更方便阅读的形式
    也可以在输出那块把代码改一下,可以cout<<"v1到v2的距离为:<<map[v1][v2]<<endl
    我就不多写了

    ##测试数据
    1 2 2
    1 3 1
    2 3 5
    2 4 4
    3 4 5
    4 5 6

    三.源代码

    #include<iostream>
    using namespace std;
    #define max 99999
    
    void fuluoyide(int n,int m)
    {
    	int map[100][100],t1,t2,t3;
    	int path[100][100];
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(i==j)
                    map[i][j]=0;
                else
                    map[i][j]=max;
        //读入边
    	cout<<"输入点1到点2的距离"<<endl; 
        for(int i=1; i<=m; i++)
        {
            cin>>t1>>t2>>t3;
            map[t1][t2]=t3;
            map[t2][t1]=t3;
            path[t1][t2]=t2;
        }
        //弗洛伊德(Floyd)核心语句
        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    if(map[i][k]+map[k][j]<map[i][j])
                    {
                    	 map[i][j]=map[i][k]+map[k][j];
                    	 path[i][j]=path[i][k];
    				}
                       
        cout<<endl<<"最短距离矩阵为:"<<endl; 
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                cout<<map[i][j]<<" ";
                cout<<endl;
        }
        
        int v1,v2,z;
        cout<<"输入两个点,输出之间路径"<<endl; 
        cin>>v1>>v2;
        z=path[v1][v2];
        cout<<v1;
        while(z!=v2)
        {
        	cout<<"->"<<z;
        	z=path[z][v2];
    	}
    	cout<<"->"<<v2;  
    } 
    
    int main()
    {
    	cout<<"输入顶点数,边数"<<endl; 
    	int n,m;
        cin>>n>>m;//n表示顶点个数,m表示边的条数
        cout<<endl;
        fuluoyide(n,m);
    }
    
    

    总体来说 弗洛伊德算法的思想不是很难懂,有一点点暴力求值的感觉,就硬算
    我还写了一篇 dijkstra 求最短路径的算法,也可以看看

    在这里插入图片描述

    如果帮助到你了,点个赞吧

    展开全文
  •  { // 第n个最短,在最后一次之前已经在不断更新的,所以,每次都是最短比最新的,取最短。  dis[j]=dis[mini]+map[mini][j];  }  }  }  } } int main() {  int n,m;  int i,j;  struct mmm t;  scanf("%d...


    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define inf 0x3f3f3f3f
    int dis[200];
    int vis[200];
    int map[200][200];
    struct mmm
    {
        int x;
        int y;
        int v;
    }xxx[200];
    void dijkstra(int S,int N)   //S表示start,E表示终点
    {
        int i,j;
        dis[S] = 0;              //初始化起始点
        vis[S] = 1;
        for(i=1;i<=N;i++)
        {
            if(vis[i]==0)        //避免自己dis[S]被赋值。
            dis[i]=map[S][i];    //算出所有直达
        }
        for(i=1;i<=N;i++)
        {
          int minn = inf, mini = S;  //minn在新的开始又变成了无穷大
          for(j=1;j<=N;j++)
          {
            if(vis[j]==0&&minn>dis[j])
            {
                minn=dis[j];
                mini=j;
            }
          }                          //第一个for每能定一个最短。
          vis[mini]=1;              //做标记,dis[mini]就定住哪个已经是最短了。
          for(j=1;j<=N;j++)
          {
            if(vis[j]==0)
            {
                if(dis[j]>dis[mini]+map[mini][j])    //第二个for是算转达。
                {                                    // 第n个最短,在最后一次之前已经在不断更新的,所以,每次都是最短比最新的,取最短。


                        dis[j]=dis[mini]+map[mini][j];


                }
            }
          }
        }
    }
    int main()
    {
       int n,m;
       int i,j;
       struct mmm t;
       scanf("%d%d",&n,&m);
       for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
    {
                if(i==j)
    map[i][j]=0;
                else map[i][j]=inf;
             }
        }
       while(m--)
       {
           int i,j,val;
           scanf("%d%d%d",&i,&j,&val);
           map[i][j]=val;
       }
       dijkstra(1,n);
       for(i=1;i<=n;i++)
       {
           xxx[i].v=dis[i];
           xxx[i].y=i;
       }
      for(j=1;j<n;j++)
        for(i=1;i<=n-j;i++)
          if(xxx[i].v>xxx[i+1].v)
      {
          t=xxx[i];
          xxx[i]=xxx[i+1];
          xxx[i+1]=t;
      }
       for(i=2;i<=n;i++)
       {
          if(dis[i]==inf)
          printf("1 %d -1\n",xxx[i].y);
          else
          printf("1 %d %d\n",xxx[i].y,xxx[i].v);
       }
        return 0;
    }

    展开全文
  • 广度优先搜索顾名思义就是以迷宫里的无向图某一个点,借助队列,一层一层以该点为中心散开进行搜索,简单的BFS只能显示出最短路径的长度,这里探讨的就是如何实现BFS对最短路径输出 简单的BFS 通过队列来实现,...

    相信我,看完之后,你会对BFS有种全新的了解,彻底掌握BFS
    只需要这一篇就足够啦,狗头

    BFS路径表示

    广度优先搜索顾名思义就是以迷宫里的无向图某一个点,借助队列,一层一层以该点为中心散开进行搜索,简单的BFS只能显示出最短路径的长度,这里探讨的就是如何实现BFS对最短路径的输出

    简单的BFS

    通过队列来实现,找到迷宫的起点(S)入队,出队列里面的队首,把队首上下左右相邻的点入队列,一直重复此操作,直到队列里面的所有元素都出队表示该迷宫不存在解,如果在队清空之前找到终点(T)的话,一层一层的遍历,找到的话就一定是最短路了,但是简单的BFS只能通过输出(now.d+1)来表示最短路的步数长度,不能表示出最短路径到底是什么?

    #include <iostream>
    #include <string>
    #include <queue>
    using namespace std;
    int n, m;//地图长宽
    string maze[110];//地图
    bool vis[110][110];//访问标记数组
    int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};//方向变化
    bool in(int x, int y) {//确保在地图里面
        return 0 <= x && x < n && 0 <= y && y < m;
    }
    struct node{//定义node类型的结构体
        int x,y,d;//d表示路径
        node(int xx,int yy,int dd){//便于输入结构体里面的值
            x=xx;
            y=yy;
            d=dd;
        }
    };
    int bfs(int sx,int sy){
        queue<node>q;
        q.push(node(sx,sy,0));//将起点放入
        vis[sx][sy]=true;
        while(!q.empty()){//队列如果不为空继续
            node now=q.front();//找到队首
            q.pop();//队首出队
            for(int i=0;i<4;i++){
                int tx=now.x+dir[i][0];//周围遍历
                int ty=now.y+dir[i][1];
                if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){//在界内且未遍历到
                    if(maze[tx][ty]=='T'){//如果是终点,BFS返回完成
                        return now.d+1;
                    }else{//如果不是不返回,标记该点入队继续搜索
                        vis[tx][ty]=true;
                        q.push(node(tx,ty,now.d+1));
                    }
                }
            }
        }
        return -1;//队空未找到就返回-1表示无解
    }
    int main() {
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            cin >> maze[i];
        }
        int x, y;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maze[i][j] == 'S') {//找到迷宫的起点
                    x = i, y = j;
                }
            }
        }
        cout<<bfs(x,y)<<endl;
        return 0;    
    }
    

    我下午问了杰哥一下,杰哥给我介绍了两种思路下面的三种方法
    真的杰哥这些思路都是很经典很厉害的思想

    思路一

    就直接引用原话啦
    在这里插入图片描述
    我看着杰哥的代码理解了一下,大概意思就是
    1.首先正着从起点进行一遍BFS找到终点,再从终点反正来一遍BFS找到起点
    2.开创俩个数组dis1[N][N]和dis2[N][N]分别用于记录正向搜索每一次的出队时的每一个离起点的层数和反向搜索每一次的出队时的每一个点离起点的层数
    3.此时通过BFS我们已经知道最短路径的长度了,某个点只要能满足
    dis1[x][y]+dis2[x][y]=minrode
    那么这个点就一定是这个迷宫最短路径上面的点
    4.通过这样我们就能知道该迷宫的最短路径表示
    在这里插入图片描述
    代码展示如下:

    include<queue>
    #include<stdio.h>
    #include<string.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=1005;//地图最大宽度 
    struct node{
    	int x,y;
    };
    queue<node>que;
    int n,m,minrode=0;
    int fx,fy;//记录终点的坐标值 
    char map[N][N];
    int dx[]={0,1,0,-1};
    int dy[]={1,0,-1,0};
    int dis1[N][N];//正向记录层数的数组 
    int dis2[N][N];//逆向记录层数的数组 
    bool mark[N][N];//用来标记是不是在最短路上 
    
    void BFS(int dis[][N],int sx,int sy){
    	
    	for(int i=0;i<n;i++)//初始化记录层数的dis数组 
    		for(int j=0;j<m;j++)
    			dis[i][j]=-1;
    	
    	while(!que.empty())que.pop();//初始化队列 
    	
    	que.push((node){sx,sy});//放入起点 
    	dis[sx][sy]=0;//(sx,sy)为起点 
    	
    	while(!que.empty()){
    		node cur=que.front();//当前状态
    		que.pop();
    		for(int i=0;i<4;i++){
    			node nxt;
    			nxt.x=cur.x+dx[i];
    			nxt.y=cur.y+dy[i];
    			if(map[nxt.x][nxt.y]=='#'){//墙壁无法通行 
    				continue;
    			} 
    			if(nxt.x>=0&&nxt.x<n&&nxt.y>=0&&nxt.y<m&&dis[nxt.x][nxt.y]==-1){
    				if(map[nxt.x][nxt.y]=='T'){
    					fx=nxt.x;fy=nxt.y;
    					minrode=dis[cur.x][cur.y]+1;
    					return ;
    				}
    				else{
    				que.push(nxt); 
    				dis[nxt.x][nxt.y]=dis[cur.x][cur.y]+1;//不断的记录层数
    			}
    			}
    		}
    	}	
    } 
    
    void Print(int x,int y){//对起点进行上下左右找,满足的mark=true的进行输出
    	printf("%d %d\n",x,y);	
    	for(int i=0;i<4;i++){//同样的进行遍历判断 
    		int nx=x+dx[i];
    		int ny=y+dy[i];
    		
    		if(nx<0||nx>=n||ny<0||ny>=m||map[nx][ny]=='#')continue; 
    		
    		if(dis1[nx][ny]<dis1[x][y])continue;//***不能往回走不能成环 
    		
    		if(mark[nx][ny]){
    			Print(nx,ny);
    			break;//避免输出多条最短路 
    		}
    	}
    }
    
    
    int main(){
    	int qx,qy;
    	scanf("%d%d",&n,&m);
    	for(int i=0;i<n;i++){
    		scanf("%s",map[i]);
    	}
    	for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'S') {//找到迷宫的起点
                    qx = i;qy = j;
                }
            }
        }
    	BFS(dis1,qx,qy);//正向遍历 
    	BFS(dis2,fx,fy);//逆向遍历 
    	
    	memset(mark,0,sizeof(mark));//初始化最短路径记录数组 
    	
    	int total=minrode;
    
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			if(dis1[i][j]+dis2[i][j]==total){ 
    				mark[i][j]=true;//如果符合的话就是最短路,mark数组该点标记为true 
    			}
    		}
    	}
    	
    	Print(qx,qy);//调用print函数进行打印mark上面为true的点 
    	
    	return 0;
    }
    
    

    重点来了,关键关键关键!!!

    if(dis1[nx][ny]<dis1[x][y])continue;//***不能往回走不能成环 
    

    这一步真的print函数的重点所在
    为什么能打印满足mark数组等于true的点,我们要知道一个迷宫不只有一条最短路,有很多点都满足这个这个条件,那么万一出现这种成环的情况怎么办?
    在这里插入图片描述
    按照print函数层次遍历的算法,在A点可以会向右跑了,这样根本不是最短路,但是我们知道按照最短的遍历,dis1数组上面符合最短路的下一步的值一定会比这一步要大,我们在这里就可以做出限制条件,这样一方面就避免了往回回溯的可能,也避免了成环跑掉的可能,如果最短路不成环的话,我们也可以对已经打印出来的点进行标记,标记后不能打印,这样也可以实现避免了往回回溯的可能。

    思路二

    照片如图
    在这里插入图片描述
    这种思路大概就很像树型结构的寻找父亲,保存此时的坐标的信息和上一个坐标的信息,从终点往回不断的找,找父亲的父亲的父亲…直到起点为止,这样找下来也是一种最短路,像我这样就只能想到一些笨办法
    第一种就是直接建立树,这个树结点不仅保存该点的值,还保存下面儿子的地址和上面父亲结点的地址,这样一来直接就可以通过树来找到了,要写树代码量真的太大了,舍去。。。
    第二种就是建立结构体包含四个值,自己的XY坐标值,父亲的XY坐标值,从结点开始利用父亲的XY值遍历整个序列,看谁的XY和这里的对应就找到了父亲结点,依次进行,但是这样的复杂度太高了吧。。。果断舍去。。。
    好的,下面就介绍杰哥给的几种复杂度低的算法

    算法一

    这样怎么说呢,有点类似树的双亲孩子表示法,建立一个数组,里面装着每一个结点,结点后面跟着父亲结点在数组里面的下标值,就是一个结构体数组,通过每一个结点里面的父亲结点在数组里面的下标值就可以找到父亲结点了,通过在数组里面存储下标来回溯,很棒呀。
    在这里插入图片描述
    代码如下:

    /*Input:默认以(0,0)为起点,(4,4)为终点,随便改一下就行 
    5 5
    ...##
    ##.##
    ....#
    .##.#
    .....*/ 
    #include<stdio.h>
    #include<string.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=1005;
    struct node{
     int x,y,lastId;
    }que[N*N];//最大有N*N个结点,没有墙全是路 
    
    int n,m;
    char map[N][N];
    
    int dx[]={0,1,0,-1};
    int dy[]={1,0,-1,0};
     
     void Print(node cur){
     if(cur.lastId!=-1){ 
      Print(que[cur.lastId]);//递归的算法,先找到第一个结点后输出值
     }
     printf("%d %d\n",cur.x,cur.y);//先找后输出就是顺序,先输出后找就是逆序 
    }
    
    int dis[N][N];
    void BFS(){
     
     memset(dis,-1,sizeof(dis));
     
     int L=1,R=0;
     que[++R]=(node){0,0,-1};//lastId=-1表示没有父亲 
     dis[0][0]=0;//(0,0)为起点 
     
     while(L<=R){
      node cur=que[L++];//当前状态
      
      for(int i=0;i<4;i++){
       node nxt;
       nxt.x=cur.x+dx[i];
       nxt.y=cur.y+dy[i];
       nxt.lastId=L-1;//当前状态的上一个状态在que数组中的下标为L-1 
       
       if(nxt.x==n-1&&nxt.y==m-1){//(n-1,m-1)为终点 
        Print(nxt);
        return; 
       }
       if(map[nxt.x][nxt.y]=='#'){//无法通行 
        continue;
       } 
       
       if(nxt.x>=0&&nxt.x<n&&nxt.y>=0&&nxt.y<m&&dis[nxt.x][nxt.y]==-1){
        que[++R]=nxt; 
        dis[nxt.x][nxt.y]=dis[cur.x][cur.y]+1;
       }
      }
     } 
    } 
    
    int main(){
     scanf("%d%d",&n,&m);
     for(int i=0;i<n;i++){
      scanf("%s",map[i]);
     }
     BFS();
     return 0;
    }
    

    算法二

    我真的有点被这个算法惊讶到了
    利用二维数组可以存储四个值,一般来数二维数组值可以存储三个值(x,y,本身点的信息),但是这里可以使用两个二维数组存储x,y,fx,fy的信息,分而和,和而找,既然知道了这四个信息,我们也就不难去回溯了
    代码如下:

    #include<queue>//还是和上面一样,(0,0)起点,(n-1,m-1)终点 
    #include<stdio.h>
    #include<string.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=1005;
    
    struct node{
     int x,y;
    };
    
    int fax[N][N];
    int fay[N][N];
     
    queue<node>que;//对列 
    
    int n,m;
    char map[N][N];
    
    int dx[]={0,1,0,-1};
    int dy[]={1,0,-1,0};
     
    int dis[N][N];
    
    void Print(int x,int y){
     if(x!=-1&&y!=-1){
      Print(fax[x][y],fay[x][y]);
      printf("%d %d\n",x,y);
     }
    }
    
    void BFS(){
     
     memset(dis,-1,sizeof(dis));
     
     que.push((node){0,0});
     dis[0][0]=0;//(0,0)为起点 
     
     fax[0][0]=-1;
     fay[0][0]=-1;
     
     while(!que.empty()){
      node cur=que.front();//当前状态
      que.pop();
      for(int i=0;i<4;i++){
       node nxt;
       nxt.x=cur.x+dx[i];
       nxt.y=cur.y+dy[i];
       
       if(map[nxt.x][nxt.y]=='#'){//无法通行 
        continue;
       } 
       
       if(nxt.x>=0&&nxt.x<n&&nxt.y>=0&&nxt.y<m&&dis[nxt.x][nxt.y]==-1){
        que.push(nxt); 
        dis[nxt.x][nxt.y]=dis[cur.x][cur.y]+1;
        fax[nxt.x][nxt.y]=cur.x;
        fay[nxt.x][nxt.y]=cur.y;
       }
      }
     } 
    } 
    
    int main(){
     scanf("%d%d",&n,&m);
     for(int i=0;i<n;i++){
      scanf("%s",map[i]);
     }
     BFS();
     Print(n-1,m-1);
     return 0;
    }
    

    其他的简单的BFS一样,最为精华的我展示出来了

    void Print(int x,int y){
     if(x!=-1&&y!=-1){
      Print(fax[x][y],fay[x][y]);
      printf("%d %d\n",x,y);
     }
    }
    

    难以言语,分开来,合起来,分开来,再合起来…
    道家的思想,
    **分而治之,和而为之 **

    嗯嗯,就介绍完啦,你是否got到啦

    是不是肥肠的斯国一

    感谢杰哥这么细心的指导

    我终于也掌握BFS啦

    哈哈哈哈

    展开全文
  • 一个普通、标配、差强人意的Dijkstra算法包含以下过程(任意... // G[i][j],表示i到j有路径,其值为路径长度。没有路径则设为INF int N; //结点个数 int D[MAX_NODES]; //表示从源点v0开始,到各个结点的路径长...
  • 掌握图的存储方法和最短路径算法。 [实验内容] 设计一个校园导游程序,为来访的客人提供各种信息查询服务。测试数据根据实际情况指定。提示:一般情况下,校园的道路是双向通行的,可设校园平面图是一个无向图。...
  • 从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大,这也是所谓的初始化工作; 对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。...
  • 今天小编就为大家分享一篇关于Dijkstra算法最短路径的C++实现与输出路径,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
  • 最短路径+路径输出

    千次阅读 2018-11-15 11:47:43
    根据输入的图形,输入起点和终点,求出最短路径最短路径的 长度。 具体步骤 编写一段代码,接收键盘的输入定点的数量,并以输入的整数对作为边来建立图形的邻接矩阵(无向权重图)。 例如 : 5,6,12 表示定点 5...
  • 本文给大家分享的是python 无向图最短路径算法:请各位大大指教,继续改进。(修改了中文字符串,使py2exe中文没烦恼),需要的朋友可以参考下
  • java数据结构课程设计校园超市选址中,我们要用到弗洛伊德算法输出最短路径最短路径长度,输出的路径用点--->点表示,本文件提供输出的代码。
  • 迷宫问题 题意:给你一个迷宫,迷宫一定有解,让你求出最短路径,并输出此条路径。 解题思路:对于这种题目,我们已经见怪不怪了,关键就是要记录前驱结点,由于此题数据量小,我们可以直接使用递归来实现,如果数据...
  • 迷宫问题最短路径C语言printf("最短路径如下:\n"); printf("长度: %d\n",minlen); printf("路径: "); for(k=0;k;k++) printf("(%d,%d) ",Path[k].i,Path[k].j); printf("\n"); return 0;
  • Qt+C++校园最短路径.zip

    2019-12-29 14:54:43
    根据校园各主要生活、学习、活动等场所、地点,设计并实现基于校园各场所之间的最短路径漫游。 要求: (1)掌握数据结构的输入/输出; (2)设计与实现校园各主要场所之间的最短路径算法; (3)根据场所之间的...
  • 本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法)。分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法——通过边实现松弛 # 指定一个点到其他各顶点的路径——单源最短路径 # 初始...
  • 一、最短路径 最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括: 确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。 ...
  • 最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
  • 最短路径最短路径重要性不言而喻,下面直接分析两个算法。 分类: 1:从某个源点到其余个点的最短路径 迪杰斯特拉(Dijkstra)算法 2:每一对之间的最短路径 弗洛伊德(Floyd)算法 一:存储结构...
  • 通过一个nex数组来记录路径,nex[i][j]表示从i到j的最短路径从i开始走的第一个点。这样整个最短路径中的nex[i][j]都是这个含义,则就表示出了最短路径。 #include using namespace std; const int maxn = 1005; int...
  • 可进行有向图的创建,所有简单路径的遍历,并找出其中的最短路径和最长路径。
  • 数据结构课程实践:1. 问题描述: 以顶点表示校平面图中各景点,要有景点名称、代号、简介等信息;以边表示路径,存放路径长度等信息(路径长度可以估算,以米为...(3)任意两个景点之间的最短路径。 我用java实现的
  • 最短路径: 在一个带权图中,顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和,定义为该路径的带权路径长度,把带权路径最短的那条路径称为最短路径。 DiskStra算法: 求单源最短路径,即求一个顶点到...
  • 有向网(有权值) 存储:邻接矩阵 最短路径:迪杰斯特拉算法 输出部分:邻接矩阵输出,最短路径输出 头 #include #include #define Max 100 //定义顶点最大容量 #define MaxWeight 32767 //表示极大值 //二进制的原码...
  • #include <stdio.h> #include <...//二位数组保存每对顶点中的最短路径长度 int **nextVex;//二维数组保存vi到vj最短路径上vi后续节点的下标 }ShortPath; typedef struct GRAPHMATRIX_STRU {
  • Dijkstra算法输出最短路径

    千次阅读 2019-06-21 17:30:25
    1. 之前我们使用Dijstra算法可以求解出从源点到达其余顶点的最短距离,那么怎么样求解出源点到达v顶点最短距离中所经过的顶点呢? 2. 算法的执行过程如下: ① 其实也很简单,我们只需要在原来使用Dijstra算法求解...
  •  { // 第n个最短,在最后一次之前已经在不断更新的,所以,每次都是最短比最新的,取最短。  dis[j]=dis[mini]+map[mini][j];  }  }  }  } } int main() {  int n,m;  int i,j;  struct mmm t;  scanf("%d...
  • 题目描述 题目描述 ...每组测试数据输出m行,代表查询的两个结点之间的最短路径长度 测试样例 输入 1 8 4 2 3 4 5 6 -1 -1 -1 -1 7 -1 -1 8 -1 -1 -1 1 6 4 6 4 5 8 1 输出 2 4 2 4 void short_tree_path()
  • JAVA|迷宫问题输出最短路径

    千次阅读 2019-12-16 11:03:06
    0.背景 本学期Java课程设计选题为迷宫游戏。...2、最短路径是否小于等于游戏给出的步数限制? 3、点击最短生成路径按钮显示最短路径。 游戏的整体框架戳此处链接https://blog.csdn.net/qq_42391904/article/detai...
  • 要实现的是输入一张 图,起点,终点,输出起点和终点之间的最短路径。 广度优先搜索 适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快 复杂度:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 73,671
精华内容 29,468
关键字:

最短路径输出