Самая быстрая реализация алгоритма Дейкстры на javascript?

Question

[Magneto903]

Дан взвешенный граф. Необходимо решить 2 задачи: найти из начальной точки длины путей до всех точек и также получить самый короткий (дешевый, оптимальный и т.п.) путь их одной точки в другую.

Логично напрашивается алгоритм Дейкстры.

НО!

Нужно, чтобы реализация работала быстро.
Для оценки: для 160 вершин и 350 рёбер выполнение за 3 миллисекунды - это медленно.

Я пытался найти реализации этого алгоритма на JavaScript в интернете. Однако либо они были слишком медленные
как например эта
или эта

Либо некорректно работали, т.е. зацикливались, хотя входные данные были корректны
как здесь

Также прикрепляю сюда пример со ~160 вершинами и ~350 ребрами, чтобы не надо было самому придумывать такой пример, чтобы измерить время

Ссылка на пример такого графа

Если можно как-то оптимизировать те реализации, ссылки на которые я прикрепил выше, и от этих оптимизаций они станут быстро работать, буду тоже очень признателен!

Comments

[Алексей Уколов]

Можно попробовать перевести на wasm.

[Magneto903]

Алексей Уколов, как сильно это ускорит? Во сколько примерно раз?

[Kovalsky]

Magneto903, бэнч покажет

Answer 1

[Wataru]

Попробуйте переписать с массивами фиксированной длины. Во всех реализациях по вашим ссылкам вершины нумеруются строками и куча массивов типа distance и visited на самом деле являются словарями, или как это в js называется. Это работает сильно медленнее тупого массива, пронумерованного от 0 до n.

Вам понадобится один словарь для перенумерации вершин в числа. Потом преобразуйте гарф на массив массивов, вместо этого сложного объекта.

И уже на нем гоняйте дейкстру. Должно по карйней мере в пару раз ускорится. А то и во все 10.

Comments

[Magneto903]

представлять граф в виде матрицы смежности?

[Magneto903]

Заменил visited и distance на объекты Map. Теперь одна итерация проходит за 0.3-1 ms.
Может быть можно быстрее

как именно заменил

var shortestDistanceNode = (distances, visited) => {
  // create a default value for shortest
    var shortest = null;
    
    // for each node in the distances object
    for (var node of distances.keys()) {
        // if no node has been assigned to shortest yet
        // or if the current node's distance is smaller than the current shortest
        var currentIsShortest = shortest == null || distances.get(node) < distances.get(shortest);
            
        // and if the current node is in the unvisited set
        if (currentIsShortest && visited[node] != true) {
        	//visited[node] == false
            // update shortest to be the current node
            shortest = node;
        }
    }
    return shortest;
};




var get_distances_from = function(graph, startNode) {

   	var distances = new Map();
   	
 	var parents = new Map();

 	for (var child of graph[startNode].keys()) {
 		distances.set(child, graph[startNode].get(child))
 		//console.log(child)
 		//console.log(child)
  		parents.set(child, startNode);
 	}	


 	// collect visited nodes
   	var visited = {};
   	visited[startNode] = true;

	// find the nearest node
   	var node = shortestDistanceNode(distances, visited);

	// for that node:
 	while (node) {
 		// find its distance from the start node & its child nodes
  		var distance = distances.get(node);
  		var children = graph[node]; 
 		// for each of those child nodes:
    	for (var child of children.entries()) {
 
        	// save the distance from the start node to the child node
        	var newdistance = distance + child[1];
			// if there's no recorded distance from the start node to the child node in the distances object
			// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
        	if (!distances.get(child[0]) || distances.get(child[0]) > newdistance) {
				// save the distance to the object
     			distances.set(child[0], newdistance);	
				// record the path
     			parents.set(child[0],node);
    		} 
        }
         
      	// move the current node to the visited set
      	visited[node] = true;
		// move to the nearest neighbor node
      	node = shortestDistanceNode(distances, visited);
    }
   	return distances;
};

структура graph

[Magneto903]

Илья Николаевский, почему-то функция, которая ещё и восстанавливает путь замыкается

var findShortestPath = (graph, startNode, endNode) => {
 	var distances = new Map();
   	
 	var parents = new Map();

 	distances.set(endNode, Infinity)
 	parents.set(endNode, null)

 	for (var child of graph[startNode].keys()) {
 		distances.set(child, graph[startNode].get(child))
 		//console.log(child)
 		//console.log(child)
  		parents.set(child, startNode);
 	}	


 	// collect visited nodes
   	var visited = {};
   	visited[startNode] = true;

	// find the nearest node
   	var node = shortestDistanceNode(distances, visited);

	// for that node:
 	while (node) {
 		// find its distance from the start node & its child nodes
  		var distance = distances.get(node);
  		var children = graph[node]; 
 		// for each of those child nodes:
    	for (var child of children.entries()) {
 
        	// save the distance from the start node to the child node
        	var newdistance = distance + child[1];
			// if there's no recorded distance from the start node to the child node in the distances object
			// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
        	if (!distances.get(child[0]) || distances.get(child[0]) > newdistance) {
				// save the distance to the object
     			distances.set(child[0], newdistance);	
				// record the path
     			parents.set(child[0],node);
    		} 
        }
         
      	// move the current node to the visited set
      	visited[node] = true;
		// move to the nearest neighbor node
      	node = shortestDistanceNode(distances, visited);
    }
	
  
 	// using the stored paths from start node to end node
 	// record the shortest path
 	var shortestPath = [endNode];
 	var parent = parents.get(endNode);
 	while (parent) {
  		shortestPath.push(parent);
  		parent = parents.get(parent);
 	}
 	shortestPath.reverse();
  
 	//this is the shortest path
 	var results = {
  		distance: distances.get(endNode),
  		path: shortestPath,
  		//all_distances: distances
 	};
 	// return the shortest path & the end node's distance from the start node
   	return results;
};

