[原创]开荒最短路径计算方法-基于Dijkstra算法的maphack改进方向 [复制链接]

https://baike.baidu.com/item/%E8%BF%AA%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95/23665989?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

典型算法应用场景：

计算出鲁高因到遗失的城市之间最短路线，并在地图上进行指示。加快开荒速度，等等。

问题描述

编辑

在有向图 G=(V,E) 中，假设每条边 E 的长度为 w，找到由顶点 V0 到其余各点的最短值。 [1]

算法思想

编辑

按路径长度递增次序产生算法： [1]

把顶点集合V分成两组： [3]

（1）S：已求出的顶点的集合（初始时只含有源点V0） [1]

（2）V-S=T：尚未确定的顶点集合 [1]

将T中顶点按递增的次序加入到S中，保证： [1]

（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度 [1]

（2）每个顶点对应一个距离值 [2]

S中顶点：从V0到此顶点的长度 [1]

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度 [1]

依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 [1]  。

（反证法可证）

求最短路径步骤 [1]

算法步骤如下： [1]

G={V,E}

1. 初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值 [1]

若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值 [1]

若不存在<V0,Vi>，d(V0,Vi)为∞ [2]

2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中 [1]

3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值 [1]

重复上述步骤2、3，直到S [1]  中包含所有顶点，即W=Vi为止 [1]

heaven65:

高大上

有啥实际用处，最好说人话

开荒时小地图指示去往目标地点的最短路线啊。A2 A3路线难找吧？有时候走错了，有时候绕路了吧？提前算出来啊。小地图里画上啊。