初尝最短路算法之 Dijkstra

最近碰到一个面试题，然后感觉是最短路问题，于是花了一天时间学习，虽然算法还是没看懂，还是记录一下：

//求解 index 号顶点到达其他顶点的最短距离
function dijkstra(path, index) {
    let m = path && path.length;
    let n = m && path[0].length;

    if (m && n && m === n && index < n) {
        //初始化 distance
        let dis = JSON.parse(JSON.stringify(path[index]));

        let flag = [];//用于标识 index 号至其他顶点的距离是否确定
        for (let i = 0; i < n; i++) {
            flag.push(false)
        }
        flag[index] = true;

        let min, minIndex;
        dis[index].way = [dis[index].shop, dis[index].shop]
        for (let i = 0; i < n; i++) {
            min = Infinity;
            //找出剩余的不确定的点到 index 最短的距离对应的索引
            for (let j = 0; j < n; j++) {
                if (!flag[j] && dis[j].weight < min) {
                    min = dis[j].weight;
                    minIndex = j;
                }
            }
            flag[minIndex] = true;//标识 index 到此顶点的距离已经确认
            if (dis[minIndex].way == undefined) dis[minIndex].way = [dis[index].shop, dis[minIndex].shop]
            for (let k = 0; k < n; k++) {
                if (dis[k].way == undefined) dis[k].way = dis[k].way = [dis[index].shop, dis[k].shop]
                //判断 minIndex 到 k 之间有无道路
                if (path[minIndex][k].weight < Infinity) {
                    //更新 distance
                    if (dis[k].weight > dis[minIndex].weight + path[minIndex][k].weight) {
                        dis[k].weight = dis[minIndex].weight + path[minIndex][k].weight;
                        dis[k].way = [...dis[minIndex].way, path[minIndex][k].shop]
                    }
                }
            }
        }
        return dis;
    }
    else {
        throw new Error("数据有误")
    }
}

let path = [
    [0, 1, 9, 7, 1],
    [1, 0, 3, 6, 8],
    [9, 3, 0, 2, 5],
    [7, 6, 2, 0, 2],
    [1, 8, 5, 2, 0]
]

console.log("source", path)
const PATHS = []
const Arr = ["A", "B", "C", "D", "E"]
for (let index = 0; index < path.length; index++) {
    PATHS[index] = path[index].map((value, index) => { return { weight: value, shop: Arr[index] } })
}

let res = []
let log = ''
for (let index = 0; index < PATHS.length; index++) {
    let result = dijkstra(PATHS, index)
    res[index] = result.map(value => value.weight)
    log += `start shop: ${result[index].shop}\n`
    result.forEach(value => log += `end: ${value.shop} weight: ${value.weight} path: ${value.way.toString().replace(/,/g, "-->")}\n`)
}
console.log('result', res)
console.log(log)

经历了一次面试，发现自己还是有很多的不足，算法和数据结构真要捞一下了。可能以后写更多有关算法和数据结构的博客。

参考

最短路径算法——Dijkstra 算法的 JS 实现