[Wataru]

Magneto903, Нет не надо матрицы смежности, оставьте списки инцидентности. Пусть у вас будет массив списков объектов {конец ребра, цена}. Раньше у вас там был словарь из строк-имен вершин. Но раз мы поменяли на числа, то можно это заменить массивом, который будет быстрее.

Вообще, по идее, если вместо Map использовать массивы ("[]"? Array?) должно еще быстрее быть.

Еще цикл в начале, который проходится по детям startNode - он лишний.

По поводу функции восстановления пути: надо distances[startNode] = 0 делать перед циклом по node. Иначе алгоритм находит путь в эту вершину через какую-то другую. Путь, который начинается в startNode же. В итоге получается цикл, в котором вы и висните.

[Wataru]

Magneto903, Еще варинат есть использовать heap - должно быть сильно быстрее.

Дейкстра работает за O(n^2+m) потому что вам надо n раз искать вершину с минимальным расстоянием ну и вы по каждому ребру ровно один раз посмотрите, улучшает ли оно расстояние до другого конца.

Если минимум искать через хип, то будет O((n+m)log n) операций, что сильно лучше для вашего случая (m < n^2), потому что хип умеет выдавать минимум и изменять значение за log n.

Вы же, кажетcя, ссылку давали на этот сборник алгоритмов.

Там есть heap. Вам надо хранить в хипе пары {расстояние, номер вершины} до всех пока не visited вершин, у которых есть расстояние. Изначально heap пустой совсем.

Вам надо переписать shortestDistanceNode просто брать минимум из minHeap. При изминении distances в цикле по node вам надо добавлять в minHeap новый объект {расстояние, номер вершины}. Именно в таком порядке, чтобы минимальный элемент содержал минимальное расстояние. Ну или функции сравнения переписать.

Но тут ньюанс - в хипе может быть куча копий вершины, ведь вы будете добавлять новую копию каждый раз, когда обновите расстояние. Поэтому еще надо цикл по child пропускать, если вершина из heap уже в visited.

Или вам придется этот minHeap немного переписать, чтобы проддерживать map из номеров вершин в их позиции в хипе. И при каждом изменении массива heapContainer обовлять этот map. Тогда в методе remove не надо будет выполнять линейный поиск через find.

Потом при изменении distance в основном цикле вы должны будете удалить вершину child[0] из хипа перед добовлением ее копии с новым расстоянием.

[Magneto903]

Илья Николаевский, Да, я попробую. Кстати насчёт массивов. Похоже в моём случае Map всё-таки быстрее работает, что конечно странно, но факт

[Magneto903]

Илья Николаевский, А брать именно MinHeap, не PriorityQueue?

[Wataru]

Magneto903, Я этот priority queue проглядел. Он как раз нужная вам надстройка над minHeap. Надо добавлять вершины с приоритетами-расстояниями.

[Magneto903]

Илья Николаевский, т.е. фактически shortestDistanceNode() можно заменить на PriorityQueue.poll()?

[Wataru]

Magneto903, ага. Только ее еще надо будет удалить из очереди.

[Magneto903]

Илья Николаевский, Ура!!! Я применил кучу и теперь проход 1 работает за время от 0.005 до 0.02 ms! Кстати удалять вершину даже не надо, PriorityQueue() распознаёт уже существующие вершины и обновляет их

[Wataru]

Magneto903, Алгоритмы - сила!

[Magneto903]

Илья Николаевский, Странно. Почему-то теперь алгоритм Дейкстры не всегда находит кратчайший путь, даже если он точно есть (по графу это хорошо видно). Можете посмотреть, может что-то не так в реализации самого Алгоритма Дейкстры?

реализация

var findShortestPath = (graph, startNode, endNode) => {
 	var distances = new Map();
 	var parents = new Map();
 	var queue = new PriorityQueue();

	queue.add(startNode, 0);
	distances.set(startNode, 0);
 	distances.set(endNode, Infinity)
 	parents.set(endNode, null)
 	 	
 	for (var child of graph[startNode].keys()) {
 		distances.set(child, graph[startNode].get(child))
 	}

 	// collect visited nodes
   	var visited = {};
   	visited[startNode] = true;

	// find the nearest node
   	var node = queue.poll();
   	
	// for that node:
 	while (node) {
 		// find its distance from the start node & its child nodes
  		var distance = distances.get(node);
  		var children = graph[node]; 
 		// for each of those child nodes:
    	for (var child of children.entries()) {
        	// save the distance from the start node to the child node
        	var newdistance = distance + child[1];
			// if there's no recorded distance from the start node to the child node in the distances object
			// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
        	if (!distances.get(child[0]) || distances.get(child[0]) > newdistance) {
				// save the distance to the object
     			distances.set(child[0], newdistance);	
				// record the path
     			parents.set(child[0], node);
     			if (queue.hasValue(child[0])) {
		        	queue.changePriority(child[0], newdistance);
		        }
    		} 
        }
      	// move the current node to the visited set
      	visited[node] = true;
		// move to the nearest neighbor node
      	node = queue.poll()
    }
	
  
 	// using the stored paths from start node to end node
 	// record the shortest path
 	var shortestPath = [endNode];
 	var parent = parents.get(endNode);
 	while (parent) {
  		shortestPath.push(parent);
  		parent = parents.get(parent);
 	}
 	shortestPath.reverse();
  
 	//this is the shortest path
 	var results = {
  		distance: distances.get(endNode),
  		path: shortestPath,
  		//all_distances: distances
 	};
 	// return the shortest path & the end node's distance from the start node
   	return results;
};

