登陆注册
37240300000224

第224章 加权有向图(下)

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

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

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

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

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

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

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

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

Dijkstra(迪杰斯特拉)算法。

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

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

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

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

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

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

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

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

同类推荐
  • 恐怖默示录

    恐怖默示录

    我不知道还能活多久。也许整个世界只有我一人。我只能在每天深夜,写下最后一天的日记。希望,明天,我还活着。——佐南
  • 融合次元

    融合次元

    2015年,一场突如其来的太阳黑子爆发,瞬间改变了这颗星球。那本来应该存在于幻想中生物,被宇宙中不可预知的伟力赋予了具现化的能力。但是带来的,却是深深的绝望。无数的丧尸,可怕的怪物,疯狂的机械生物,耳熟能详的英雄,记忆深处的偶像…………他们,都将作为你的敌人,你的猎物。杀戮,成长,掠夺,力量,背叛……这就是末日的旋律。空手拆高达,谈笑灭千军,傲视凌云间……都不再是奢望。奇特的人物进化,不一样的末日旋律,这里是地球,这里超脱了次元融合了次元。
  • 桑海传说

    桑海传说

    桑海,一场关于上古诸神的传说,一场末世与新生的轮回,是神还是人?所谓神话由何而来,又向何而去?究竟是命运的在重复还是人为控制?迷失的是未来还是过去?那些穿越古今的未解之谜将一一展现在大家面前。作者简介无能……
  • 末世之太上无情

    末世之太上无情

    张漠回到了末世初始的三天前,陪伴他的只有一把名叫玄心的剑………
  • 穿越农家贵女

    穿越农家贵女

    空间在手,美食我有,一心养好小正太,顺便养成男人。本文温馨!
热门推荐
  • 倾之冰魄

    倾之冰魄

    一切的开始只因为你的眼神,一切的结尾一只因为你的那句话.
  • 在我肩上

    在我肩上

    “掌门,我认为这名弟子。。噗”烈长老刚想说点反对意见,一声响屁响起。所有人都怔住了。烈长老自己也怔住了,烈长老左右两人都捂住了嘴巴。“咳。。掌门师兄,我认为。。噗。”烈长老毕竟见过大世面,稳定一下情绪。刚想再说时又是一声响屁,比上次还要响。烈长老左右两位长老甚至都都悄悄的把椅子向后面挪去。“我认为。。噗”烈长老黑脸通红,刚想在说时,又是一声响屁。这声比上次更加的响,回声都不时在大殿回荡,烈长老身后的两位长老花白的胡须甚至都被这屁吹的咧咧的打岔。
  • 丹鼎仙路

    丹鼎仙路

    十年萌醒,一朝凤鸣。且看少年如何以身体为鼎炉凭内丹之术,开启属于他的丹鼎仙路。
  • 挪移虚空

    挪移虚空

    人类在星球之上,星球属于宇宙,宇宙只属于位面空间的冰山一角,位面空间只是无尽虚空的一份子.............从三维空间到四维时空,探索无尽的虚空世界和世界的尽头。
  • 仙国霸唱

    仙国霸唱

    和诸王政治对撞!与诸将战场攻杀!同诸子百家争鸣!他赵崝定要在这璀璨的时代中,争他一个如画江山来!
  • 复仇小姐

    复仇小姐

    她本是大户人家的丫鬟,却不想竟意外失忆,也没有想到会遇见那个人,当记忆全都回来,看见小姐害死自己的爱人她该何去何从?当一切都失去,是否只能孤注一掷?
  • 为你拥有良好心态和习惯

    为你拥有良好心态和习惯

    世界卫生组织指出21世纪健康人应具备10大要素,其中具备“良好的心态”和“良好的生活习惯”都是健康人的重要标志。本书在上篇介绍了良好的心态对健康的有益作用,各类人群如青少年,大学生,教师,老年人如何拥有良好心态,克服不良心态等:下篇则介绍了具备良好习惯是健康人的人格魅力,是健康体魄之本,它能帮助人们走向成功并告诉你怎样从小培养良好生活习惯,成年人怎样改变不良习惯,防止疾病发生等。
  • 异界之成神记

    异界之成神记

    神,天地万物的创造者、主宰者。茫茫的混沌宇宙究竟何人为神,是西方世界中地狱的撒旦和他的恶魔,还是天堂的上帝耶和华和他的天使,亦或是奥林匹斯山上宙斯和他的众神,再或者是东方世界中天庭众神、各路仙家大能、高高再生的六圣、天道鸿钧?不是,他们都不是神。虽然他们都有着超凡的实力,被世间众人敬仰,但是他们并不能称为神,因为混沌大道之下,只有一类人可以成为神,而他们并不在其中……。传说中的世界,传说中的人。背叛、诱惑、绝望,经历百态,留我本心,方为神!
  • 爱未明人心悲

    爱未明人心悲

    六年前,他们两个曾是最要好的玩伴,无话不说,有福同享有难同当。如今,他们久别重逢,一见面,她就被他夺走了她初吻,她讨厌他。之后两人却因为他的父母有意撮合他们而住在了同一屋檐下。慢慢的,她发觉自己爱上了他了!最终,她觉得他还是喜欢他的前女友的,所以,她再次忍痛离开了!
  • 中国历代张天师评传(第2卷)

    中国历代张天师评传(第2卷)

    本书论述并总结了自第十二代至第三十代张天师的生平事迹、道法特点,以及他们对其所处时代的社会贡献,并对他们在中国道教史上的历史地位作出了客观公允的评价。