嵇爾的吐槽

#没事画轮子的嵇尔不定期的(W)碎(E)碎(B)念(B)和(L)吐(O)槽(G)

赞服地铁通最短路径计算 2019-03-28 17:30:00

赞服地铁

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

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

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

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

这个不是我造的,是其他小伙伴的杰作!

地铁通

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

项目代码在这里

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

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

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

Dijkstra最短路径树

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

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

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

大概是这么回事

已知

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

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

文字描述

  1. 先记录一个表(函数,序列,随你怎么叫)D,到达所有的站点距离都设为无穷大。
  2. 到达出发点S的距离为0。
  3. 从出发点S开始,找到出发点S能直接到达的所有的点v,把距离记在表D上。
  4. 找到出发点S可以到达的最近的站点u。
  5. 然后从这个站点u出发,找到这个点u能直接到达的所有的点v,如果经过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

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的长度为 跳过

经过B到达E的长度为 填入Dist

经过B到达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的长度为 跳过

Q中距离A最近的是E

从E开始

Q = [F]

获取E能直接到达的路径

EF = 3

经过E到达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];
}
评论共