[Wataru]

Magneto903, Проверьте
1) queue.poll() удаляет первую вершину.
2) очередь возвращает вершину с МИНИМАЛЬНЫМ приоритетом.
3) Цикл for (var child of graph[startNode].keys()) не нужен.
4) Если child нет в очереди - то надо добавить вершину с приоритетом newdistance. Вы же только обновляете приоритет. если вершины нет.

[Magneto903]

Илья Николаевский, не совсем понял по поводу первых двух пунктов. 3-ий и 4-ий я сделал, и теперь всё сломалось) Переполнение памяти происходит

что именно я сделал

var findShortestPath = (graph, startNode, endNode) => {
 	var distances = new Map();
 	var parents = new Map();
 	var queue = new PriorityQueue();

	queue.add(startNode, 0);
	distances.set(startNode, 0);
 	distances.set(endNode, Infinity)
 	parents.set(endNode, null)
 	
 	/*	
 	for (var child of graph[startNode].keys()) {
 		distances.set(child, graph[startNode].get(child))
 	}
 	*/

 	// collect visited nodes
   	var visited = {};
   	visited[startNode] = true;

	// find the nearest node
   	var node = queue.poll();
   	
	// for that node:
 	while (node) {
 		// find its distance from the start node & its child nodes
  		var distance = distances.get(node);
  		var children = graph[node]; 
 		// for each of those child nodes:
    	for (var child of children.entries()) {
        	// save the distance from the start node to the child node
        	var newdistance = distance + child[1];
			// if there's no recorded distance from the start node to the child node in the distances object
			// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
        	if (!distances.get(child[0]) || distances.get(child[0]) > newdistance) {
				// save the distance to the object
     			distances.set(child[0], newdistance);	
				// record the path
     			parents.set(child[0], node);
     			if (queue.hasValue(child[0])) {
		        	queue.changePriority(child[0], newdistance);
		        } else {
		        	queue.add(child[0], newdistance);
		        }
    		} 
    		
        }
      	// move the current node to the visited set
      	visited[node] = true;
		// move to the nearest neighbor node
      	node = queue.poll()
    }
	
  
 	// using the stored paths from start node to end node
 	// record the shortest path
 	var shortestPath = [endNode];
 	var parent = parents.get(endNode);
 	while (parent) {
  		shortestPath.push(parent);
  		parent = parents.get(parent);
 	}
 	shortestPath.reverse();
  
 	//this is the shortest path
 	var results = {
  		distance: distances.get(endNode),
  		path: shortestPath,
  		//all_distances: distances
 	};
 	// return the shortest path & the end node's distance from the start node
   	return results;
};

[Wataru]

Magneto903, Что у вас за PriorityQueue реализация? Посмотрите код, потестируйте. Добавьте в очередь приоритеты a:1,b:3,c:5 и сделайте queue.poll() несколько раз.

Надо, что бы вернулись именно минимальные числа и они из очереди удалялись. Т.е. 3 poll() вернут a,b,c в таком порядке.

Если возвращается максимальный элемент, то вам надо пихать в очередь не newdistance, а -newdistance.

Если все три раза возвращается один и тот же элемент, то значит после poll() надо удалять элемент из очереди или спользовать какой-нибудь pop_front(), pop() метод у queue.

Код выглядит правильно.

[Magneto903]

Илья Николаевский, Странно. Вроде PriorityQueue работает корректно

var test_queue = new PriorityQueue();

test_queue.add('a', 1);
test_queue.add('c', 5);
test_queue.add('b', 3);

console.log(test_queue.poll()) // return a
console.log(test_queue.poll()) // return b
console.log(test_queue.poll()) // return c

[Wataru]

Magneto903, Попробуйте воткнуть changePriority в конце. поменяйте 5 на 2. Должно вернуть a, c, b.

Добавьте отладочный вывод в дейкстру или вообще пройдитесь отладчиком по падающему тесту. Я не помниаю, как оно может падать по памяти. Смотрите, сколько вершин в очереди.

Еще дайте ссылку на реализацию priorityQueue. Может там косяк.

[Magneto903]

PriorityQueue

// It is the same as min heap except that when comparing two elements
// we take into account its priority instead of the element's value.
class PriorityQueue extends MinHeap {
  constructor() {
    // Call MinHip constructor first.
    super();

    // Setup priorities map.
    this.priorities = new Map();

    // Use custom comparator for heap elements that will take element priority
    // instead of element value into account.
    this.compare = new Comparator(this.comparePriority.bind(this));
  }

  /**
   * Add item to the priority queue.
   * @param {*} item - item we're going to add to the queue.
   * @param {number} [priority] - items priority.
   * @return {PriorityQueue}
   */
  add(item, priority = 0) {
    this.priorities.set(item, priority);
    super.add(item);
    return this;
  }

  /**
   * Remove item from priority queue.
   * @param {*} item - item we're going to remove.
   * @param {Comparator} [customFindingComparator] - custom function for finding the item to remove
   * @return {PriorityQueue}
   */
  remove(item, customFindingComparator) {
    super.remove(item, customFindingComparator);
    this.priorities.delete(item);
    return this;
  }

