欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

13.GIS中Dijkstra(迪杰斯特拉)算法如何实现?(JavaScript版本有向图)

程序员文章站 2022-06-07 15:05:51
...

❤❤❤❤❤烧脑的一句话:若从点S到点T有一条最短路径,则该路径上的任何点到S的距离都是最短的。啥?!?!?

题目要求:

13.GIS中Dijkstra(迪杰斯特拉)算法如何实现?(JavaScript版本有向图)

实现要点:邻接矩阵+贪心算法(分解找最优解)+回溯法

实现简单说明:从起点出发,找到其直接相连的结点距离,然后一步一步向远处延伸。

实现详细说明:先是初始化。然后从起点V1出发,找到其直接相连的结点距离,比如V1相连的是V2,V4,V5。写入dis对应下标数组。并更新他们parent结点为V1,且V1标记已访问True。再在未访问的中找最小的距离,是V2是10。然后将V2作为起点,找到其直接相连的结点距离,进行(V2的距离+V2到相邻节点的距离)和(上一步初始状态下dis的距离)比较,前者小则替换,并将其更新parent。依次,直到遍历完所有节点。(如果不清楚,看代码详细注释

实现代码:

let startParent = null;

// 矩阵 [V1,V2,V3,V4,V5] 分别对应 0,1 2 3 4 
let matrix =
    [
        [0, 10, Infinity, 30, 100],

        [Infinity, 0, 50, Infinity, Infinity],

        [Infinity, Infinity, 0, Infinity, 10],

        [Infinity, Infinity, 20, 0, 60],

        [Infinity, Infinity, Infinity, Infinity, 0]
    ]

/*
 * V1 出发点  
 * 
 */
function dijkstra(V1 = 0, to) {
    let i = 0, j = 0, k = 0;

    //初始化
    // 已经访问过的节点 
    let visited = matrix.map(() => false); //[false, false, false, false, false]
    // 前驱结点
    // let parent = [];
    let parent = matrix.map(() => -1);
    // 距离权重
    // let dis = [];
    let dis = matrix.map(() => Infinity);

    // 顶点数
    let vertexCount = matrix.length || 0;

    console.log('初始化后表格如下:');
    console.table({
        visited,
        dis,
        parent
    });

    // 第一次不需要松弛操作 :不需要松弛操作就是 dis直接赋值为matrix[V1];
    dis = matrix[V1]; //[0, 10, Infinity, 30, 100]
    for (i = 0; i < vertexCount; i++) {
        if (matrix[V1][i] !== Infinity) {
            parent[i] = V1;
        } else {
            parent[i] = -1;
        }
        // visited[i] = false;
        parent[V1] = startParent;
    }
    visited[V1] = true;

    console.log('第一次操作后表格如下:');
    console.table({
        visited,
        dis,
        parent
    });
    // console.log(parent);//["NIL", 0, -1, 0, 0]
    // console.log(visited);//[true, false, false, false, false]
    // console.log(dis);//[0, 10, Infinity, 30, 100]

    // 第二次开始进行松弛:需要根据最小的距离权重修改直接相邻点的距离权重
    for (i = 1; i < vertexCount; i++) {
        let temp = i, minValue = Infinity;
        // 搜索之前队列中权重最小的点
        for (j = 0; j < vertexCount; j++) {
            if (visited[j] === false && dis[j] < minValue) {
                minValue = dis[j];
                temp = j;
            }
        }
        visited[temp] = true;

        // 更新队列
        // console.log(temp);//第一次:1
        // console.log(minValue);//第一次:10
        for (k = 0; k < vertexCount; k++) {
            if (visited[k] === false && matrix[temp][k] < Infinity && minValue + matrix[temp][k] < dis[k]) {
                parent[k] = temp;
                dis[k] = minValue + matrix[temp][k];
            }
        }
    }
    console.log('从起点V1到各顶点的最短路径如下表格如下:');
    console.table({
        visited,
        dis,
        parent
    });

    //结果展示
    let v = to;//设置当前点
    let path=[];
    while (v !== V1) {
        path.push(v);
        v = parent[v];    //找回溯点
    }
    path.push(V1);
    let str = "";
    str=path.reverse().map(function(item,index){
        return 'V'+(item+1);
    }).join('=>');
    console.log('最短路径是'+str,',长度是'+dis[to]);
}
dijkstra(0,4);

 

实现结果展示:

13.GIS中Dijkstra(迪杰斯特拉)算法如何实现?(JavaScript版本有向图)

总结:实现有一定的局限性,可扩展性不高,其次邻接矩阵浪费空间,可以考虑邻接表。还有Dijkstra算法仅仅使用于权值为非负的图的单源最短路径。所以说实现最短路径的算法不只这一种,还有其他比如Bellman-Ford算法等。(其中红色注明的也就是可以优化的点,欢迎大家优化)。