(阅读库www.yuedsk.com)(阅读库 www.yuedsk.com) 既然是加权有向图，那在这个场景下，有向性怎么体现呢？
可以观察到，图中的每一个点都有8个方向可以离开。
东，南，西，北，东北，东南，西南，西北。
等于说，每个点和它周边的8个点都可以构成一条边。
而边的权重等于两个点海拔差的绝对值。
这样，这幅地图就转化为了加权有向图。
然后，再求总权重最小，或者说总海拔差最小（最节省体力）的路径。
对于求加权有向图两个点之间的最短路径，有一种经典的算法：
Dijkstra（迪杰斯特拉）算法。
它会构造一棵最短路径树，提供从出发点[0，0]到图中任意一点的最短路径。
那有了这么一棵树，要找出发点到目的地[3，3]的最短路径不就是很方便的事情了么？
杨成很快就搞定了这个算法。
不过，他发现了一个让人懊恼的问题：
JavaScript在以前的版本一直不支持优先级队列。
而优先级队列是这个算法能够加快效率的关键。
他只好使用数组来做替代。
从数组中查找最小的项，并且将其移除，可是一个开销不小的操作呢！阅读库 www.yuedsk.comyuedsk www.yuedsk.com
可以观察到，图中的每一个点都有8个方向可以离开。
东，南，西，北，东北，东南，西南，西北。
等于说，每个点和它周边的8个点都可以构成一条边。
而边的权重等于两个点海拔差的绝对值。
这样，这幅地图就转化为了加权有向图。
然后，再求总权重最小，或者说总海拔差最小（最节省体力）的路径。
对于求加权有向图两个点之间的最短路径，有一种经典的算法：
Dijkstra（迪杰斯特拉）算法。
它会构造一棵最短路径树，提供从出发点[0，0]到图中任意一点的最短路径。
那有了这么一棵树，要找出发点到目的地[3，3]的最短路径不就是很方便的事情了么？
杨成很快就搞定了这个算法。
不过，他发现了一个让人懊恼的问题：
JavaScript在以前的版本一直不支持优先级队列。
而优先级队列是这个算法能够加快效率的关键。
他只好使用数组来做替代。
从数组中查找最小的项，并且将其移除，可是一个开销不小的操作呢！阅读库 www.yuedsk.comyuedsk www.yuedsk.com
如果您中途有事离开，请按CTRL+D键保存当前页面至收藏夹，以便以后接着观看！