  /**
   * Change priority of the item in a queue.
   * @param {*} item - item we're going to re-prioritize.
   * @param {number} priority - new item's priority.
   * @return {PriorityQueue}
   */
  changePriority(item, priority) {
    this.remove(item, new Comparator(this.compareValue));
    this.add(item, priority);
    return this;
  }

  /**
   * Find item by ite value.
   * @param {*} item
   * @return {Number[]}
   */
  findByValue(item) {
    return this.find(item, new Comparator(this.compareValue));
  }

  /**
   * Check if item already exists in a queue.
   * @param {*} item
   * @return {boolean}
   */
  hasValue(item) {
    return this.findByValue(item).length > 0;
  }

  /**
   * Compares priorities of two items.
   * @param {*} a
   * @param {*} b
   * @return {number}
   */
  comparePriority(a, b) {
    if (this.priorities.get(a) === this.priorities.get(b)) {
      return 0;
    }
    return this.priorities.get(a) < this.priorities.get(b) ? -1 : 1;
  }

  /**
   * Compares values of two items.
   * @param {*} a
   * @param {*} b
   * @return {number}
   */
  compareValue(a, b) {
    if (a === b) {
      return 0;
    }
    return a < b ? -1 : 1;
  }
}

[Wataru]

Magneto903, Не знаю, может minHeap коряво написан.

Вряд ли это причина ваших проблем, но changePriority (вернее вызываемый им remove) тут работает за линию. Поэтому в итоге решение, когда заработает, будет тормозить. Это можно вылечить, если переписать minHeap возвращать номер позиции куда добавленный элемент был воткнут в add. Ее надо в priorityQueue.add и changePriority сохранять. При вызове remove или changePriority надо удалять с этой позиции (немного переписать minHeap.remove не вызывая find, ведь номер позиции уже известен).

Добавляйте всюду отладочный вывод в консоль (minheap тоже), смотрите где память выделяется, куда девается.

[Magneto903]

Илья Николаевский, Вам скинуть код MinHeap?

[Wataru]

Magneto903, давайте...

[Magneto903]

Илья Николаевский,

MinHeap

import Heap from './Heap';

export default class MinHeap extends Heap {
  /**
   * Checks if pair of heap elements is in correct order.
   * For MinHeap the first element must be always smaller or equal.
   * For MaxHeap the first element must be always bigger or equal.
   *
   * @param {*} firstElement
   * @param {*} secondElement
   * @return {boolean}
   */
  pairIsInCorrectOrder(firstElement, secondElement) {
    return this.compare.lessThanOrEqual(firstElement, secondElement);
  }
}

Т.к. MinHeap зависит от Heap

Heap

import Comparator from '../../utils/comparator/Comparator';

/**
 * Parent class for Min and Max Heaps.
 */
export default class Heap {
  /**
   * @constructs Heap
   * @param {Function} [comparatorFunction]
   */
  constructor(comparatorFunction) {
    if (new.target === Heap) {
      throw new TypeError('Cannot construct Heap instance directly');
    }

    // Array representation of the heap.
    this.heapContainer = [];
    this.compare = new Comparator(comparatorFunction);
  }

  /**
   * @param {number} parentIndex
   * @return {number}
   */
  getLeftChildIndex(parentIndex) {
    return (2 * parentIndex) + 1;
  }

  /**
   * @param {number} parentIndex
   * @return {number}
   */
  getRightChildIndex(parentIndex) {
    return (2 * parentIndex) + 2;
  }

