Как показать вес ребра графа в алгоритме Дейкстры?

Question

[kotbasikcom]

function shortPathWithDistances(graph, start, end) {
  const distances = {}
  const visited = new Set()
  const path = {}

  for (const key in graph) {
    if (key !== start) {
      distances[key] = Infinity
    } else {
      distances[start] = 0
    }
  }
  while (!visited.has(end)) {
    let lowestDistance = Infinity
    let node = null

    for (const key in distances) {
      if (lowestDistance > distances[key] && !visited.has(key)) {
        lowestDistance = distances[key]
        node = key
      }
    }
    const neighbors = graph[node]
    for (const key in neighbors) {
      const newDistance = distances[node] + neighbors[key]
      if (newDistance < distances[key]) {
        distances[key] = newDistance
        path[key] = node
      }
    }
    visited.add(node)
  }
  const shortPath = []
  let current = end
  while (current !== start) {
    const currentWithDistance = { [current]: distances[current] }
    shortPath.unshift(currentWithDistance)
    current = path[current]
  }
  shortPath.unshift({ [start]: 0 })
  return shortPath
}

Как выводить не длину пути до стартовой вершины (в коде "distances[current]"), а вес ребра до предыдущей вершины?

Answer 1

[Антон Горецкий]

Чтобы показать вес ребра графа в алгоритме Дейкстры, нам необходимо сохранять информацию о весах ребер между предыдущей вершиной в пути и текущей вершиной. Для этого мы можем вести отдельный объект, который будет хранить веса ребер для каждой вершины в path.

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

Вот обновленная функция:

function shortPathWithDistances(graph, start, end) {
  const distances = {};
  const visited = new Set();
  const path = {};
  const edgeWeights = {}; // Новый объект для хранения весов ребер

  for (const key in graph) {
    if (key !== start) {
      distances[key] = Infinity;
    } else {
      distances[start] = 0;
    }
  }
  while (!visited.has(end)) {
    let lowestDistance = Infinity;
    let node = null;

    for (const key in distances) {
      if (lowestDistance > distances[key] && !visited.has(key)) {
        lowestDistance = distances[key];
        node = key;
      }
    }
    const neighbors = graph[node];
    for (const key in neighbors) {
      const newDistance = distances[node] + neighbors[key];
      if (newDistance < distances[key]) {
        distances[key] = newDistance;
        path[key] = node;
        edgeWeights[key] = neighbors[key]; // Сохраняем вес ребра
      }
    }
    visited.add(node);
  }
  const shortPath = [];
  let current = end;
  while (current !== start) {
    const currentWithDistance = { node: current, edgeWeight: edgeWeights[current] };
    shortPath.unshift(currentWithDistance);
    current = path[current];
  }
  shortPath.unshift({ node: start, edgeWeight: 0 });
  return shortPath;
}

Теперь в построенном массиве shortPath каждый элемент будет содержать информацию о текущей вершине и весе ребра, ведущего к предыдущей вершине, сформированного наименьшего пути.

Comments

[kotbasikcom]

Спасибо. Вот же я тупарь. Пытался сохранять так

const newDistance = distances[node] + neighbors[key];
const rods = neighbors[key];
if (newDistance < distances[key]) {