第二百二四章 加权有向图（下） (第1/1页)

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

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

    东，南，西，北，东北，东南，西南，西北。

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

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

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

    然后，再求总权重最小，或者说总海拔差最小（最节省体力）的路径。

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

    Dijkstra（迪杰斯特拉）算法。