章节错误,点此举报(免注册),举报后维护人员会在两分钟内校正章节内容,请耐心等待,并刷新页面。
既然是加权有向图,那在这个场景下,有向性怎么体现呢? 可以观察到,图中的每一个点都有8个方向可以离开。 东,南,西,北,东北,东南,西南,西北。 等于说,每个点和它周边的8个点都可以构成一条边。 而边的权重等于两个点海拔差的绝对值。 这样,这幅地图就转化为了加权有向图。 然后,再求总权重最小,或者说总海拔差最小(最节省体力)的路径。 对于求加权有向图两个点之间的最短路径,有一种经典的算法: Dijkstra(迪杰斯特拉)算法。