使用 Javascript 的 Dijkstra 算法

该算法用于计算城市之间的最小最短距离。

连同所附文章，如果您想了解更多信息，我添加了另一个增强功能。

Mubert

Mubert -一个使用人工智能算法和机器学习生成连续音乐流的平台

下载

1. 我计算了之前的路径，从那里我们可以得到它到达那里的完整路径。

const dijkstra = (graph) => {
    const vertex = graph.length;
    const path = new Array(vertex).fill(false);
    const distance = new Array(vertex).fill(Infinity);
    const prev = [-1];
    distance[0] = 0; // source Node

    const getMinDistanceIndex = (path, distance) => {
        let min = Infinity;
        let minIndex = -1;

        for (let j = 0; j< vertex; j++) {
            if (path[j] == false && min > distance[j]) {
                min = distance[j];
                minIndex = j;
            }    
        }    

        return minIndex;
    }

    for (let i = 0; i < vertex; i++) {
        const minDistanceIndex = getMinDistanceIndex(path, distance);
        path[minDistanceIndex] = true;

        for (let j = 0; j< vertex; j++) {
            if (path[j] == false && graph[minDistanceIndex][j] > 0 && distance[minDistanceIndex] + graph[minDistanceIndex][j] < distance[j]) {
                distance[j] = distance[minDistanceIndex] + graph[minDistanceIndex][j];
                prev[j] = minDistanceIndex;
            }
        }
    }

    console.log(path, distance, prev);
}

const graph = [ [ 0, 4, 0, 0, 0, 0, 0, 8, 0 ],
              [ 4, 0, 8, 0, 0, 0, 0, 11, 0 ],
              [ 0, 8, 0, 7, 0, 4, 0, 0, 2 ],
              [ 0, 0, 7, 0, 9, 14, 0, 0, 0],
              [ 0, 0, 0, 9, 0, 10, 0, 0, 0 ],
              [ 0, 0, 4, 14, 10, 0, 2, 0, 0],
              [ 0, 0, 0, 0, 0, 2, 0, 1, 6 ],
              [ 8, 11, 0, 0, 0, 0, 1, 0, 7 ],
              [ 0, 0, 2, 0, 0, 0, 6, 7, 0 ]];

dijkstra(graph);
/*
[true, true, true, true, true, true, true, true, true]
[0, 4, 12, 19, 21, 11, 9,  8, 14]
[-1, 0, 1, 2, 5, 6, 7, 0, 2]
*/

如果您有任何疑问，请随时联系我

参考
https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/