13.GIS中Dijkstra(迪杰斯特拉)算法如何实现?(JavaScript版本有向图)
程序员文章站
2022-06-07 15:05:51
...
❤❤❤❤❤烧脑的一句话:若从点S到点T有一条最短路径,则该路径上的任何点到S的距离都是最短的。啥?!?!?
题目要求:
实现要点:邻接矩阵+贪心算法(分解找最优解)+回溯法
实现简单说明:从起点出发,找到其直接相连的结点距离,然后一步一步向远处延伸。
实现详细说明:先是初始化。然后从起点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);
实现结果展示:
总结:实现有一定的局限性,可扩展性不高,其次邻接矩阵浪费空间,可以考虑邻接表。还有Dijkstra算法仅仅使用于权值为非负的图的单源最短路径。所以说实现最短路径的算法不只这一种,还有其他比如Bellman-Ford算法等。(其中红色注明的也就是可以优化的点,欢迎大家优化)。
下一篇: 西瓜影音不能播放的原因和解决方法