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

引入具体案例分析：

1.先来个有向图(有方向)

已知图像如下，以顶点A为起始点，求到其余顶点之间的最短路径。

//首先，先定义表示上图的邻接矩阵
let graph = [
    [0, 2, 4, 0, 0, 0],
    [0, 0, 2, 4, 2, 0],
    [0, 0, 0, 0, 3, 0],
    [0, 0, 0, 0, 0, 2],
    [0, 0, 0, 3, 0, 2],
    [0, 0, 0, 0, 0, 0]
];

//然后，把所有的距离初始化为无限大
//let inf = Number.POSITIVE_INFINITY;
let inf = Infinity;

//从尚未处理的顶点中选出距离最近的顶点
function minDistance(dist, visit) {
    let min = inf
    let minIndex = -1
    for(let i =0; i < dist.length; i++) {
        if(!visit[i] && dist[i] < min) {
            minIndex = i
            min = dist[i]
        }
    }
    return minIndex
};

//算法函数
function dijkstra(start) {
　　//设置变量dist存储从起始节点到其他节点的最短路径距离
    let dist = []
　　//将存储访问过的顶点数组visit[]初始化为false
    let visit = []
    let length = graph.length
    for (let i = 0; i < length; i++) {
        dist[i] = inf
        visit[i] = false
    }
　　//把源顶点到自己的距离设为0
    dist[start] = 0
　　//找出到其余顶点的最短距离（只需要算length -1次，最后一个点前面的已经被标记为已访问）
    for (let j = 0; j < length - 1; j++) {
　　　　//从尚未处理的顶点中选出距离最近的顶点
        let u = minDistance(dist, visit)
　　　　　//把选出的顶点标为visited，以避免重复计算
        visit[u] = true
        for (let v = 0; v < length; v++) {
            if (
　　　　　　　　 //已经被处理过的点，已经得到了最短的距离，无需再次计算
                !visit[v] &&
　　　　　　　　 //这种情况出现于dijkstra(1)这种情况，源点（start）存在无法到达某一个点A，当然这里不会走到这一步，因为只循环了length-1次，如果存在两个无法到达的点，那么再处理最后一次时，便会出现这种情况
                dist[u] != inf &&
　　　　　　　　 //当前处理的u点和v点不相邻
                graph[u][v] != 0 &&
　　　　　　　   //如果找到更短的路径，则更新最短路径的值
                dist[u] + graph[u][v] < dist[v]
            ) {
                dist[v] = dist[u] + graph[u][v]
            }
        }
    }
　　//处理完所有顶点后，返回源顶点（start）到图中其他顶点最短路径的结果
    return dist
};
//测试
const res = dijkstra(0)
console.log(`A点到各个点最短路径：${res}`);　　　　/* 结果： A点到各个点最短路径：0,2,4,6,4,6*/
// [0, 2, 4, 6, 4, 6]
// 求B点到其他个点的最短距离
// const res = dijkstra(1); 
// console.log(`B点到各个点最短路径：${res}`);　　　　/* 结果： */
// Infinity表示点B与点A不相邻，从上图可知A与B相邻，而B与A不相邻
// [Infinity, 0, 2, 4, 2, 4]

2.再来个无向图

已知图像如下，以北京为起始点，求到其他城市的最短距离。

//同样的代码，不过邻接矩阵换成以下矩阵
let graph = [
　　[0, 100, 1200, Infinity, Infinity, Infinity],
　　[100, 0, 900, 300 , Infinity , Infinity],
　　[1200, 900, 0, 400, 500 , Infinity, Infinity],
　　[Infinity, 300, 400, 0, 1300, 1400],
　　[Infinity, Infinity, 500, 1300, 1500],
　　[Infinity, Infinity, Infinity, 1400, 1500]
];

//测试
const res = dijkstra(0)
console.log(`北京到各个城市的最短路径：${res}`);　　　　/* 结果：北京到各个城市的最短路径：0,100,800,400,1300,1800 */
//const res = dijkstra(1);
//console.log(`天津到各个城市的最短路径：${res}`);　　　　/* 结果：天津到各个城市的最短路径：100,0,700,300,1200,1700 */

　　ps:贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
　　
　　

标签：无

你的评论