登陆注册
37240300000224

第224章 加权有向图(下)

既然是加权有向图,那在这个场景下,有向性怎么体现呢?

可以观察到,图中的每一个点都有8个方向可以离开。

东,南,西,北,东北,东南,西南,西北。

等于说,每个点和它周边的8个点都可以构成一条边。

而边的权重等于两个点海拔差的绝对值。

这样,这幅地图就转化为了加权有向图。

然后,再求总权重最小,或者说总海拔差最小(最节省体力)的路径。

对于求加权有向图两个点之间的最短路径,有一种经典的算法:

Dijkstra(迪杰斯特拉)算法。

它会构造一棵最短路径树,提供从出发点[0,0]到图中任意一点的最短路径。

那有了这么一棵树,要找出发点到目的地[3,3]的最短路径不就是很方便的事情了么?

杨成很快就搞定了这个算法。

不过,他发现了一个让人懊恼的问题:

JavaScript在以前的版本一直不支持优先级队列。

而优先级队列是这个算法能够加快效率的关键。

他只好使用数组来做替代。

从数组中查找最小的项,并且将其移除,可是一个开销不小的操作呢!

同类推荐
  • 丧尸国度之特种兵

    丧尸国度之特种兵

    一次意外世界变成了地狱,无数的丧尸席卷整个世界,两个身负拯救世界重担的特种兵为了这最后的任务,在这个末日中尸挡杀尸,人挡杀人!
  • 假面骑士OZ

    假面骑士OZ

    主角是个没有梦想,没有工作,没有家庭的男人。但是对任何事情都提不起兴趣的他,从来都不认为自己是如此的不幸。这样的男人得到了变身腰带,投身于和怪人的激战中。敌方是不知从哪个时代起就存在的异形五人组。因某种原因身体的一部分有残缺,为了有一个完整的实体而寄望于古币。他们为了增加古币而繁殖更多的怪人,而怪人们的成长则依赖于吞食人类的欲望。最终的欲望变成了袭击人类。赐予主角腰带的神秘人竟是异形五人中的一员。他们以得到古币为目的,OZ自己也同样靠收集古币获得新的力量。
  • 尘埃下的国度

    尘埃下的国度

    不管你在哪里,地铁里亦或是餐桌上?这不重要,请你抬头看看四周,几乎所有人都将目光聚集在那一块小小的屏幕上,仿佛掌间那方寸之地囊括了整个世界,他们感受着陌生人的悲欢离合,也分享自己的喜怒哀乐,他们罔顾海洋深处的哀鸣,漠视森林边缘的颤栗,更加忽略脚底下弱者发出的歇斯底里的呐喊。他们生活在一个弱肉强食的时代,却早已忘记了弱肉强食的残酷。假如某一天,某种神秘而可怕的力量入侵人类文明,以法律为基准的秩序开始崩塌,人类又将何去何从?
  • 硅时代

    硅时代

    思维是什么?人脑对客观事物的本质属性和事物之间内在联系的规律性所做出的概括与间接的反映。人脑对客观事物的本质属性的认知是什么?是记忆,是记忆对客观事物的描述,事物之间内在联系的规律是什么,是人脑对事物主观认知的相同点,换句话说是搜索记忆,并建立联系。而记忆是以生物电震荡的形势存储与脑域之中的,大脑是什么?碳氢化合物,既然碳氢化合物可以存储生物电,那么硅基芯片为什么不能呢?!
  • 异空星尘

    异空星尘

    生灵的行为皆有其本质,无论它是否源于自由思想的欲望,都反映着同一个理念:战争。自从生命诞生的那一刻起,这场战争默默地开始,生灵对未知未来的憧憬从未停止,一次次地以牺牲面对灭顶之灾,生命逐渐繁衍。思想的演变,慢慢地从自然规则的牢笼中挣脱,为了欲望,不惜以血色渲染脚下的大地,挑战神明的意志。真理崩陷,在无尽的杀戮面前,它不过只是路边不起眼的石子,眼睁睁地看着所爱的事物被逐个毁灭。世界的天平,虚伪的平衡法则,用自己的砝码,将自己推向没有真理的灭亡。生存,本身就是一种罪恶。亿万年,战争终结之时,零落的真相将会给予这世界前所未有的制裁,誓永不回首。谁又是最后的生存者?
