【JS】根据老师讲解Dijkstra算法的模拟过程思路,自己实现了Dijkstra算法。
来源:12-3 实现 Dijkstra 算法
Potter520
2023-05-17
function dijkstra(graph) {
let curv = 0;
let dis = Array(graph.V()).fill(Number.MAX_SAFE_INTEGER);
let visited = Array(graph.V()).fill(false);
//! 需遍历的顶点数
let count = graph.V();
//! 1.确定一个点
dis[curv] = 0;
visited[curv] = true;
--count;
while (count > 0) {
//! 距离curv最邻近的顶点
let minw = -1;
//! 距离curv最邻近的顶点距离
let minDis = Number.MAX_SAFE_INTEGER;
//! 2.根据确定点,更新相邻点的距离
for (const w of graph.adj(curv)) {
if (visited[w]) {
continue;
}
dis[w] = Math.min(dis[w], dis[curv] + graph.getWeight(curv, w));
if (dis[w] < minDis) {
minw = w;
minDis = dis[w];
}
}
//! 3.遍历结束后,设置其中的最短边,作为下一个确定点
if (minw != -1) {
//! 4.再次执行1过程,直到所有顶点都遍历完成
curv = minw;
visited[curv] = true;
--count;
} else {
console.log("已找不到最邻近距离点:", `curv:${curv},minw:${minw}`);
break;
}
}
for (let i = 0; i < graph.V(); i++) {
console.log(`0-${i}:`, dis[i]);
}
return dis;
}
let res = dijkstra(new WeightedGraph(resolve(__dirname, "g.txt")));
console.log(res);
输出结果:
0-0: 0
0-1: 3
0-2: 2
0-3: 5
0-4: 6
[ 0, 3, 2, 5, 6 ]
测试这个图没有问题,请问老师我这实现有问题吗?
由于自己回答自己的问题,系统提示老师和同学看不到,所以把答案贴到下面
此时:curv=4,没有邻边遍历,退出条件。导致3和5都未遍历,所以还是得在前面加一段逻辑,从剩余的点遍历找最短距离的点,再走下面的逻辑。
写回答
1回答
-
感谢分享。
力扣中有大量 dijkstra 相关的问题,比如这个问题:https://leetcode.com/problems/network-delay-time/ 可以用类似这样的问题测试自己的算法。
继续加油!:)
00
相似问题