31 Мар


2019

Алгоритм Дейкстры для поиска кратчайшего пути в графе.
Наконец мой взор пал на этот алгоритм 😉 в это сложно поверить но я лелеял мечту реализовать его около 3 лет, но все как-то руки не доходили. На самом деле на разбор и обдумывание ушло пару дней, алгоритм достаточно прост, и самое главное понять основную концепцию. 
Данный алгоритм можно логически разделить на 2 подзадачи:
  1. Расчет минимального пути от входной вершины графа до всех остальных вершин.
  2. Обратный расчет оптимального пути от конечной вершины до начальной используя массив минимальных переходов по ребрам. Рассчитывается в пункте 1.
И собственно на этом все. Основные определения можно посмотреть тут (ссылка).
 
Перед началом разбора алгоритма краткий ликбез по структуре данных 'Граф'.
Для примера возьмем следующий неориентированный граф:
1. Метод хранения ребер.
g = [
  [0, 1],
  [0, 3],
  [1, 0],
  [1, 2],
  [2, 3],
  [2, 1],
  [2, 4],
  [3, 0],
  [3, 2],
  [4, 2],
  [4, 5],
  [5, 4]
]

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

2. Хранение переходов в виде матрицы.

g = [
  [0, 8, 0, 2, 0, 0],
  [8, 0, 12, 0, 0, 0],
  [0, 12, 0, 6, 1, 0],
  [2, 0, 6, 0, 0, 0,],
  [0, 0, 1, 0, 0, 22],
  [0, 0, 0, 0, 22, 0]
]

В данном случае удобно хранить вес ребер между 2 вершинами.

3. Список смежности (для наглядности хеш таблица)

g3 = {
  0: (1, 3),
  1: (0, 2),
  2: (1, 3, 4),
  3: (0, 2),
  4: (2, 5)
  5: (4, )
}

Визуализация

Этот пункт можно пропустить, т.к. граф это структура, и работаю я со структурой. Однако это добавит наглядности. 

 

deikstra.js
function paintGraph(g, groups = []) {
  var len = undefined;
  const nodes = [];
  g.forEach((_, i) =>
    nodes.push({
      id: i,
      label: `${i}`,
      group: groups[i] ? groups[i] : 0,
      shape: 'circle'
    })
  );
  const visited = new Array(g.length).fill(0);
  const edges = [];
  for (const i in g) {
    for (const j in g[i]) {
      if (g[i][j] !== 0 && i !== j) {
        if (!visited[j]) {
          edges.push({ from: i, to: j, label: `${g[i][j]}` });
        }
      }
    }
    visited[i] = 1;
  }
  // create a network
  var container = document.getElementById('mynetwork');
  var data = {
    nodes: nodes,
    edges: edges
  };
  var options = {
    physics: false,
    nodes: {
      shape: 'dot',
      size: 30,
      font: {
        size: 32
      },
      borderWidth: 2,
      shadow: true
    },
    edges: {
      width: 2,
      shadow: true
    }
  };
  network = new vis.Network(container, data, options);
}

const g = [
  [0, 8, 0, 2, 0, 0],
  [8, 0, 12, 0, 0, 0],
  [0, 12, 0, 6, 1, 0],
  [2, 0, 6, 0, 0, 0],
  [0, 0, 1, 0, 0, 22],
  [0, 0, 0, 0, 22, 0]
];

paintGraph(g);

 

index.html
<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <title>Page Title</title>
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <link rel="stylesheet" type="text/css" media="screen" href="main.css">
  <link rel="stylesheet" type="text/css" href="https://cdnjs.cloudflare.com/ajax/libs/vis/4.21.0/vis.min.css">
  <style type="text/css">
    #mynetwork {
      width: 100%;
      height: 100vh;
      border: 1px solid lightgray;
    }
  </style>
  <script src="main.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/vis/4.21.0/vis.min.js"></script>
</head>
<body>
  <div id="mynetwork"></div>

  <script src="./deikstra.js"></script>
</body>
</html>

И на выходе у нас получается следующее визуальное представление графа.

 

Реализация.

Спустя кучу текста сам алгоритм. Лично мне для понимания помогло 5 минутное залипание в следующую гифку:

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