  /**
   * @param {number} childIndex
   * @return {number}
   */
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }

  /**
   * @param {number} childIndex
   * @return {boolean}
   */
  hasParent(childIndex) {
    return this.getParentIndex(childIndex) >= 0;
  }

  /**
   * @param {number} parentIndex
   * @return {boolean}
   */
  hasLeftChild(parentIndex) {
    return this.getLeftChildIndex(parentIndex) < this.heapContainer.length;
  }

  /**
   * @param {number} parentIndex
   * @return {boolean}
   */
  hasRightChild(parentIndex) {
    return this.getRightChildIndex(parentIndex) < this.heapContainer.length;
  }

  /**
   * @param {number} parentIndex
   * @return {*}
   */
  leftChild(parentIndex) {
    return this.heapContainer[this.getLeftChildIndex(parentIndex)];
  }

  /**
   * @param {number} parentIndex
   * @return {*}
   */
  rightChild(parentIndex) {
    return this.heapContainer[this.getRightChildIndex(parentIndex)];
  }

  /**
   * @param {number} childIndex
   * @return {*}
   */
  parent(childIndex) {
    return this.heapContainer[this.getParentIndex(childIndex)];
  }

  /**
   * @param {number} indexOne
   * @param {number} indexTwo
   */
  swap(indexOne, indexTwo) {
    const tmp = this.heapContainer[indexTwo];
    this.heapContainer[indexTwo] = this.heapContainer[indexOne];
    this.heapContainer[indexOne] = tmp;
  }

  /**
   * @return {*}
   */
  peek() {
    if (this.heapContainer.length === 0) {
      return null;
    }

    return this.heapContainer[0];
  }

  /**
   * @return {*}
   */
  poll() {
    if (this.heapContainer.length === 0) {
      return null;
    }

    if (this.heapContainer.length === 1) {
      return this.heapContainer.pop();
    }

    const item = this.heapContainer[0];

    // Move the last element from the end to the head.
    this.heapContainer[0] = this.heapContainer.pop();
    this.heapifyDown();

    return item;
  }

  /**
   * @param {*} item
   * @return {Heap}
   */
  add(item) {
    this.heapContainer.push(item);
    this.heapifyUp();
    return this;
  }

  /**
   * @param {*} item
   * @param {Comparator} [comparator]
   * @return {Heap}
   */
  remove(item, comparator = this.compare) {
    // Find number of items to remove.
    const numberOfItemsToRemove = this.find(item, comparator).length;

    for (let iteration = 0; iteration < numberOfItemsToRemove; iteration += 1) {
      // We need to find item index to remove each time after removal since
      // indices are being changed after each heapify process.
      const indexToRemove = this.find(item, comparator).pop();

      // If we need to remove last child in the heap then just remove it.
      // There is no need to heapify the heap afterwards.
      if (indexToRemove === (this.heapContainer.length - 1)) {
        this.heapContainer.pop();
      } else {
        // Move last element in heap to the vacant (removed) position.
        this.heapContainer[indexToRemove] = this.heapContainer.pop();

        // Get parent.
        const parentItem = this.parent(indexToRemove);

        // If there is no parent or parent is in correct order with the node
        // we're going to delete then heapify down. Otherwise heapify up.
        if (
          this.hasLeftChild(indexToRemove)
          && (
            !parentItem
            || this.pairIsInCorrectOrder(parentItem, this.heapContainer[indexToRemove])
          )
        ) {
          this.heapifyDown(indexToRemove);
        } else {
          this.heapifyUp(indexToRemove);
        }
      }
    }

    return this;
  }

  /**
   * @param {*} item
   * @param {Comparator} [comparator]
   * @return {Number[]}
   */
  find(item, comparator = this.compare) {
    const foundItemIndices = [];

    for (let itemIndex = 0; itemIndex < this.heapContainer.length; itemIndex += 1) {
      if (comparator.equal(item, this.heapContainer[itemIndex])) {
        foundItemIndices.push(itemIndex);
      }
    }

    return foundItemIndices;
  }

  /**
   * @return {boolean}
   */
  isEmpty() {
    return !this.heapContainer.length;
  }

  /**
   * @return {string}
   */
  toString() {
    return this.heapContainer.toString();
  }

  /**
   * @param {number} [customStartIndex]
   */
  heapifyUp(customStartIndex) {
    // Take the last element (last in array or the bottom left in a tree)
    // in the heap container and lift it up until it is in the correct
    // order with respect to its parent element.
    let currentIndex = customStartIndex || this.heapContainer.length - 1;

    while (
      this.hasParent(currentIndex)
      && !this.pairIsInCorrectOrder(this.parent(currentIndex), this.heapContainer[currentIndex])
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));
      currentIndex = this.getParentIndex(currentIndex);
    }
  }

  /**
   * @param {number} [customStartIndex]
   */
  heapifyDown(customStartIndex = 0) {
    // Compare the parent element to its children and swap parent with the appropriate
    // child (smallest child for MinHeap, largest child for MaxHeap).
    // Do the same for next children after swap.
    let currentIndex = customStartIndex;
    let nextIndex = null;

    while (this.hasLeftChild(currentIndex)) {
      if (
        this.hasRightChild(currentIndex)
        && this.pairIsInCorrectOrder(this.rightChild(currentIndex), this.leftChild(currentIndex))
      ) {
        nextIndex = this.getRightChildIndex(currentIndex);
      } else {
        nextIndex = this.getLeftChildIndex(currentIndex);
      }

      if (this.pairIsInCorrectOrder(
        this.heapContainer[currentIndex],
        this.heapContainer[nextIndex],
      )) {
        break;
      }

      this.swap(currentIndex, nextIndex);
      currentIndex = nextIndex;
    }
  }

  /**
   * Checks if pair of heap elements is in correct order.
   * For MinHeap the first element must be always smaller or equal.
   * For MaxHeap the first element must be always bigger or equal.
   *
   * @param {*} firstElement
   * @param {*} secondElement
   * @return {boolean}
   */
  /* istanbul ignore next */
  pairIsInCorrectOrder(firstElement, secondElement) {
    throw new Error(`
      You have to implement heap pair comparision method
      for ${firstElement} and ${secondElement} values.
    `);
  }
}

[Wataru]

Magneto903, Выглядит нормально.

[Magneto903]

