文档章节

最短路径问题之一:忽略权重直接求最短路径

蓝翔统战部
 蓝翔统战部
发布于 2015/06/24 10:18
字数 585
阅读 24
收藏 0

前两天又跟同学聊起了最短路径问题,决定将部分理解和体会整理一下

实际路径图如下,忽略权重


 
首先根据实际路径图定义一个Map,map中存放一个当前位置,和与它相连的各位置.
查找路径时,
1.根据起点在map中从当前位置查找,
2.查找该当前位置所对应与它相连的各位置,并按该方法一直查找,直至找到终点
3.中间过程中,若在相连位置列表中出现已经遍历过的节点时,则不再遍历该节点
4.找到最终结果后,逆向推回来,并将结果整理

例如:

求从5到6的最短路径

首先观察5的位置,发现跟5关联的有1、3、4,然后将1、3、4记下来,并记录他们是从5过来的,然后观察1,发现跟1相连的有2、3、4,但是其中3、4都已经出现过了,所以不必要再记录,于是将2记录下来,并记录2是从1过来的,然后观察与2相连的节点,发现跟2相连的节点有3、6。   把3忽略,找到6,并且记录6是从2过来的,现在根据终点和他们每一次的来源点反向找回去,即可找到最佳路径。


lua代码实现
local map = {
    [1] = {2,3,4,5},
    [2] = {1,3,6},
    [3] = {1,2,4,5},
    [4] = {1,3,5},
    [5] = {1,3,4},
    [6] = {2},
}
 
-- 是否存在
function isExits(arr, value)
    for i,v in ipairs(arr) do
       if v.node == value then return true end  
    end
    return false
end
 
function findWay(map, startNode, endNode)
    -- 足迹
    local foots = {
        {node=startNode, from=nil} -- node 节点 from 从哪里来
    }
    -- 遍历足迹
    for i1,v1 in ipairs(foots) do
        -- 遍历v1的相邻节点
       for i2,v2 in ipairs(map[v1.node]) do
            -- 是否已经走过此地
            if not isExits(foots, v2) then -- 如果没有走过此
                foots[#foots + 1] = {node=v2, from=v1}
                if v2 == endNode then  
                    --TODO 已经找到,是写整理输出。  
                    local way = {endNode}
                    local from = v1
                    while from ~= nil do
                        way[#way +1] = from.node
                        from = from.from
                    end
                    return way
                end
            end
       end
    end
end
 

求节点5到节点6的最短路径,最短路径可能不止一种,该算法会打印其中之一
local way = findWay(map, 5,6)
for i,v in ipairs(way) do
   print(v)
end

© 著作权归作者所有

蓝翔统战部
粉丝 2
博文 5
码字总数 2438
作品 0
海淀
程序员
私信 提问
pgrouting图插件在存储配置管理系统的应用

作者简介 帅宇,资深DBA,从事Oracle数据库管理和SQL开发超过15年,3年+PG数据库开发经验,擅长数据库建模设计,SQL开发,SQL性能调优。现就职于平安科技数据库技术部,云数据库架构师,负责...

PostgreSQL中文社区
06/15
0
0
图的单源最短路径(Dijkstra算法)

在许多路由问题中,寻找图中一个顶点到另一个顶点的最短路径或最小带权路径是非常重要的提炼过程。正式表述为,给定一个带权有向图 , 顶点到中顶点的最短路径为在边集中连接到代价最小的路径...

2017/12/19
0
0
最短路径问题算法(Shortest Path Problems' Algorithms)

版权声明:本文为博主原创文章,欢迎转载,但请注明出处,谢谢愿意分享知识的你~~ https://blog.csdn.net/qq_32690999/article/details/84953063 最短路径问题算法 作者:Bluemapleman(tomq...

蓝色枫魂
2018/12/11
0
0
最短路径问题---Dijkstra算法详解

前言 Nobody can go back and start a new beginning,but anyone can start today and make a new ending. Name:Willam Time:2017/3/8 1、最短路径问题介绍 问题解释: 从图中的某个顶点出发......

qq_35644234
2017/03/08
0
0
基于图论数据关联方法的目标跟踪

目标跟踪方法包括生成类方法和判别类方法。与生成类方法最大的区别是,判别类方法分类器采用机器学习,训练中用到了背景信息,这样分类器就能专注区分前景和背景,所以判别类方法普遍都比生成...

韦德爱老詹
2018/04/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mysql的sql_mode模式

sql_mode 是一个很容易被忽视的配置,宽松模式下可能会被输入一些非准确数据,所以生产环境下会要求为严格模式,为了保持生产环境和开发环境,测试环境一致性,我们开发环境和测试环境也要配...

贾峰uk
23分钟前
2
0
Qt程序打包发布方法(使用官方提供的windeployqt工具)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/toTheUnknown/article/details/81748179 如果使用到了Qt ...

shzwork
52分钟前
7
0
MainThreadSupport

MainThreadSupport EventBus 3.0 中的代码片段. org.greenrobot.eventbus.MainThreadSupport 定义一个接口,并给出默认实现类. 调用者可以在EventBus的构建者中替换该实现. public interface ...

马湖村第九后羿
今天
3
0
指定要使用的形状来代替文字的显示

控制手机键盘弹出的功能只能在ios上实现,安卓是实现不了的,所以安卓只能使用type类型来控制键盘类型,例如你要弹出数字键盘就使用type="number",如果要弹出电话键盘就使用type="tel",但这...

前端老手
今天
8
0
总结:Raft协议

一、Raft协议是什么? 分布式一致性算法。即解决分布式系统中各个副本数据一致性问题。 二、Raft的日志广播过程 发送日志到所有Followers(Raft中将非Leader节点称为Follower)。 Followers收...

浮躁的码农
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部