爱看小说网

繁体版 简体版
爱看小说网 > 编程之战 > 第二百二四章 加权有向图(下)

第二百二四章 加权有向图(下)

章节错误,点此举报(免注册),举报后维护人员会在两分钟内校正章节内容,请耐心等待,并刷新页面。

既然是加权有向图,那在这个场景下,有向性怎么体现呢?    可以观察到,图中的每一个点都有8个方向可以离开。    东,南,西,北,东北,东南,西南,西北。    等于说,每个点和它周边的8个点都可以构成一条边。    而边的权重等于两个点海拔差的绝对值。    这样,这幅地图就转化为了加权有向图。    然后,再求总权重最小,或者说总海拔差最小(最节省体力)的路径。    对于求加权有向图两个点之间的最短路径,有一种经典的算法:    Dijkstra(迪杰斯特拉)算法。

『加入书签,方便阅读』