Илья Николаевский, я ещё обратил внимание, что если не убирать циклfor (var child of graph[startNode].keys()) {, то переполнение не происходит, но путь тем не менее не находится или находится, но явно не тот, что нужен

[Wataru]

Magneto903, с этим циклом алгоритм не выполняется фактически.

[Magneto903]

Илья Николаевский, этот цикл зацикливается

while (parent) {
  		shortestPath.push(parent);
  		parent = parents.get(parent);
 	}

Почему то там как будто вершины указывают друг друга родителями вот так и скачет от одной к другой вершине

[Wataru]

Magneto903, Смотрите внимательно в отладке, этот цикл доходит до стартовой вершины? Выведите parents.

[Magneto903]

Илья Николаевский, Добавил буквально несколько отладочных выводов:

код

var findShortestPath = (graph, startNode, endNode) => {
 	var distances = new Map();
 	var parents = new Map();
 	var queue = new PriorityQueue();

	queue.add(startNode, 0);
	distances.set(startNode, 0);
 	distances.set(endNode, Infinity)
 	parents.set(endNode, null)
 	
 	/*	
 	for (var child of graph[startNode].keys()) {
 		distances.set(child, graph[startNode].get(child))
 	}
 	*/

	// find the nearest node
   	var node = queue.poll();

   	console.log('first_node', node)
	// for that node:
 	while (node) {
 		console.log('current_node', node)
 		// find its distance from the start node & its child nodes
  		var distance = distances.get(node);
  		var children = graph[node]; 

  		console.log("node's distance:", distance)
  		console.log("node's children:", children)
 		// for each of those child nodes:
    	for (var child of children.entries()) {
        	// save the distance from the start node to the child node
        	var newdistance = distance + child[1];
			// if there's no recorded distance from the start node to the child node in the distances object
			// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
        	if (!distances.get(child[0]) || distances.get(child[0]) > newdistance) {
				// save the distance to the object
     			distances.set(child[0], newdistance);	
				// record the path
     			parents.set(child[0], node);
     			if (queue.hasValue(child[0])) {
		        	queue.changePriority(child[0], newdistance);
		        } else {
		        	queue.add(child[0], newdistance);
		        }
    		} 
    		
        }
		// move to the nearest neighbor node
      	node = queue.poll()
    }
	
  
 	// using the stored paths from start node to end node
 	// record the shortest path
 	console.log("distances", distances)
 	console.log("parents:", parents)
 	var shortestPath = [endNode];
 	var parent = parents.get(endNode);
 	while (parent) {

  		shortestPath.push(parent);
  		parent = parents.get(parent);
 	}
 	shortestPath.reverse();
  
 	//this is the shortest path
 	var results = {
  		distance: distances.get(endNode),
  		path: shortestPath,
  		//all_distances: distances
 	};
 	// return the shortest path & the end node's distance from the start node
   	return results;
};

Тестирую на простом графе:

var test_graph = [
    'none',
    new Map([
        [2, 1],
        [3, 3],
        [4, 4]
    ]),
    new Map([
        [1, 2],
        [3, 4],
        [4, 6]
    ]),
    new Map([
        [1, 3],
        [2, 5],
        [4, 11]
    ]),
    new Map([
        [3, 14]
    ]),
]

console.log(test_graph)

var path = findShortestPath(test_graph, 1, 3)

console.log(path)

вот что вывелось (прежде чем память переполнилась)


Похоже, что я 2 раза обхожу вершину (в данном случае вершину 1), хотя должен только один раз. Т.к. как уже я выяснил queue.poll() работает правильно, видимо я посещенную вершину заново добавляю в очередь

[Wataru]

Magneto903, Странный у вас какой-то граф. Я правильно понял, что индекс в массиве - это начальная вершина, ключ в map - это вторая вершина, а значение - длина ребра?
У вас ребра вперед и назад разной длины, есть связь всех вершин с четвертой, а она назад только с третьей. Но дейкстра и в ориентированных графах работет, так что это не проблема.

Дабавьте еще вывода туда, где newDistance считается и в очереди что-то обновляется или добавляется. Проблема там, где второй раз выводится current_node 1. Видимо на предыдущей итерации он ее добавляет в очередь из дуги 1=>3

Как он ей делает distance = 3? Ведь в начале вы делаете distances.set(startNode, 0); и только уменьшаете расстояние.

Видимо косяк в этом коде:

if (!distances.get(child[0]) || distances.get(child[0]) > newdistance)

когда child[0] == 1, distances[1] ==0, newdistance ==3 он переписывает. Проверьте приоритет операций, что возвращает !distances.get(). Пройдитесь дебаггером.

[Magneto903]

Илья Николаевский, Да. вы правы, проблема оказалась именно в:

if (!distances.get(child[0]) || distances.get(child[0]) > newdistance)

Я заменил на

if (distances.get(child[0]) == undefined || distances.get(child[0]) > newdistance)

и всё заработало!

[Евгений Шалаев]

Magneto903, какая в итоге реализация получилась и какая скорость выполнения?

[Magneto903]

Евгений Шалаев, Пока только в разработке.

[Magneto903]

Илья Николаевский, Я попробовал последовать вашему совету и хранить отдельно позицию каждой точки в дереве, чтобы быстрее удалять.(Если оставить всё как было, то довольно сильно тормозит). На простом графе всё прекрасно работает. Но почему-то когда я начинаю его уже использовать для больших графов, которые используют боты, он не всегда может найти путь.
Я модифицировал следующие функции Heap: swap(), poll(), add(), remove() и find()

модифицированный Heap

/**
 * Parent class for Min and Max Heaps.
 */
class Heap {
  /**
   * @constructs Heap
   * @param {Function} [comparatorFunction]
   */
  constructor(comparatorFunction) {
    if (new.target === Heap) {
      throw new TypeError('Cannot construct Heap instance directly');
    }

    // Array representation of the heap.
    this.heapContainer = [];
    this.compare = new Comparator(comparatorFunction);
    this.indexes = new Map();
  }

  /**
   * @param {number} parentIndex
   * @return {number}
   */
  getLeftChildIndex(parentIndex) {
    return (2 * parentIndex) + 1;
  }

  /**
   * @param {number} parentIndex
   * @return {number}
   */
  getRightChildIndex(parentIndex) {
    return (2 * parentIndex) + 2;
  }

  /**
   * @param {number} childIndex
   * @return {number}
   */
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }

  /**
   * @param {number} childIndex
   * @return {boolean}
   */
  hasParent(childIndex) {
    return this.getParentIndex(childIndex) >= 0;
  }

  /**
   * @param {number} parentIndex
   * @return {boolean}
   */
  hasLeftChild(parentIndex) {
    return this.getLeftChildIndex(parentIndex) < this.heapContainer.length;
  }

  /**
   * @param {number} parentIndex
   * @return {boolean}
   */
  hasRightChild(parentIndex) {
    return this.getRightChildIndex(parentIndex) < this.heapContainer.length;
  }

  /**
   * @param {number} parentIndex
   * @return {*}
   */
  leftChild(parentIndex) {
    return this.heapContainer[this.getLeftChildIndex(parentIndex)];
  }

  /**
   * @param {number} parentIndex
   * @return {*}
   */
  rightChild(parentIndex) {
    return this.heapContainer[this.getRightChildIndex(parentIndex)];
  }

  /**
   * @param {number} childIndex
   * @return {*}
   */
  parent(childIndex) {
    return this.heapContainer[this.getParentIndex(childIndex)];
  }

  /**
   * @param {number} indexOne
   * @param {number} indexTwo
   */
  swap(indexOne, indexTwo) {
    const tmp = this.heapContainer[indexTwo];
    this.heapContainer[indexTwo] = this.heapContainer[indexOne];
    this.indexes.set(indexTwo, this.heapContainer[indexOne])
    this.heapContainer[indexOne] = tmp;
    this.indexes.set(indexOne, tmp)
  }

  /**
   * @return {*}
   */
  peek() {
    if (this.heapContainer.length === 0) {
      return null;
    }

    return this.heapContainer[0];
  }

  /**
   * @return {*}
   */
  poll() {
    if (this.heapContainer.length === 0) {
      return null;
    }

    if (this.heapContainer.length === 1) {
      return this.heapContainer.pop();
    }

    const item = this.heapContainer[0];
    this.indexes.delete(item)

    // Move the last element from the end to the head.
    this.heapContainer[0] = this.heapContainer.pop();
    this.heapifyDown();

    return item;
  }

  /**
   * @param {*} item
   * @return {Heap}
   */
  add(item) {
    this.indexes.set(item, this.heapContainer.length)
    this.heapContainer.push(item);
    this.heapifyUp();
    return this;
  }

  /**
   * @param {*} item
   * @param {Comparator} [comparator]
   * @return {Heap}
   */
  remove(item, comparator = this.compare) {
    // Find number of items to remove.
    const numberOfItemsToRemove = this.find(item, comparator).length;

    for (let iteration = 0; iteration < numberOfItemsToRemove; iteration += 1) {
      // We need to find item index to remove each time after removal since
      // indices are being changed after each heapify process.
      const indexToRemove = this.find(item, comparator).pop();

      // If we need to remove last child in the heap then just remove it.
      // There is no need to heapify the heap afterwards.
      if (indexToRemove === (this.heapContainer.length - 1)) {
        this.heapContainer.pop();

      } else {
        // Move last element in heap to the vacant (removed) position.
        this.heapContainer[indexToRemove] = this.heapContainer.pop();

        // Get parent.
        const parentItem = this.parent(indexToRemove);

        // If there is no parent or parent is in correct order with the node
        // we're going to delete then heapify down. Otherwise heapify up.
        if (
          this.hasLeftChild(indexToRemove)
          && (
            !parentItem
            || this.pairIsInCorrectOrder(parentItem, this.heapContainer[indexToRemove])
          )
        ) {
          this.heapifyDown(indexToRemove);
        } else {
          this.heapifyUp(indexToRemove);
        }
      }
      this.indexes.delete(item)
    }

    return this;
  }

  /**
   * @param {*} item
   * @param {Comparator} [comparator]
   * @return {Number[]}
   */
  find(item, comparator = this.compare) {
    /*
    const foundItemIndices = [];

    for (let itemIndex = 0; itemIndex < this.heapContainer.length; itemIndex += 1) {
      if (comparator.equal(item, this.heapContainer[itemIndex])) {
        foundItemIndices.push(itemIndex);
      }
    }

    return foundItemIndices;
    */
    var foundItemIndices = [];
    var index = this.indexes.get(item)
    if (index != undefined && index != null) {
      foundItemIndices.push(index)
    }
    
    return foundItemIndices
  }

  /**
   * @return {boolean}
   */
  isEmpty() {
    return !this.heapContainer.length;
  }

  /**
   * @return {string}
   */
  toString() {
    return this.heapContainer.toString();
  }

  /**
   * @param {number} [customStartIndex]
   */
  heapifyUp(customStartIndex) {
    // Take the last element (last in array or the bottom left in a tree)
    // in the heap container and lift it up until it is in the correct
    // order with respect to its parent element.
    let currentIndex = customStartIndex || this.heapContainer.length - 1;

    while (
      this.hasParent(currentIndex)
      && !this.pairIsInCorrectOrder(this.parent(currentIndex), this.heapContainer[currentIndex])
    ) {

      this.swap(currentIndex, this.getParentIndex(currentIndex));
      currentIndex = this.getParentIndex(currentIndex);
    }

  }

  /**
   * @param {number} [customStartIndex]
   */
  heapifyDown(customStartIndex = 0) {
    // Compare the parent element to its children and swap parent with the appropriate
    // child (smallest child for MinHeap, largest child for MaxHeap).
    // Do the same for next children after swap.
    let currentIndex = customStartIndex;
    let nextIndex = null;

    while (this.hasLeftChild(currentIndex)) {
      if (
        this.hasRightChild(currentIndex)
        && this.pairIsInCorrectOrder(this.rightChild(currentIndex), this.leftChild(currentIndex))
      ) {
        nextIndex = this.getRightChildIndex(currentIndex);
      } else {
        nextIndex = this.getLeftChildIndex(currentIndex);
      }

      if (this.pairIsInCorrectOrder(
        this.heapContainer[currentIndex],
        this.heapContainer[nextIndex],
      )) {
        break;
      }

      this.swap(currentIndex, nextIndex);
      currentIndex = nextIndex;
    }
  }

  /**
   * Checks if pair of heap elements is in correct order.
   * For MinHeap the first element must be always smaller or equal.
   * For MaxHeap the first element must be always bigger or equal.
   *
   * @param {*} firstElement
   * @param {*} secondElement
   * @return {boolean}
   */
  /* istanbul ignore next */
  pairIsInCorrectOrder(firstElement, secondElement) {
    throw new Error(`
      You have to implement heap pair comparision method
      for ${firstElement} and ${secondElement} values.
    `);
  }
}

