赞服地铁通最短路径计算

2019-03-28 17:30:00   技术   javascript MC

赞服地铁

赞服是我最近一段时间在玩的Minecraft的一个服务器。这个服务器的一大特色就是从来不换周目，于是就造就了很多虽然说不上壮观但是很有意思的……工程。其中一个工程就是地铁系统。虽然没有一些视频里面那种很壮观漂亮的地铁站，但是……

截止到目前为止，赞服地铁一共有39条线路，共计135个地铁站:trollface:。

说数字可能还没什么概念，于是上个图吧。

不用点击，这是缩略图，不会放大

这个不是我造的，是其他小伙伴的杰作！

地铁通

我个人有个“玩什么游戏都想弄弄黑科技”的习性。于是为了解决“我想去某个地方但是面对四通八达的地铁不知道怎么坐才能到”这个问题，就和小伙伴合作做了一个赞服地铁通。

项目代码在这里。

举个例子，目前服务器距离最远的2个站，线路如下：

不用点击，这个还是缩略图，不会放大

在游戏里做矿车需要半个多小时，手动再见！

Dijkstra最短路径树

做个小东西里面用到了不少我以前没有玩过的东西，不过从算法上来说没什么特别的。

算最短距离用了Dijkstra算法。其实我很早（刚大学毕业）就想研究研究，当时把上海地铁的数据都拖下来了，就是没动键盘……结果就是现在研究觉得自己的脑子不太好使了。

具体算法定义可以去搜各种维基百科/百度等等。

大概是这么回事

已知

  • 有权重的有向图G (记录了所有站点，站点之间是否有通路，站点之间的距离)
  • 来源S(出发点)

求

  • 从S出发到所有其他点的最短路径

文字描述

  1. 先记录一个表（函数，序列，随你怎么叫）D，到达所有的站点距离都设为无穷大。 \(D(v) = +∞\)
  2. 到达出发点S的距离为0。 \(D(S) = 0\)
  3. 从出发点S开始，找到出发点S能直接到达的所有的点v，把距离记在表D上。 \(D(v) = E(S,v)\)
  4. 找到出发点S可以到达的最近的站点u。
  5. 然后从这个站点u出发，找到这个点u能直接到达的所有的点v，如果经过u到v的距离比表上原来记录的距离短，就把距离记在表上。 这个过程有的文档上叫做“拓展”，也有叫“拉直”，“捋直”。 \(D(v) = D(u) + E(u,v)\)
  6. 找到距离出发点S最近的站点另一个u，重复5，一直做到没点可找。

实例（以下都是人工循环，可以直接跳过）

站点实例

简单起见，弄了单向。

已知

有向图G = {
    所有站点V = [A, B, C, D, E, F]
    路径和距离E = {
        AB = 6
        AD = 3
        AC = 11
        DC = 4
        BC = 2
        BE = 5
        BF = 7
        CF = 8
        EF = 3
    }
}
起始点S = A

初始化

Q = [A,B,C,D,E,F]
Dist = {
    A = 0
    B = +∞
    C = +∞
    D = +∞
    E = +∞
    F = +∞
}

从A开始

Q = [B,C,D,E,F]

获取A能直接到达的路径

AB = 6
AD = 3
AC = 11

填入Dist

Dist = {
    A = 0
    B = 6
    C = 11
    D = 3
    E = +∞
    F = +∞
}

Q中距离A最近的是D

从D开始

Q = [B,C,E,F]

获取D能直接到达的路径

DC = 4

经过D到达C的长度为 \(Dist(D) + E(D, C) = 7 < Dist(C)\) 填入Dist

Dist = {
    A = 0
    B = 6
    C = 7
    D = 3
    E = +∞
    F = +∞
}

Q中距离A最近的是B

从B开始

Q = [C,E,F]

获取B能直接到达的路径

BC = 2
BE = 5
BF = 7

经过B到达C的长度为 \(Dist(B) + E(B, C) = 8 > Dist(C)\) 跳过

经过B到达E的长度为 \(Dist(B) + E(B, C) = 11 < Dist(E)\) 填入Dist

经过B到达F的长度为 \(Dist(B) + E(B, F) = 13 < Dist(F)\) 填入Dist

Dist = {
    A = 0
    B = 6
    C = 7
    D = 3
    E = 11
    F = 13
}

Q中距离A最近的是C

从C开始

Q = [E,F]

获取C能直接到达的路径

CF = 8

经过C到达F的长度为 \(Dist(C) + E(C, F) = 15 > Dist(F)\) 跳过

Q中距离A最近的是E

从E开始

Q = [F]

获取E能直接到达的路径

EF = 3

经过E到达F的长度为 \(Dist(E) + E(E, F) = 14 > Dist(F)\) 跳过

Q中距离A最近的是F

从F开始

Q = []

获取F能直接到达的路径(没有，跳过)

Q中无点

结果就是

Dist = {
    A = 0
    B = 6
    C = 7
    D = 3
    E = 11
    F = 13
}

前驱站点

直接输出的Dist，只能看到路径长度，如果需要输出路径，就需要记录一下前驱站点。当然自己写个表硬记下来也是可以的。

代码

代码到处都有，地铁通里面使用的是这样的：

输入一个stations的array和edges的array，这两个就充当G的角色了

function Dijkstra(stations, edges, s) {
    var Extract_Min = function(q, d) {
        var minNode = undefined;
        for (var i = 0; i < q.length; i++) {
            var node = q[i];
            if (minNode == undefined) {
                minNode = node;
            } else if (d[node] < d[minNode]) {
                minNode = node;
            }
        }
        return minNode;
    }
    var d = {};
    var prev = {};
    var Q = [];
    for (var i = 0; i < stations.length; i++) {
        var v = stations[i];
        d[v.name] = Number.MAX_VALUE;
        prev[v.name] = Number.MAX_VALUE;
        Q.push(v.name);
    }
    d[s] = 0;
    var S = [];
    while (Q.length > 0) {
        var u = Extract_Min(Q, d)
        Q.splice(Q.indexOf(u), 1);
        S.push(u);
        for (var i = 0; i < edges.length; i++) {
            var edge = edges[i];
            if (edge.start.name == u) {
                var v = edge.end.name;
                if (d[v] > d[u] + edge.distance) {
                    d[v] = d[u] + edge.distance;
                    prev[v] = u;
                }
            }
        }
    }
    return [d, prev];
}
评论共条