我的Dijkstra的算法实现未返回最短路径 [英] My Dijkstra's algorithm implementation does not return shortest path
问题描述
我试图在JavaScript中实现Dijkstra的最短路径算法，并通过多个示例对其进行了测试.
I tried to implement the Dijkstra's shortest path algorithm in JavaScript, and tested it with multiple examples.
我正在使用此图查看其行为:
I am using this graph to see how it would behave:
如果我想找到从A到I的最短路径，结果应该是[A，D，C，F，G，H，I]，距离等于10.
If I want to find the shortest path from A to I, the result should be [A, D, C, F, G, H, I] with distance equal to 10.
但是我的实现将路径返回为[A，B，E，J，F，G，H，I]，距离为14.
But my implementation returns the path as [A, B, E, J, F, G, H, I] with distance of 14.
这是我的JavaScript代码:
Here is my JavaScript code:
const graph = {
A: {B: 3, C: 4, D: 2},
B: {A: 3, D: 6, E: 1},
C: {A: 4, D: 1, F: 3},
D: {A: 2, B: 6, C: 1, E: 5},
E: {B: 1, D: 5, J: 1},
F: {C: 3, G: 2, J: 5},
G: {F: 2, H: 1, I: 3},
H: {G: 1, I: 1, X: 2},
I: {G: 3, H: 1, X: 8},
J: {E: 1, F: 5, X: 6},
X: {H: 2, I: 8, J: 6},
};
// The class Dsp:
class Dsp {
constructor() {
//Previous node after update of distance
this.prev = {};
//Distances of each node
this.distances = {};
//Array of unvisited neighbors
this.unvisitedn = [];
//Path of visited nodes from first to final node
this.path = [];
}
findsp(graph, start, end) {
//Register graph data
this.registerGraphData(graph, start);
//Set the starting node as the current node
let cn = start;
//While there are unvisited nodes
while (this.unvisitedn.length > 0) {
//Mark the currentNode as visited
this.markAsVisited(cn);
//Compare distance from current node to unvisited neighbors
let nodes = this.compareNodeDistances(graph, cn);
//Update neighbor distance
this.updateNodeDistances(nodes, cn);
//Compare each unvisited neighbor and choose the one with the lowest distances
//Set the choosed node as the new current node
cn = this.selectNextNode(graph, cn);
}
return this.generatePath(start, end);
}
registerGraphData(graph, start) {
//Set starting weight for all nodes
const higherWeight = 10000;
//For each node in the graph
for (let node in graph) {
//If the node is the starting node
if (node == start)
//Set starting weight as 0
this.distances[node] = 0;
//else set the higherWeight
else
this.distances[node] = higherWeight;
//Add to the unvisited nodes
this.unvisitedn.push(node);
}
console.log(this.distances);
console.log(this.unvisitedn);
}
markAsVisited(cn) {
console.log('Visiting', cn);
let index = this.unvisitedn.indexOf(cn);
this.unvisitedn.splice(index, 1);
}
getUnvisitedNeighbors(graph, cn) {
//All current node neighbors
let nbs = graph[cn];
let unbs = [];
for (let nb in nbs) {
if (this.unvisitedn.includes(nb))
unbs.push(nb);
}
console.log(cn, 'Unvisited neighbors:', unbs);
return unbs;
}
compareNodeDistances(graph, cn) {
let unbs = this.getUnvisitedNeighbors(graph, cn);
//new distances
let newDistances = {};
//For all currentNode neighbors
for (let nb of unbs) { //Substituted unbs
//Neighbor Weight
let nbw = graph[cn][nb];
//console.log('Neighbor weight', nbw);
//neighbor distance
let nbd = this.distances[nb];
//console.log('Neighbor distance', nbd);
//current node distance
let cnd = this.distances[cn];
//console.log('Current node distance', cnd);
//If the neighbor distance > current node distance + neighbor weight
if (nbd > cnd + nbw)
newDistances[nb] = cnd + nbw;
}
console.log('new distances:', newDistances);
return newDistances;
}
updateNodeDistances(nodes, cn) {
//Update distances for each neighbor that was compared
for (let node in nodes) {
console.log(nodes);
this.distances[node] = nodes[node];
this.prev[node] = cn;
}
console.log("Node distances after update", this.distances);
console.log("Node previous nodes after update", this.prev);
}
selectNextNode(graph, cn) {
let unbs = this.getUnvisitedNeighbors(graph, cn);
let mind = 100000;
let nextn = null;
//If there are unvisited neighbors
if (unbs.length > 0) {
for (let nb of unbs) {
if (this.distances[nb] < mind) {
mind = this.distances[nb];
nextn = nb;
}
}
} else {
nextn = this.unvisitedn[0];
}
return nextn;
}
generatePath(start, end) {
let cn = end;
let path = {};
let nodes = [];
while (cn !== start) {
nodes.push(cn);
cn = this.prev[cn];
}
nodes.push(start);
nodes.reverse();
path['nodes'] = nodes;
path['distance'] = this.distances[end];
return path;
}
}
let shp = new Dsp();
console.log(shp.findsp(graph, 'A', 'I'));我想了解我编写的步骤有什么问题.
I would like to understand what´s wrong with the steps I programmed.
我做错了什么?还有其他步骤或考虑吗?
What am I doing wrong? Is there some additional step, or consideration?
推荐答案
问题是您没有执行最佳优先搜索.您的代码实际上执行了深度优先搜索，您只需在其中优化从 current 节点中选择的哪个未访问的 neighbor 即可.但是，您应该从所有未访问的节点中获取距离最小的节点，而不仅要从当前节点的相邻节点中获取.
The problem is that you are not performing a best-first search. Your code really performs a depth-first search, where you just optimise which unvisited neighbor you will choose from the current node. But you should take the node with the minimum distance from among all unvisited nodes, not just among the neighbors of the current node.
另请参见 Wikipedia 上算法说明的第6步:
See also step 6 of the algorithm description on Wikipedia:
- 否则，选择标记有最小尝试距离的未访问节点，将其设置为新的当前节点"
- Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node"
所以问题出在 selectNextNode 中.可以对此进行更正:
So the problem is in selectNextNode. It could be corrected to this:
selectNextNode(graph, cn) {
let mindist = Infinity;
let best;
for (let node of this.unvisitedn) {
if (this.distances[node] < mindist) {
mindist = this.distances[node];
best = node;
}
}
return best;
}
但是，这是一个幼稚的实现，因为在每一轮中您都必须再次找到最小值:这使得算法不是最优的.真正的Dijkstra算法将使用优先级队列(例如堆)，从而使查找效率更高.
However, this is a naive implementation, as in each round you have to find the minimum again: this makes the algorithm non-optimal. A true Dijkstra algorithm will use a priority queue, such as a heap, which makes this lookup more efficient.
不幸的是，JavaScript还没有提供本机堆实现，因此我们必须自己抛出或引用一个库.我从对在Javascript中实现Priority Queue的有效方式的答案中获取了实现.有关该实现的更多详细信息，请参见此处.
Unfortunately JavaScript does not (yet) provide a native heap implementation, so we have to throw our own or reference a library. I took the implementation from my answer to Efficient way to implement Priority Queue in Javascript?. See there for more details on that implementation.
我认为最短路径算法的实现不保证使用类.像您的 findsp 这样的功能就足够了.
I think the implementation of the shortest path algorithm does not warrant the use of a class. A function like your findsp should be enough.
所以这里是:
/* MinHeap minimised - taken from https://stackoverflow.com/a/66511107/5459839 */
const MinHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]>h[j+1][0])j++;if(j>=h.length||k<=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k<h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};
function DijkstraShortestPath(graph, start, end) {
// Heap with one entry: distance is 0 at start, and there is no previous.
let heap = [[0, start, null]];
let prev = {};
while (heap.length) {
let [distance, current, cameFrom] = MinHeap.pop(heap);
if (current in prev) continue; // Already visited
prev[current] = cameFrom; // Mark as visited
if (current == end) { // Found!
// Reconstruct path
let path = [];
while (current) {
path.push(current);
current = prev[current];
}
path.reverse();
return { path, distance };
}
// Push unvisited neighbors on the heap
for (let [neighbor, edge] of Object.entries(graph[current])) {
if (!(neighbor in prev)) MinHeap.push(heap, [distance + edge, neighbor, current]);
}
}
}
// Demo:
const graph = {
A: {B: 3, C: 4, D: 2},
B: {A: 3, D: 6, E: 1},
C: {A: 4, D: 1, F: 3},
D: {A: 2, B: 6, C: 1, E: 5},
E: {B: 1, D: 5, J: 1},
F: {C: 3, G: 2, J: 5},
G: {F: 2, H: 1, I: 3},
H: {G: 1, I: 1, X: 2},
I: {G: 3, H: 1, X: 8},
J: {E: 1, F: 5, X: 6},
X: {H: 2, I: 8, J: 6},
}
console.log(DijkstraShortestPath(graph, 'A', 'I'));这篇关于我的Dijkstra的算法实现未返回最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
