迪杰特斯拉算法求最短路径

悠悠 2022-06-04 09:46 226阅读 0赞

### 前言： ###

通过JavaScript实现该算法，并求出初始点到各个点的最短路径

<!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <title>迪杰特斯拉算法</title>
    </head>
    <body>
        <script> //说明 //@xiaoD //计算第一个节点开始到各个节点的最短路径 //邻接矩阵 var data = [ [0, 4, 6, -1, -1, -1, -1, -1], [4, 0, -1, 5, 4, -1, -1, -1], [6, -1, 0, 4, 7, -1, -1, -1], [-1, 5, 4, 0, -1, 9, 7, -1], [-1, 4, 7, -1, 0, 5, 6, -1], [-1, -1, -1, 9, 5, 0, 5, 4], [-1, -1, -1, 7, 6, 5, 0, 1], [-1, -1, -1, -1, -1, 4, 1, 0] ]; //对邻接矩阵进行规范化 for(var i=0; i<data.length; i++) { for(var j=0; j<data.length; j++) { if(data[i][j] === -1) { data[i][j] = Infinity; } } } //对节点进行字母描述 var nodeName = [] //最短路径数组 var minPath = []; //该节点是否已经找到最短路径 var findMin = []; //(找到最短路径节点)的临近节点 var nearNode; //上一个节点 var preNode = []; //初始化数据 for(var i=0; i<data.length; i++) { minPath[i] = data[0][i]; findMin[i] = false; preNode[i] = i; nodeName[i] = String.fromCharCode(65+i) } findMin[0] = true; for(var i=1; i<data.length; i++) { //找出距离(找到最短路径节点)的节点和距离 var min = Infinity; for(var j=0; j<data.length; j++) { if(!findMin[j] && minPath[j] < min) { min = minPath[j]; nearNode = j; } } //临近节点也找到最短路径 findMin[nearNode] = true; for(var k=0; k<data.length; k++) { if(!findMin[k] && minPath[k] > (min + data[nearNode][k])) { minPath[k] = min + data[nearNode][k]; preNode[k] = nearNode; } } } var pre; var list; var result; for(var i=0; i<minPath.length; i++) { console.log(nodeName[0] + " ----> " + nodeName[i] + " 的最小距离是 " + minPath[i]); if(i === preNode[i]) { console.log(nodeName[0] + " ----> " + nodeName[preNode[i]] + "\n\n"); }else{ pre = i; list = []; while(pre !== preNode[pre]) { list.push(nodeName[pre]); pre = preNode[pre]; } list.push(nodeName[preNode[pre]], nodeName[0]); result = ""; for(var t=list.length-1; t > 0; t--) { result = result + list[t] +" ----> "; } result += list[0]; console.log(result + "\n\n"); } } </script>
    </body>
    </html>