Любой, кто когда-либо пользовался смартфоном для навигации, вероятно, сталкивался с ситуациями, когда ему предлагали несколько различных вариантов маршрута. Вы можете не осознавать, что вся работа по поиску самого быстрого маршрута требовала больших усилий, может быть, не для компьютера, но много всего происходит в фоновом режиме. Этот процесс, скорее всего, требует или имеет одну из основных концепций одного из самых важных алгоритмов нашего времени - алгоритма Дейкстры.

Алгоритм Дейкстры - это алгоритм поиска кратчайших путей между узлами взвешенного графа. Мы будем реализовывать функцию JavaScript для запуска нашего алгоритма. Вы спросите, что такое взвешенный граф? Граф - это абстрактный тип данных, используемый для моделирования набора соединений.

На вашем телефоне этот график будет выглядеть как карта, но под капотом это структура данных, называемая взвешенным графиком. Места на карте - это узлы графа, пути между ними - это ребра, а время, чтобы добраться от одного узла к другому, - это вес каждого края.

Основные шаги для поиска кратчайшего пути к финишу от начала заключаются в следующем.

  1. Перейдите к узлу, который мы не посещали, выбрав самый быстрый узел, чтобы добраться до него первым.
  2. На этом узле проверьте, сколько времени нам потребуется, чтобы добраться до каждого из его соседних узлов. Добавьте вес соседа ко времени, которое потребовалось, чтобы добраться до узла, на котором мы сейчас находимся. Имейте в виду, что мы вычисляем время, за которое мы достигаем этих узлов до посещения их.
  3. Убедитесь, что это вычисленное время быстрее, чем ранее известное кратчайшее время, чтобы добраться до этого узла. Если это быстрее, обновите наши записи, чтобы отразить новое самое короткое время. Мы также добавим этот узел в нашу линию узлов, которые нужно посетить в следующий раз. Эта линия будет расположена в порядке наименьшего расчетного времени достижения.

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

Чтобы начать наш график, давайте создадим объект, и мы будем использовать его в качестве аргумента для основного алгоритма.

//Create the graph object
//Each key represents a node on the graph. Each key has an object for its value, which represents the immediate neighbors and the weight of reaching that neighbor. 
const graph = {
  start: {A: 5, B: 2},
      A: {C: 4, D: 2},
      B: {A: 8, D: 7},
      C: {D: 6, finish: 3},
      D: {finish: 1},
 finish: {}
};

Итак, теперь, когда мы создали объект графика относительно изображения графика выше, как алгоритм Дейкстры будет работать с ним? Во-первых, ему нужно найти самый низкий узел, а затем обновить вес непосредственных соседей узла. Повторяйте эти два шага, пока не сделаете это на каждом узле. Наконец, верните наименьший вес для достижения узла и оптимальный путь, который мы нашли для достижения этого узла.

Чтобы отслеживать наши узлы и их расстояния, мы создадим еще один объект под названием «вес», который представляет собой расстояние от одного узла до следующего. Для начала мы можем сказать, что вес от начала до A равен 5, а от начала до B равен 2. Поскольку мы не знаем, где заканчивается путь, мы пока установит конечный вес на бесконечность. Вот как это выглядит.

//Keep track of the lowest weight from one node to the next.
const weight = {
 A: 5,
 B: 2,
 finish: Infinity
};

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

// Keep track of the lowest weight parent
const parents = {
  A: 'start', 
  B: 'start', 
  finish: null
};

Если вы никогда не слышали о кешировании, это означает, что для экономии времени мы также можем отслеживать узлы, которые мы уже посетили. Чтобы отслеживать это, мы будем использовать структуру данных массива.

const visited = ["start", "A", "B"];

Если вы снова посмотрите на график, мы не сможем продолжить поиск самого нижнего узла и обновить вес дочерних узлов.

Самый низкий вес - это узел B (2), а его дочерние элементы - это A и D. Мы добавляем их к нашему весовому объекту следующим образом:

//weights
{ A: 5,
  B: 2,
  D: 9, //the total weight from start to D which is 2 + 7 = 9
  Finish: Infinity
};

Затем мы обновляем обработанные и родительские структуры данных, пока не обработаем все узлы.

Давайте фактически определим функцию, которая дает нам узел с наименьшим весом, который не был обработан с учетом весов и обработанных узлов.

const findLowestWeightNode = (weights, processed) => {
   const knownNodes = Object.keys(weights)
   
   const lowestWeightNode = knownNodes.reduce((lowest, node) => {
   if (lowest === null && !processed.includes(node)) {
    lowest = node;
    }
  if (weights[node] < weights[lowest] && !processed.includes(node)) {    
  lowest = node;
   }
  return lowest;
  }, null);
  
 return lowestWeightNode
};

Теперь давайте реализуем основную функцию dijkstra, которая будет принимать наш исходный график в качестве параметра. Сначала мы создадим веса, родителей и обработанные структуры данных.

const dijkstra = (graph) => {
   
// track lowest cost to reach each node  
const weights = Object.assign({finish: Infinity}, graph.start); 
  
// track paths  
const parents = {finish: null};  
for (let child in graph.start) {    
  parents[child] = 'start';  
 }
   
// track nodes that have already been processed  
const processed = [];
//Next, we’ll set the initial value of the node being processed //using the lowestCostNode function. Then, we’ll begin a while loop, //which will continuously look for the cheapest node.
let node = findLowestWeightNode(weights, processed);
   
while (node) {
//Get the weight of the current node
let weight = weights[node];
//Get all the neighbors of current node
let children = graph[node]; 
//Loop through each of the children, and calculate the weight to reach that child node. We'll update the weight of that node in the weights object if it is lowest or the ONLY weight available
for (let n in children) {   
    let newWeight = weight + children[n];     
     if (!weights[n] || weights[n] > newWeight) { 
      weights[n] = newWeight; 
      parents[n] = node;
        }
     }
 //push processed data into its data structure
 processed.push(node);
 // repeat until we processed all of our nodes.    
 node = findLowestWeightNode(weights, processed);
}
.... continued

Все это кажется большим, НО мы почти закончили! После завершения цикла while у нас будет наименьший вес для достижения конечного узла. Теперь мы настраиваем нашу последнюю функцию, чтобы получить наш оптимальный путь. Мы делаем это, глядя на объект наших родителей, который мы создали ранее.

...
let optimalPath = ['finish'];
let parent = parents.finish;
while (parent) {
    optimalPath.unshift(parent);
    parent = parents[parent]; // add parent to start of path array
  }
  
  const results = {
    distance: weights.finish,
    path: optimalPath
  };

  return results;

}; //end of function

Наши окончательные результаты будут выглядеть примерно так

{ distance: 8, path: [ 'start', 'A', 'D', 'finish']