// Создаем граф с помощью хэш-таблицы
const graph = {
'A': { 'B': 5, 'C': 2 },
'B': { 'A': 5, 'D': 1 },
'C': { 'A': 2, 'D': 6 },
'D': { 'B': 1, 'C': 6 }
};
function dijkstra(graph, startNode) {
// Инициализируем объекты для хранения расстояний и предшествующих узлов
const distances = {};
const previous = {};
const queue = [];
// Устанавливаем начальное расстояние в 0 и остальные в Infinity
Object.keys(graph).forEach(node => {
distances[node] = Infinity;
previous[node] = null;
queue.push(node);
});
distances[startNode] = 0;
while (queue.length > 0) {
// Находим узел с наименьшим расстоянием
const minDistanceNode = queue.reduce((minNode, node) => {
return distances[node] < distances[minNode] ? node : minNode;
});
// Удаляем текущий узел из очереди
queue.splice(queue.indexOf(minDistanceNode), 1);
// Проверяем соседей текущего узла
for (let neighbor in graph[minDistanceNode]) {
const distance = graph[minDistanceNode][neighbor];
const totalDistance = distances[minDistanceNode] + distance;
if (totalDistance < distances[neighbor]) {
// Обновляем расстояние до соседа, если оно меньше текущего
distances[neighbor] = totalDistance;
previous[neighbor] = minDistanceNode;
}
}
}
return { distances, previous };
}
// Пример использования
const startNode = 'A';
const { distances, previous } = dijkstra(graph, startNode);
console.log(distances);
console.log(previous);
Простой