[Wataru]

this.indexes у вас должен быть map из item в место в очереди.

В swap надо делать:

this.indexes.set(this.heapContainer[indexOne], indexOne);
this.indexes.set(this.heapContainer[indexTwo], indexTwo);

Надо в poll тоже переписывать index у pop-нутого элемента:
this.indexes.set(this.heapContainer[0], 0);

В remove тоже есть место где вы на место indexToRemove ставите последний элемент. Надо

indexes[heapContainer[indexToRemove]] = indexToRemove;

сделать.

Воде все косяки, что я нашел.

[Magneto903]

Илья Николаевский, Огромное спасибо!

[Magneto903]

Илья Николаевский, теперь работает за 0.2-0.5 ms проход одной итерации. Странно, по идее ускорение должно было быть примерно в n раз, т.е. в данном случае в 160 раз. Однако до ввода объекта indexes работало за 1-5ms...

[Wataru]

Magneto903, ускорение не в n раз. До этого было n^2+m, теперь стало (n+m) log n операций. Да и операции чуть посложнее стали. Где-то 10 раз и есть ускорение. Этого вам теперь должно хватить.

[Magneto903]

Илья Николаевский, Нет, увы этого не хватает((
Красный бот использует 2 раза Дейкстру:
1) Найти ближайшего зелёного бота
2) Найти путь до него