Перезапись происходит если соблюдены следующие условия:

  1. Рядомстоящая вершина не помечена как посещенная.
  2. Сумма переходов до вершины графа откуда осуществяется переход + вес ребра до вершины графа куда осуществляется переход должен быть меньше чем сумма переходов в рассматриваемой вершине.

После того как все соседние вершины рассмотрены помечаем текущую вершину как посещенную, переходим к следующей.

function buildWeightMap(g, startPoint) {
  // массив для хранения посещенных вершин
  const visitedNode = new Array(g.length).fill(0);
  // массив содержащий кратчайшие веса переходов, заполняем бесконечностью, либо недостежимым числом
  // Предполагая что сумма весов не может превысить нашу 'бесконечность'
  const weightsMap = new Array(g.length).fill(Infinity);
  // Вес до начального пути 0, ну что вы в самом деле..мы же на месте стоим!
  weightsMap[startPoint] = 0;
  // Начинаем рассматривать алгоритм с начальной вершины.
  let currentNode = startPoint;
  // Направление куда ходим по графу, изначально идем по вершинам которые больше текущей
  let counterForward = +1;
  // Повторяем цикл пока все вершины не повещены
  while (visitedNode.indexOf(0) > -1) {
    // Итерируем по связанным вершинам.
    for (let j in g[currentNode]) {
      /* Проверяем что:
      1. Соседняя вершина ранее не была посещена
      2. Сумма до текущей вершины + вес ребра до следующей больше чем предыдущий минимальный путь
      3. Рассматриваемая вершина вообще есть (не 0, в js 0 == false)
      Если 1 из условий верно - прпоускаем шаг.
      */
      if (
        visitedNode[j] ||
        g[currentNode][j] + weightsMap[currentNode] > weightsMap[j] ||
        g[currentNode][j] === 0
      ) {
        continue;
      }
      // Запись нового минимального пути до вершины.
      weightsMap[j] = g[currentNode][j] + weightsMap[currentNode];
    }
    // Помечаем текущую вершину посещенной
    visitedNode[currentNode] = 1;
    // Двигаем согласно установленному направлению
    currentNode += counterForward;
    // Если дошли до конца массива то
    if (currentNode >= g.length) {
      // Устанавливаем текущую вершину на стартовую позицию
      currentNode = startPoint;
      // Менянем направление обхода массива посещенных нод к началу массива
      counterForward = -1;
    }
  }
  return weightsMap;
}

Передав наш граф в данную функцию получим на выходе следующий массив: [8, 12, 0, 6, 1, 23]. Что соответствует минимальной сумме ребер для перехода во все вершины из стартовой позиции. Если взглянуть на граф (визуально) то можно сделать вывод что это соответствует действительности (индекс массива соответвует вершине графа).

На основании этих весов можно построить наиболее оптимальный путь из конечной вершины в стартовую.

function buildShortestPath(g, weightsMap, endPos) {
  // Минимальная сумма ребер от стартовой до конечной вершины
  let endNodeWeight = weightsMap[endPos];
  //  Инициализация массива вершин соответвующих маршруту
  const path = [];
  // текущая позиция соответствующая рассматриваемой вершины
  let pos = endPos;
  // выполянем до тех пор пока весь рассматрвиаемой вершины не будет равен 0
  // что соответствует стартовой вершины графа
  while (endNodeWeight !== 0) {
    // итерируем по всем связанным вершинам
    for (let i in g[pos]) {
      // проверка на то что вес текущий позиции равен сумме веса предыдущей вершины 
      // + вес ребра для перехода из смежных вершин. (Это гарантирует то что путь минимальной длины)
      if (endNodeWeight === g[pos][i] + weightsMap[i]) {
        // записваем вершину в массив путей
        path.unshift(+i);
        // смещаем вес на следующую вершину
        endNodeWeight = weightsMap[i];
        // выбираем новую вершину для рассмотрения
        pos = i;
      }
    }
  }
  return path;
}

Для нашего графа кратчайший путь до позиции 0 (из вершины 2) будет следующим: [2, 3, 0].

Пощупать можно тут. Для изменения своего графа придется редактировать код.

Чуть позже тут появится интерактивна версия.

 

Философия мысли
Алгоритмы