Untitled

// https://levelup.gitconnected.com/finding-the-shortest-path-in-javascript-dijkstras-algorithm-8d16451eea34
// https://github.com/noamsauerutley/shortest-path/blob/master/test/shortestPath.spec.js

// Решение вот этого графа
// https://upload.wikimedia.org/wikipedia/commons/thumb/3/3b/Shortest_path_with_direct_weights.svg/800px-Shortest_path_with_direct_weights.svg.png


const shortestDistanceNode = (distances, visited) => {
	let shortest = null;

	for (let node in distances) {
		let currentIsShortest =
			shortest === null || distances[node] < distances[shortest];
		if (currentIsShortest && !visited.includes(node)) {
			shortest = node;
		}
	}
	return shortest;
};

const findShortestPath = (graph, startNode, endNode) => {
	// establish object for recording distances from the start node
	let distances = {};
	distances[endNode] = "Infinity";
	distances = Object.assign(distances, graph[startNode]);

	// track paths
	let parents = { endNode: null };
	for (let child in graph[startNode]) {
		parents[child] = startNode;
	}

	// track nodes that have already been visited
	let visited = [];

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

	// for that node
	while (node) {
		// find its distance from the start node & its child nodes
		let distance = distances[node];
		let children = graph[node];
		// for each of those child nodes
		for (let child in children) {
			// make sure each child node is not the start node
			if (String(child) === String(startNode)) {
				continue;
			} else {
				// save the distance from the start node to the child node
				let newdistance = distance + children[child];
				// 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
				// save the distance to the object
				// record the path
				if (!distances[child] || distances[child] > newdistance) {
					distances[child] = newdistance;
					parents[child] = node;
				}
			}
		}
		// move the node to the visited set
		visited.push(node);
		// move to the nearest neighbor node
		node = shortestDistanceNode(distances, visited);
	}

	// using the stored paths from start node to end node
	// record the shortest path
	let shortestPath = [endNode];
	let parent = parents[endNode];
	while (parent) {
		shortestPath.push(parent);
		parent = parents[parent];
	}
	shortestPath.reverse();

	// return the shortest path from start node to end node & its distance
	let results = {
		distance: distances[endNode],
		path: shortestPath,
	};

	return results;
};

// module.exports = findShortestPath;


// const graph = {
// 	start: { A: 5, B: 2 },
// 	A: { start: 1, C: 4, D: 2 },
// 	B: { A: 8, D: 7 },
// 	C: { D: 6, end: 3 },
// 	D: { end: 1 },
// 	end: {},
// };

// 0 = start
// 1 = A
// 2 = B
// 3 = end

const graph = {
	A: {B: 4, C: 2 },
	B: {C: 5, D: 10},
	C: {E: 3},
	E: {D: 4},
	D: {F: 11},
};




const shortestPath = findShortestPath(graph, 'A', 'F');
console.log(shortestPath);

// test(`shortest path from 'start' to 'end' should be 8 with start-A-D-end`, () => {
//   const shortestPath = findShortestPath(graph, 'start', 'end');
//   expect(shortestPath).toEqual({
//     distance: 8,
//     path: ['start', 'A', 'D', 'end'],
//   });
// });