Зелёный бот использует 3 раза:
1) Найти ближайшего красного бота
2) Найти дальнюю точку от ближайшего красного бота
3) Найти путь до этой дальней точки

В итоге на пару красный бот - зелёный бот уходит в худшем случае 2.5ms.
Поэтому, уже даже при 2 парах может торможения и нет, но показатель в CPU Monitor'е очень близок к 100%. Т.е это сильная нагрузка, хотя всего 2 пары.

А я хотел хотя бы 10 пар...

Но видимо проблема не в реализации этого алгоритма, а в его использовании для этой задачи. Но это уже другой вопрос.

[Magneto903]

Илья Николаевский, а вы знакомы с wasm?

[Wataru]

Magneto903, Вообще нет.

[Magneto903]

Илья Николаевский, Ладно, на самом деле мне кажется, что проблема в моём коде c++. Я не очень хорошо знаю C++.
В общем, я переписал тот нестабильный, но быстрый алгоритм на C++. Ну всё работало в C++, я думал значит будет работать и в wasm. Но когда я скомпилировал, то начала возникать ошибка Uncaught RuntimeError: memory access out of bounds. (При выполнении get_dists())Насколько я понял, это значит, что я обращаюсь к чему-то неинициализированному. Может c++ как-то на это не обращал внимание, но wasm чувствителен.

Можете пожалуйста посмотреть, где я делаю "опасные" операции (сам я ничего не нашел, но повторюсь, я не силен в c++)

[Wataru]

Magneto903,

Попробуйте константы поднять. 20 соседей - возможно мало. Длина очередей может быть, вообще говоря, любой в этом решении.

[Magneto903]

Илья Николаевский, ну я тестировал на простом графе, где всего 5 вершин и 6 рёбер. Ошибка вроде не в этом. Но я думаю, что действительно стоит увеличить это число для больших графов

[Magneto903]

Wataru, ура ура ура, я наконец-то понял, что проблема была не в поиске пути в графе!!!

Answer 2

[Василий Банников]

Вариант 1:
Можно реализовать самостоятельно на js, но не использовать те фичи, которые снижают производительность.
Вариант 2:
Реализовать алгоритм на Rust и скомпилировать код под wasm.
Например есть такая либа: https://crates.io/crates/pathfinding, которую можно заиспользовать для этого

Answer 3

[profesor08]

А почему Javascript? В плане времени, 3-4мс, это ничто для интерпретируемого языка (запускал код в консоли браузера из первой ссылки). Там есть странные моменты, которые можно поправить, например вот этот `if (String(child) === String(startNode))`, или сделать поменьше операций с массивами, или заранее выделить им фиксированный размер, чтоб избежать пушей и динамического выделения памяти. Если понимаешь алгоритм, то можешь пробежаться по коду и поискать моменты, где можно отбросить ненужные итерации.

Answer 4

[Армянское Радио]

Написать на С/С++ и откомпилировать при помощи wasm. С большой долей вероятности, скорость будет не хуже нативного запуска программы на С/C++