热门推荐
  • 恶魔索爱,强势来袭

    恶魔索爱,强势来袭

    一场意外,他们相遇,她一味地想逃,逃离这个恶魔的控制,可他却只手遮天,用所有人的性命要挟她,囚禁她,断了她的念头。而她也在某个时候把自己也陷入这个恶魔的变态的爱中……
  • 你好,我的佳人

    你好,我的佳人

    从自己看小说,到渐渐的开始写小说,希望大家多多支持。
  • 诸神寂灭之猎神者

    诸神寂灭之猎神者

    说,当火热的星辰从天空坠落,九州崩裂,穹城关闭,侍童从风之源走出,神罚便降临于世,即是诸神寂灭的时代到来,这个世界所有的一切都将被彻底的大清洗。在纷乱的末世中,集权者之间讳莫如深的恩怨纠葛,越演越烈。在追逐权利和欲望的过程中,在御灵士们激烈的厮杀中,阴谋和背叛不断冲击着曾经坚信不疑的真理,将爱情,亲情,友情碾压的支离破碎,似乎一切都笼罩在了浓重的阴霾中……(这是一个慢热型的故事,阿洛也是第一次写这种风格的故事,请各位多多包涵!也请多多支持!)
  • 九鼎天神

    九鼎天神

    传说在远古时期,出现了一位实力无比强横的天地大能,凭借着自己强横的实力,统一了大陆,后世的人都尊他为天神。他建立起了伟大的功业,后来据说成神之后破碎虚空去往了神界。先前为了巩固自己的统治,显示自己至高无上的权利,遂命匠师聚集天下的各种稀有金属铁器,铸造九鼎,象征着统一天下。后来天神死后,九鼎便不知踪迹。但传说得九鼎者得天下,不仅仅是因为那是权利的象征,更有人言,在九鼎之内有能够成神得秘密。主人公蒙进,年少丧父,母亲不知所踪。但看我们的主人公从所谓的废材炼体成神,践踏所谓的强者,聚齐九鼎,平定乾坤。
  • 江南才子向志成

    江南才子向志成

    当代现实主义长篇爱情小说《江南才子向志成》,以上世纪改革开放前后这个充满挑战的时代为大背景,生动形象描述了瓷都景德镇斗彩园里江南才子向志成,心心相惜,风雨同舟,与五位邻居妹妹之间的情感纠葛,及其自强不息的奋斗故事。蕴含了与命运不屈,和时代共舞,一段凄美而动人的心路历程,糅合了时代丰富而杂复的内容,让人身临其境,感同身受,呈现了对过去朴素而美好生活的不尽留恋,更是渴望现在和将来,对人世间一种尊爱女性的热情呼唤。
  • 傲视曙光

    傲视曙光

    前世,他是一代枭雄,却被视为大魔王,今生,他天生灵力,却因拥有多属性而无法修炼,不甘平庸,他自创功法,突破瓶颈,修炼问天决,修为大增,八大属性万箭齐发,如虎添翼,且看废材逆天改命,所向披靡,天下无敌!
  • 克服困难的方法

    克服困难的方法

    一位伟大的艺术家深知逆境出人才的道理,所以当有人问他,那位跟他学画的青年能否成为一位伟大的艺术家时,他便坚定地回答:“决不可能!因为他每年有6000英磅丰厚的收入呢!”艰苦的环境能够造就出成功的人才,而富裕的环境只会令人堕落。
  • 夜瞳

    夜瞳

    平凡一少年,出生在一名为归始的大陆,天生拥有诡异眼瞳的他无法修炼隐气,家族的人纷纷嘲笑他,少年被一名老者打的重伤意识处于混沌之间。。。。遇到了一中年男子,男子。。。。。。
  • 修仙大学校长

    修仙大学校长

    “老师,我那份关于高聚能灵块反应堆的研究你看了吗?”“你还敢说,我试了下,弄到一半就爆炸了!”“老师,我那份金属性修行者体质研究你看了吗?”“看了,我不认为金属性修行者就一定要找个土属性的道侣!”“校长,泛大陆联合议会准备举行议长大选,邀请您出席。”“跟他们说我没空,最近在搞新研究。”“校长,您夫人来了。”“嗯?哪个?”“王八蛋,柯之道,你到底有几个?”“啊,我突然觉得我的境界马上要突破了,我需要闭关一段时间。”
  • 舍檐低语

    舍檐低语

    由著名作家衣向东作序并题写书名,由丛书主编著名作家纪广洋作序。全书收录发表过的作品约70来篇。内容清新隽永,值得一读。