不要构造显式图(指针很昂贵)-使用成对的坐标来表示队列中的节点,并修改Dijkstra实现以直接在2d数组表示中进行操作。
使用类似于costs数组的数组来存储算法计算出的(初始尝试)距离。
Dijkstra将在一次运行中计算所有节点的成本,因此,如果您的起点是固定的,则运行一次就足够了-无需运行数百万次。
PS:创建了一个在图像上运行Dijkstra的Jsfiddle:https://goo.gl/5GWwMF
计算鼠标单击到所有点的距离,其中较暗的像素被解释为更昂贵。
对于较大的图像,它变慢了,但到目前为止还没有使它崩溃,但是我认为对于您的数据,它将在浏览器中耗尽内存。
Dijkstra实现使用以下接口访问图形-我认为这应该很直接,以提供您的数据结构之上,而无需显式生成带有显式节点和内存边缘的“传统”图数据结构:
/**
* The interface the Dijkstra implementation below uses
* to access the graph and to store the calculated final
* and intermediate distance data.
*
* @Interface
*/
Graph = function() {};
/**
* Returns the current distance for the given node.
* @param {Object} node
* @return {number}
*/
Graph.currentDistance = function(node) {};
/**
* Stores the current distance for the given node.
* @param {Object} node
* @param {number} distance
*/
Graph.setCurrentDistance = function(node, distance) {};
/**
* Returns an array of connected nodes for the given node,
* including the distances.
*
* @param {Object}
* @return {Array<{cost:number, node:Object}>}
*/
Graph.connections = function(node) {};
PPS:添加了代码,以在第一次单击后显示所有单击的短路路径。还修复了允许对角线移动的错误:https://goo.gl/wXGwiv
因此,总而言之,尽管这在浏览器中可能无法缩放到50k x 50x,但我认为这表明直接在数组上进行操作的Dijkstra值得在服务器端尝试,并且大小与数据数组相同的数组值得从单个点存储所有最短路径所需的全部操作。